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

Given an $n \times n$ vandermonde matrix $V$ which is invertible, is any $(n-1) \times (n-1)$ submatrix of $V$ invertible also? I think the answer is yes, but I don't know how to prove.

share|improve this question
add comment

4 Answers

up vote 15 down vote accepted

This is an elaboration of Thierry's answer: If $0 \leq a_0 < a_1 < \cdots < a_{d-1}$ is any sequence of nonnegative integers, then the determinant $\det \left( x_j^{a_i} \right)$ is equal to $\prod_{i < j}(x_i - x_j) \cdot s_{\lambda}(x_1, \ldots, x_d)$ where $\lambda = (a_0, a_1-1, a_2-2, \ldots, a_{d-1} - (d-1))$ and $s_{\lambda}$ is the Schur function. (Wikipedia takes this as the definition of Schur functions.)

In your case, you want $(a_0, a_1, \ldots, a_d)$ to be $(0,1,2,3,\ldots, d-k-1, d-k+1, d-k+2, \ldots, d)$. The corresponding partition $\lambda$ is $(0,0,0,\ldots, 1,1,\ldots, 1)$ where there are $k$ ones. This Schur function is the elementary symmetric function $$e_k(x) := \sum_{i_1 < i_2 < \cdots < i_k} x_{i_1} x_{i_2} \cdots x_{i_k},$$ which is apparently also known as a Veite sum.

So your minor vanishes precisely when there is a repeated column, or when $e_k$ is $0$.

share|improve this answer
    
Nice, I did not know there was this nice generalization. By the way, I'm not sure where the term Viète sum comes from, I'm pretty sure I learned it under a different name. –  Thierry Zell Apr 7 '11 at 19:38
    
What's the meaning of $\epsilon_k(x)$? –  Tiebin Mi Apr 8 '11 at 2:46
    
Here $e_k$ is $\pm$ the coefficient of $t^{n-1-k}$ in $\prod_1^{n-1}(t-x_j).$ –  Aaron Meyerowitz Apr 8 '11 at 8:49
add comment

Well, you're almost right... Such a determinant is sometimes known as "lacunary vandermonde" determinant, although my internet searches have not given much. Lemma 4 in this paper states that the lacunary vandermonde determinant of variables $(x_1, \dots, x_n)$ missing the terms in $x_i^k$ is obtained by a product of the regular vandermonde of $(x_1, \dots, x_n)$ times a Viete sum.

You can work out for yourself how to prove this: it's not very difficult, but it's a good exercise. The point though is that, since you assumed your vandermonde was invertible, your lacunary determinant vanishes iff the Viete sum is zero. So there is a hypersurface of possible values for $(x_1, \dots, x_n)$ that cancel your lacunary determinant.

share|improve this answer
    
Your link to "Viete sum" does not seem to work. –  Roland Bacher Apr 7 '11 at 15:48
    
@Roland: fixed, thanks. I should have double-checked when I posted it; Wikipedia titles with funny (here, accented) characters often seem to trip up MO when copy-pasted. –  Thierry Zell Apr 7 '11 at 16:54
add comment

No. Take $n=2$ and $\alpha_1=0, \alpha_2=1$. Then the Vandermonde matrix \[ \begin{bmatrix} 1 & 0 \\\ 1 & 1 \end{bmatrix} \] is invertible, but the upper-right submatrix is not.

share|improve this answer
2  
Or $$ \begin{bmatrix} 1 & 1 & 4 \\ 1 & -1 & 2 \\ 1 & 1 & 1 \end{bmatrix} $$ –  Nick S Apr 7 '11 at 21:49
add comment

Recognizing the functions $e_k$ in David's excellent elaboration of Thierry's answer leads to a simple (equivalent) description and a proof for the problem considered here (but probably not the more general one of $n-1$ arbitrary powers.)

Consider the Vandermonde matrix $$V= \begin{bmatrix} 1 & 1 & 1 & \ldots & 1 & 1 \\ x_1 & x_2 & x_3 & \ldots & x_{n-1} & t \\ x_1^2 & x_2^2 & x_3^2 & \ldots & x_{n-1}^2 &t^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_1^{n-1} & x_2^{n-1} & x_3^{n-1} & \ldots & x_{n-1}^{n-1} & t^{n-1} \end{bmatrix}$$

Claim: The minor obtained from removing the row and column of $t^{n-1-k}$ is non-invertible exactly when the $x_i$ are the $n-1$ (distinct) roots of a polynomial $$a_0t^{n-1}+a_1t^{n-2}+\cdots+a_{n-2}t+a_{n-1}$$ with $a_k=0.$


Sketch: Think of $t$ as a variable and the various $x_j$ as parameters. The determinant is a sum of $n!$ terms each with total degree $\frac{n^2-n}{2}$ in $t$ and the $x_j$. It is also a polynomial $f(t)$ with coefficients polynomals in the $x_i$. This determinant is zero if any two of the columns are equal. Hence $f(t)$ is identically zero if any two $x_i$ are equal so $$f(t)=g(t)\prod_{0<i<j<n}(x_j-x_i)$$ Where $g(t)=e_0t^{n-1}+e_1t^{n-2}+\cdots+e_{n-2}t+e_{n-1}$ and $e_k$ has degree $k$ in the $x_j.$

Observe that

  • The determinant of the minor obtained by deleting the row and column of $t^{n-1-k}$ from $V\ $ is ${\displaystyle e_k \prod_{0<i<j<n}(x_j-x_i)}$
  • $g(t)$ is zero when $t=x_j$ so $g(t)=\prod_{0<j<n}(t-x_j)$

    Put this together to establish the claim. We also see that $$e_k(x_1,\cdots,x_{n-1}) = \sum_{0<i_1 < i_2 < \cdots < i_k<n} x_{i_1} x_{i_2} \cdots x_{i_k}.$$ (I've ignored the possible need for $\pm$ depending on the parity and order of the columns.)


Other notes:

  • That expression $$e_k(x_1,\cdots,x_{n-1}) := \sum_{0<i_1 < i_2 < \cdots < i_k<n} x_{i_1} x_{i_2} \cdots x_{i_k}$$ is linear in each parameter. Thus it is generally possible to choose values for any $n-2$ of the $x_j,$ along with a minor which should have determinant $0,$ and then solve uniquely for the value of remaining parameter. (I say generally because there are particular initial choices which force the minor to be singular or non-singular independent of the final value. Then a pertubation, however small, of any one chosen value restores the unique solution for the final value.)

It is worth looking at the three cases of the last row, the first row, and the other rows.

  • It seems that $e_0$ would be the zero function. But one should require $k>0$ as $k=0$ corresponds to the minor which eliminates the last row. Then what remains is also a Vandermonde matrix and hence non-singular. In the polynomial form of the claim we see that there can't be enough distinct roots.

  • The fact that $e_{n-1} = x_1x_2x_3\cdots x_{n-1}$ corresponds to the generalization of Barts answer: If some $x_i=0$ and the minor eliminates the first row, we end up with an all zero column and a singular minor. Otherwise we can factor out $x_i \ne 0$ from each column and what remains is again a Vandermonde matrix and nonsingular.

  • If the minor eliminates neither the first nor the last row, then we can set the parameters to be $x_j=\exp(\frac{2\pi i j}{n-1}),$ the $n-1^{\mbox{st}}$ roots of unity, and have a singular minor since the first and last rows are identical (all 1's). For the problem considered here, this is the only way (up to scaling) to have a repeated row. Also, this is not a different case than $e_k=0$ since we just have the roots of $t^{n-1}-1.$

That easy example is unavailable if we restrict to entries from $\mathbb{R}$ and $n>3.$ Then it is especially fortunate to have the description in terms of the $e_k.$

share|improve this answer
    
Is the determinant of $V$ a sum of $n!$ terms each with total degree $\frac{n^2−n}{2}$ in $t$ and the $x_j$? –  Tiebin Mi Apr 9 '11 at 4:17
    
Thanks, I fixed it along with several other minor inanities (row instead of column, $n-k$ instead of $n-k-1$ etc.) –  Aaron Meyerowitz Apr 9 '11 at 6:31
add comment

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.