Vandermonde matrices and general position

Question

I was wondering if it is known whether a Vandermonde matrix over a sufficiently large finite field is in general position with respect to intersections of subspaces spanned by subsets of columns, i.e. whether the dimension of such intersections is as small as that of a randomly chosen matrix over a large field. To be more specific, consider a k x n matrix V. Consider any m subsets $S_1$,..., $S_m$ of the set of column indexes {1, 2,... n}. Let $W_i$ be the subspace spanned by the subset of columns with indexes in $S_i$. Let U be the intersection of the subspaces $W_1$,…,$W_m$. The question is whether the dimension of U when matrix V is restricted to be Vandermonde is as small as that when the entries of matrix V are randomly chosen over a large field.

I would be most grateful for any comments, suggestions or pointers to relevant work regarding this problem.

Answer 1

Not quite what you are asking for but I think these concepts are related. First: Is it $k\geq n$ or $k\leq n$. Are $S_i$ disjoint?. If $k < n $ There is a property called restricted orthonormality property which says that two subspaces spanned by the columns of $A$ indexed by two disjoint subsets are almost orthogonal and hence less likley to have intersection other than 0.

A matrix $A$ is said to satisfy restricted orthonormality property with constants $\theta_{s,s'}$ if $|\langle A_Sx,A_{S'}x'\rangle|\leq \theta_{s,s'}\lVert x\rVert_2\lVert x'\rVert_2$ for all disjoint sets $S,S'$ which are subsets of $\{1,2,..,n\}$ with cardinality $|S|\leq s,|S'|\leq s'$. This is saying that the two subspaces spanned by the columns of $A$ indexted by these two sets are almost orthogonal and hence they have the more chance of having smaller intersection. Also random matrices (Gaussian, Bernoulli)satisfy this property with high probability. If a submatrix is chosen randomly from large Fourier matrix it also satisfy this property. Since Vandermonde matrix has a lot of optimal properties a submatrix of V might well satisfy this. Other terms to look for: Spark of a matrix, Kruskal Rank, Restricted Isometry. Incoherence.

Answer 2

This is true when $m=2$. First throw out the columns in $S_1 \cap S_2$, which of course lie in $U$. Then count the remaining columns. The dimension of the intersectiosn between $W_1$ and $W_2$ in a random matrix is the size of $S_1$ plus the size of $S_2$ minus the dimension of the space (the space modulo the columns in $S_1 \cap S_2$). But this same formula holds true for Vandermonde matrices, because they have full spark. Because of the formula $dim (W_1) + dim (W_2) = dim (W_1 + W_2) + dim (W_1 \cap W_2)$, an increase of $dim(W_1 \cap W_2)$ implies a shortfall of $(W_1 \cup W_2)$, which means that the $k \times k$ minors are all zero, so at least one $k \times k$ minor is $0$, which never happens in a Vandermonde matrix.