Vandermonde Submatrices and Arithmetic Progressions

[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-p Vandermonde matrix over a finite extension of GF(2) are invertible where p 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 AP_k denote an arithmetic progression of length $latek k$. Let [N] := \{1, 2, \cdots, N\} for N \in \mathbb{N}.

The Szemerédi theorem says, any “sufficiently dense” subset S \subset [N] contains infinitely many AP_k for all k \in \mathbb{N}. A finitary version says: Fix your favourite k \in \mathbb{N}, \delta \in [0, 1]. Then,  there exists a natural N := N_{k, \delta} such that if you look any subset S \subset [N] of size at least \delta N, you will find an AP_k. Yet another version says:

Szemerédi’s Theorem. The size of the largest subset S \subset [N] without an AP_k cannot be too large; in particular, it is o(N).

Recall that a function f(x) is o(g) if it grows too slow compared to g(x), so that \lim_{N\rightarrow \infty}{f(x)/g(x) = 0}.

Recall that the (r,c) entry of an order-p Vandermonde matrix V^\prime is just w_p^{(r-1) (c-1)} where \omega_p is a principal pth root of unity in the field \mathbb{F}. This means, the rth row of V^\prime is

x(r) = (1, \omega_p^{(r-1)}, \omega_p^{2(r-1)}, \cdots, \omega_p^{(p-1)(r-1)}) ,

and the cth column is

y(c) = (1, \omega_p^{(c-1)}, \omega_p^{2(c-1)}, \cdots, \omega_p^{(p-1)(c-1)})^T .

We can generalize the row vector x(r) as x(r;a, d) for some integers a\geq 0, d \geq 1 where

x(r; a)_i := \omega_p^{a + (i-1)d} so that

x(r) := x(r; 0,1).

Now, let S = \{s_1, \cdots, s_k\} \in [p] be a set of arbitrary distinct nongenative integers. For some positive integer d, we can build a generalized Vandermonde matrix V := V(S, d) as follows. The (r, t)th entry of V would be

\omega_p^{s_r + (t-1) d}

so that the rth row becomes

x(r; s_r, d) = (\omega_p^{s_r}, \omega_p^{s_r+d(r-1)}, \omega_p^{s_r+2d(r-1)}, \cdots, \omega_p^{s_r+(p-1)d(r-1)}) ,

and the tth column of V has the form

v(t) := (\omega_p^{s_1+(t-1)d}, \omega_p^{s_2+(t-1)d}, \cdots, \omega_p^{s_k+(t-1)d})^{\text{T}}

Since the exponents of \omega_p along any row of V form an arithmetic progression, it is easy to see that V is invertible. (Why? When computing the determinant, we can factor out \omega_p^{a_r} from the rth row for r \in [k], leaving a Vandermonde matrix of order k generated by \omega_p^d. This matrix is non singular since \omega_p^d is also a pth root of unity.)

Let A be the set of column-indices of V above, and recall that this is an arithmetic progression in [p]. What can we say about A?

Let W be a proper subspace of \mathbb{F}^k so that dim(W) < k. Suppose A = \{t \in Z_p \mid v(t) \in W\}. By our observation above, A cannot contain an arithmetic progression of length k, because otherwise, the matrix V(A) would be invertible and its columns \{v(t) : t \in A\} would span \mathbb{F}^k; since v(t) \in W by assumption, it would imply dim(V) = k, a contradiction.

This leads us to the following observation.

Observation: If A \subset [p] contains an arithmetic progression of length k, then

dim\  span\  \cup _{t \in A} v(t) \geq k.

Now let us ask the following question.

Question: Let W be an arbitrary strict subspace of \mathbb{F}^k. If we pick a t \in \mathbb{Z}_p at random, what is the probability that v(t) \in W?

Suppose there is a set A \in \mathbb{Z}_p such that the vectors span\{v(a) \mid a\in A \} = span(W). Since W is a strict subspace of \mathbb{F}^k, A does not contain an arithmetic progression of length k, and \vert A \vert = o_k(p) by Szemeredi’s theorem. The probability that v(t) \in W equals the probability that t \in A, which is \vert A \vert / p = o(1), which tends to zero as p goes to infinity.

Lemma (Due to Alex Russell). Let W be an arbitrary strict subspace of \mathbb{F}^k. If we pick a t \in \mathbb{Z}_p at random,

\displaystyle \Pr_{t \sim \mathbb{Z}_p}[ v(t) \in W ] = o_k(p)/p = o_k(1)

as p 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 p be a prime and V be an order-p Vandermonde matrix over the field \mathbb{F} containing a principal pth root of unity. Let V_{R,C} be the submatrix of V indexed by the rows in R and columns in C.

Theorem A (Due to Alex Russell).  Let k < p a constant.  Select two size-k subsets R, A \subset \mathbb{Z}_p where R is arbitrary and A is uniformly random. The probability that the submatrix V_{R,A}  is invertible is 1 - o_k(1), i.e., the probability tends to one as p goes to infinity.

The outline of the proof is as follows. We select k distinct random integers one by one and add it to a set A which is initially empty. At any time, let W = span \cup_{a \in A} v(a). Everytime we pick a random t \in \mathbb{Z}_p, we invoke the lemma above to show that \Pr[v(t) \in W] \leq (k + o(p))/p = o(1) as p goes to infinity. We repeat this for k times. Because the samples are independent, the probability that some t (out of the k samples) is bad is at most k o_k(1). If this happens, we say that the subset C is bad. Otherwise, dim(W) = k and we got ourselves an invertible k\times k-submatrix V_{R,A} given by the columns \{v(a)\} for all a\in A.

A Chebotarev-like Statement.  Suppose the field \mathbb{F} contains all pth roots of unity, let V be the corresponding Vandermonde matrix. A matrix is totally invertible if every submatrix is invertible. Chebotarev’s thoerem states that the matrix  V 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 D is an arbitrary subset of \mathbf{Z}_p of a constant size. Similarly, let S be a uniformly random subset of \mathbb{Z}_p of a constant size. Let k^\prime = \min{(\vert D \vert, \vert A \vert)}. Let V^\prime := V_{D, S}.

The probability that some order-k submatrix of V^\prime is singular is no more than

\displaystyle \sum_{2\leq k \leq k^\prime}{ {\vert S \vert \choose k} {\vert D \vert \choose k} k o(1)}.

This probability is o(1) as long as the sets S, D have constant sizes. Also notice that the same argument holds if we use the transpose V^{\text{T}} for V. This leads us to the following corollary.

Corollary. Fix k \in [p]. Select two constant-size subsets D, S \subset \mathbb{Z}_p where D is arbitrary and S is uniformly random. Then, the submatrices V_{S,D} and V_{D,S} are totally invertible with probability 1- o(1).

An attempt via Schwartz-Zippel. Let M be the set of pth roots of unity contained in a field \mathbb{F}. Select a set T = \{t_1, \cdots, t_k\} \subset \mathbb{Z}_p and a set of k distinct pth roots of unity X = \{x_1, \cdots, x_k\}. Let q(X) := det(V_{T, X}) be the determinant of the order-k submatrix V_{T,X} of the Vandermonde matrix V := (\omega_p^{ij})_{i,j\in \mathbb{Z}_p} obtained from the rows in T and the columns in X.

Notice that deg(x_j) in the k-variable polynomial q(X) is t_j. It can be shown that the number of zeros of q(X) is at most \sum_j{t_j}p^{k-1}. Consequently, if the elements of X \subset M are selected uniformly at random from all size-k subsets, the probability that q(X) = 0 will be at most kd/p where d = \max_j{t_j}.

For our coding theory problem, k is at most the number of data disks, d. Set T = \{0, \cdots, d-1\}, and let X \subset M be a random subset of size d. Let V^\prime := V_{T, X}. The probability that some submatrix of V^\prime is singular is no more than

\displaystyle \sum_{2 \leq k \leq d}{ {d \choose k}^2 kd/p }.

This probability is at most {2d \choose d}d^2/p \approx 2^{2d}d^2/p\sqrt{\pi d}. It will be at most 1/2 if p \geq 2^{2d}d^{3/2}. Not great, but as Don Knuth said, a bound is a bound.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s