Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
Thank you for your suggestions. I'm interested in the case k<n, but where the column spaces of the subsets have in general nontrivial intersection and the subsets can be overlapping. Do your suggestions apply in this case? –  thcp Mar 26 '12 at 22:46
    
No. It doesn't work for overlapping set of indices. –  mmaann Mar 28 '12 at 17:43
    
Restricted orthonormality seems unlikely to help over finite fields, but the spark seems like it should be very helpful. –  Will Sawin Jul 6 '12 at 16:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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