6
$\begingroup$

Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields.

More precisely, let $p$ be prime and $\omega=e^{2\pi i/p}$, the complex $p$th root of unity, and let $\Omega$ be the matrix given by $\Omega_{ij}=\omega^{ij}$, for $i,j \in \{0,1,\dots,p-1\}$. Then Chebotarev's theorem on roots of unity says that every square submatrix of $\Omega$ is nonsingular; see wikipedia.

Alternatively, this is equivalent to stating that, for a complex-valued polynomial $f$ of degree less than $p$, if $f$ evaluates to zero for $t$ distinct powers of $\omega$, then either $f$ is zero, or $f$ has at least $t+1$ terms, or in other words, $$|\mathrm{supp}(f)| + |\mathrm{supp}(\hat{f})| > p.$$

Suppose then that $q$ is a prime power for which $p$ divides $q-1$, such that $\mathbf{F}_q$ contains a primitive $p$th root of unity $\omega$. Does the analogue hold there? I am particularly interested in the case that $q$ is prime.

The $2 \times 2$ square submatrices will be nonsingular because a polynomial $x^a + cx^b$, where $p>a>b\geq 0$, $c \neq 0$ will have a root $\omega^i$ if and only if $\omega^{(a-b)i}=c$, which will hold for at most one $i \in [p]$. Computation shows the analogue holds for the $p=7$th roots of unity modulo $q=29$.

$\endgroup$

1 Answer 1

3
$\begingroup$

Not for $GF(p)$ of prime cardinality. Consider a nontrivial factorization $p-1=uv$ which always exists. Let $w$ be primitive in $GF(p)^{\ast}$ The "regular" DFT submatrix which is made up of $u^{th}$ row and every $v^{th}$ column entry is an all 1 matrix and singular. More generally, when we have $GF(p^m)$ a primitive element has order $p^m-1$ and since $p^m-1=(p-1)(p^{m-1}+p^{m-2}+\cdots+1)$ is a valid factorization a similar argument holds. Thus the answer is no for any finite field.

Edit in response to comment by OP: Thanks for clarifying the question. I believe that it would fail in that case as well, since there is an extra dependency in finite fields: All elements, including $\omega$ of order $p$ inside a $GF(q)$ with $p|(q-1)$, have a characteristic polynomial $P$ of moderate degree. In this case, the set of determinant polynomials (which is quite large) would have to avoid all multiples of $P$ which is very unlikely. There may well be a pigeonhole type proof for this. Some quick computations confirmed this. Take $GF(23)$ and $w=2$ of order $11$. Then the indices $I\times J=(0,2,6)\times(0,1,3)$ for example lead to $$[w^{I(k)J(l)}]_{k,l=1,\ldots,3}$$ the $3\times3$ submatrix with zero determinant.

$\endgroup$
1
  • $\begingroup$ My question is: if $GF(q)$ contains a primitive $p$th root of unity $\omega$, where $p$ is prime, does the Vandermonde matrix $[\omega^{ij}]_{i,j=0}^{p-1}$ contain any singular square submatrices? $\endgroup$
    – user41530
    Dec 13, 2015 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.