[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]
Currently, we are asking whether all submatrices of the order- Vandermonde matrix over a finite extension of are invertible where is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.
We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.
Let denote an arithmetic progression of length $latek k$. Let for .
The Szemerédi theorem says, any “sufficiently dense” subset contains infinitely many for all . A finitary version says: Fix your favourite . Then, there exists a natural such that if you look any subset of size at least , you will find an . Yet another version says:
Szemerédi’s Theorem. The size of the largest subset without an cannot be too large; in particular, it is .
Recall that a function is if it grows too slow compared to , so that .
Recall that the entry of an order- Vandermonde matrix is just where is a principal th root of unity in the field . This means, the th row of is
and the th column is
We can generalize the row vector as for some integers where
Now, let be a set of arbitrary distinct nongenative integers. For some positive integer , we can build a generalized Vandermonde matrix as follows. The th entry of would be
so that the th row becomes
and the th column of has the form
Since the exponents of along any row of form an arithmetic progression, it is easy to see that is invertible. (Why? When computing the determinant, we can factor out from the th row for , leaving a Vandermonde matrix of order generated by . This matrix is non singular since is also a th root of unity.)
Let be the set of column-indices of above, and recall that this is an arithmetic progression in . What can we say about ?
Let be a proper subspace of so that . Suppose . By our observation above, cannot contain an arithmetic progression of length , because otherwise, the matrix would be invertible and its columns would span ; since by assumption, it would imply , a contradiction.
This leads us to the following observation.
Observation: If contains an arithmetic progression of length , then
Now let us ask the following question.
Question: Let be an arbitrary strict subspace of . If we pick a at random, what is the probability that ?
Suppose there is a set such that the vectors . Since is a strict subspace of , does not contain an arithmetic progression of length , and by Szemeredi’s theorem. The probability that equals the probability that , which is , which tends to zero as goes to infinity.
Lemma (Due to Alex Russell). Let be an arbitrary strict subspace of . If we pick a at random,
as goes to infinity.
We are ready to prove the following nontrivial statement about the minors of the Vandermonde matrix. (This theorem is due to Alex Russell and Ravi Sundaram.)
Let be a prime and be an order- Vandermonde matrix over the field containing a principal th root of unity. Let be the submatrix of indexed by the rows in and columns in .
Theorem A (Due to Alex Russell). Let a constant. Select two size- subsets where is arbitrary and is uniformly random. The probability that the submatrix is invertible is , i.e., the probability tends to one as goes to infinity.
The outline of the proof is as follows. We select distinct random integers one by one and add it to a set which is initially empty. At any time, let . Everytime we pick a random , we invoke the lemma above to show that as goes to infinity. We repeat this for times. Because the samples are independent, the probability that some (out of the samples) is bad is at most . If this happens, we say that the subset is bad. Otherwise, and we got ourselves an invertible -submatrix given by the columns for all .
A Chebotarev-like Statement. Suppose the field contains all th roots of unity, let be the corresponding Vandermonde matrix. A matrix is totally invertible if every submatrix is invertible. Chebotarev’s thoerem states that the matrix is totally invertible.
Theorem A allows us to make a probabilistic statement which is similar to Chebotarev’s theorem in spirit. Continuing the proof-outline of Theorem A, suppose is an arbitrary subset of of a constant size. Similarly, let be a uniformly random subset of of a constant size. Let . Let .
The probability that some order- submatrix of is singular is no more than
This probability is as long as the sets have constant sizes. Also notice that the same argument holds if we use the transpose for . This leads us to the following corollary.
Corollary. Fix . Select two constant-size subsets where is arbitrary and is uniformly random. Then, the submatrices and are totally invertible with probability .
An attempt via Schwartz-Zippel. Let be the set of th roots of unity contained in a field . Select a set and a set of distinct th roots of unity . Let be the determinant of the order- submatrix of the Vandermonde matrix obtained from the rows in and the columns in .
Notice that in the -variable polynomial is . It can be shown that the number of zeros of is at most . Consequently, if the elements of are selected uniformly at random from all size- subsets, the probability that will be at most where .
For our coding theory problem, is at most the number of data disks, . Set , and let be a random subset of size . Let . The probability that some submatrix of is singular is no more than
This probability is at most . It will be at most if . Not great, but as Don Knuth said, a bound is a bound.