Principal Non-singularity of Fourier Matrices on ℤ p × ℤ q \mathbb{Z}_{p}\times\mathbb{Z}_{q} and ℤ 2 k × ℤ q \mathbb{Z}_{2}^{k}\times\mathbb{Z}_{q}

Weiqi Zhou · 2025

Read Principal Non-singularity of Fourier Matrices on ℤ p × ℤ q \mathbb{Z}_{p}\times\mathbb{Z}_{q} and ℤ 2 k × ℤ q \mathbb{Z}_{2}^{k}\times\mathbb{Z}_{q} by Weiqi Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01189.txt.

Introduction

Weiqi Zhou proves a matrix result in a solo 2025 mathematics note. Fourier matrices on cyclic groups have a famous property from Chebotarëv: no minor vanishes when the size is prime. For products of two groups, the picture is less complete. Zhou asks when all principal minors stay nonzero there.

He covers pairs of distinct odd primes under a size and generation condition. He also covers groups mixing powers of two with an odd prime. In the second case a reordering of rows and columns may be needed. The proof repackages known methods into one unified exposition. The result matters for building Riesz bases of exponentials. Those bases shape signal analysis on irregular domains.

Catalog record

CREATORWeiqi Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01189

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Principal Non-singularity of Fourier Matrices on ℤ p × ℤ q \mathbb{Z}_{p}\times\mathbb{Z}_{q} and ℤ 2 k × ℤ q \mathbb{Z}_{2}^{k}\times\mathbb{Z}_{q} Weiqi Zhou Abstract Let F n F_{n} be the n × n n\times n Fourier matrix (on cyclic groups ℤ n \mathbb{Z}_{n} ), a reknowned theorem of Chebotarëv asserts that all minors in F n F_{n} for prime n n are non-zero. In this short note it is shown that (i) all principal minors in the Kronecker product F p ⊗ F q F_{p}\otimes F_{q} are non-vanishing (principal non-singularity) for distinct odd primes p , q p,q if q q is large enough and generates the multiplicative group ℤ p ∗ \mathbb{Z}_{p}^{*} ; (ii) the Fourier matrix on ℤ 2 k × ℤ q \mathbb{Z}_{2}^{k}\times\mathbb{Z}_{q} is principally non-singular upon permutation (in particular, for k = 1 k=1 the identity permutation suffices) for odd prime q q and k = 1 , 2 , 3 k=1,2,3 . The proof is just an exposition of existing techniques re-organized in a unified way. The result will have implications in combining Riesz bases of exponentials. Keywords : Chebotarev’s Theorem, Uncertainty Principle, Principle Minor, Fourier Matrices, Kronecker Product. 2020 MSC : 42A99, 15A15 1 Introduction Let A be a square matrix whose rows and columns are indexed by the same set, and \mathcal{I},\mathcal{J} subsets of the index set. Denote by A[\mathcal{I},\mathcal{J}] the submatrix obtained by taking row indices from \mathcal{I} and column indices from \mathcal{J} (If \mathcal{I},\mathcal{J} are singletons then it is the corresponding entry, i.e., A[i,j] means the i,j -th entry). A minor is the determinant of a submatrix satisfying |\mathcal{I}|=|\mathcal{J}| . If in addition \mathcal{I}=\mathcal{J} , then the submatrix is called principal and its determinant is called a principal minor . We shall say that a matrix is principally non-singular if all its principal minors are non-zero, and principally non-singular upon permutation if there is a column permutation so that all principal minors in the permuted matrix are non-zero. Let Z_{n}=\{0,1,\ldots,n-1\} be the additive cyclic group of order n , and set \zeta_{n}=e^{2\pi i/n} . The Fourier matrix on the finite Abelian group \mathbb{Z}_{n_{1}}\times\ldots\times\mathbb{Z}_{n_{d}} is the matrix indexed by \mathbb{Z}_{n_{1}}\times\ldots\times\mathbb{Z}_{n_{d}} with its j,k -th entry given by \prod_{\ell=1}^{d}\zeta_{n_{\ell}}^{j_{\ell}k_{\ell}} where both j=(j_{1},\ldots,j_{d}) and k=(k_{1},\ldots,k_{d}) are in \mathbb{Z}_{n_{1}}\times\ldots\times\mathbb{Z}_{n_{d}} . It is typical to further attach the factor n^{-1/2} with n=n_{1}\ldots n_{d} to make the matrix unitary, but in this article it is more convenient not to include this scaling factor. When d=1 , it is then the usual n\times n DFT matrix scaled by \sqrt{n} and we denote it by F_{n} . Therefore F_{n} can also be viewed as an n\times n Vandermonde matrix on n -th roots of unity. A celebrated theorem of Chebotarëv (see e.g., [ 16 ] ) states that if p is a prime number, then all minors in F_{p} are non-zero. This theorem is also equivalent to the enhanced (compared to the usual uncertainty principal as in [ 6 , 15 ] ) uncertainty principle (see [ 17 ] ) that |\supp(\vec{x})|+|\supp(F_{p}\vec{x})|\geq p+1 , where \supp(\vec{x})=\{k\in\mathbb{Z}_{p}:x_{k}\neq 0\} is the support of \vec{x} . For composite n this is in general not true, for example if n=4 and \mathcal{I}=\{0,2\} , then all entries in the principal submatrix F_{4}[\mathcal{I},\mathcal{I}] are identically 1 . There have been efforts on understanding whether permuted Fourier matrices can be principally non-singular, this is primarily motivated by classical questions in sampling theory such as when can we combine Riesz exponential bases on disjoint sets to form a new Riesz exponential basis on the union of these sets, or conversely how can we split a Riesz exponential basis on a set to get Riesz exponential bases on each individual component in a partition of the original set. A Riesz basis is the image of an orthonormal basis under a bounded (away from both \infty and 0 ) linear operator. In the absence of an orthogonal exponential basis (e.g., triangles and disks admit no orthogonal Fourier bases [ 9 ] ), a Riesz exponential basis would be a good choice for analyzing and reconstructing functions. In the introductory part of e.g., [ 12 , 14 ] there are rich examples showing the complexity of this problem. Denote the multiplicative group modulo n by \mathbb{Z}_{n}^{*} . In simpler settings such as when the underlying set is a finite collection of intervals with rational end points, then the possibility of combing or splitting Riesz exponential bases will rely critically on the principal non-singularity of F_{n} upon permutations. The conjecture that F_{n} is principally non-singular upon permutation (in particular it is conjectured that the identity permutation shall suffice if n is square free) is thereof posed in the recent work [ 2 , 3 ] . This is supported by numerical experiments up to n=30 and proved for n=2p and n=qr in [ 13 ] for odd primes p,q,r with q large enough and generating \mathbb{Z}_{r}^{*} . It is also known (see e.g., [ 1 ] ) that as n grows the smallest non-zero principal minor in n^{-1/2}F_{n} (scaled to be unitary) decay exponentially (e.g., the minimum principal minor is about 10^{-11} in for n=30 ), which makes them difficult to detect numercially. Principally non-singularity of a Fourier matrix on some finite Abelian group G can also be interpreted as a form of uncertainty principle that vectors on G and their Fourier transforms can not have disjoint supports. Let A\in\mathbb{C}^{m\times n} and B\in\mathbb{C}^{m^{\prime}\times n^{\prime}} , the Kronecker product A\otimes B is an mm^{\prime}\times nn^{\prime} matrix defined as A\otimes B=\begin{pmatrix}A[0,0]B&\ldots&A[0,n-1]B\\ \vdots&\ddots&\vdots\\ A[m-1,0]B&\ldots&A[m-1,n-1]B\end{pmatrix}. (1) Since any k\in\mathbb{Z}_{mn} can be uniquely write as k=q_{k}n+r_{k} for some q_{k}\in\mathbb{Z}_{m} and some r_{k}\in\mathbb{Z}_{n} , from ( 1 ) it is clear that F_{m}\otimes F_{n} is the Fourier matrix on \mathbb{Z}_{m}\times\mathbb{Z}_{n} with the index correspondence being that the j,k -th entry in F_{m}\otimes F_{n} corresponds to the (q_{j},q_{k}),(r_{j},r_{k}) -th entry in the Fourier matrix on \mathbb{Z}_{m}\times\mathbb{Z}_{n} . This also shows that F_{m}\otimes F_{n} only differs from F_{n}\otimes F_{m} by a simultaneous permutation. The purpose of this short note is to show in Corollary 1 and Corollary 2 respectively that F_{p}\otimes F_{q} is principally non-singular for distinct odd primes p,q if q is large enough and generates Z_{p}^{*} , and that \underbrace{F_{2}\otimes\ldots\otimes F_{2}}_{k\text{ terms}}\otimes F_{q} is principally non-singular upon permutation (in particular, for k=1 the identity permutation suffices) for odd prime q and k=1,2,3 . The proof is essentially the same as in [ 8 , 13 ] with the method summarized and unified in Theorem 1 . 2 Main Results The following lemma is originally stated in [ 8 , Lemma 2] for polynomials on finite fields of prime orders, it actually holds in many cases (e.g., it is true in \mathbb{C}[x] ) since all we need for it to hold is just a polynomial ring with a well defined notion of formal derivatives that satisfies the product rule, allows factorization into linear factors, and is non-vanishing, hence we state it for polynomials on integral domains for most generality (see e.g., [ 11 , Chapter III-6, Theorem 6.7, Lemma 6.9, Theorem 6.10] ) and for completeness also include the proof (despite that the proof is exactly the same). Lemma 1 . [ 8 , Lemma 2] Let D be

Read the complete text