# Vandermonde Determinant

This is an exercise from Ian Stewart's Galois Theory, $3^{rd}$ edition:

If $z_1,z_2,\ldots,z_n$ are distinct complex numbers, show that the determinant $$D=\left|\begin{array}[cccc] 11&1&\cdots&1\\ z_1&z_2&\cdots&z_n\\ z_1^2&z_2^2&\cdots&z_n^2\\ \vdots&\vdots&\ddots&\vdots\\ z_1^{n-1}&z_2^{n-1}&\cdots&z_n^{n-1} \end{array}\right|$$ is nonzero.

Hint: Consider the $z_j$ as independent indeterminates over $\Bbb C$. Then $D$ is a polynomial in the $z_j$, of total degree $0+1+\cdots+(n-1)=\frac{1}{2}n(n-1)$. Moreover, $D$ vanishes whenever $z_j=z_k$ for $k\neq j$, as it then has two identical rows. Therefore $D$ is divisible by $z_j-z_k$ for all $j\neq k$, hence it is divisible by $\prod_{j<k}(z_j-z_k)$. Now compare degrees.

My question is how to do this. I follow the hint and I'm thinking of $D$ as a cofactor expansion; is that the idea? Also, the fact that $D$ vanishes whenever $z_j=z_k$ for $k\neq j$ follows since it would have two identical columns, right? I don't see why $z_j=z_k$ would imply it has two identical rows, as the hint suggests. The fact that it is divisible by $(z_j-z_k)$ is easy since that would make $z_k$ a root for $k=j$, but I'm not quite sure I follow why the degrees would be different. I think the degree of the product would be $1+2+\cdots+(k-1)$, but then add these up for all $k<n$?

I appreciate any clarification that you can provide!

-

The hint that Stewart is proving is basically asking you to prove that the Vandermonde determinant above is a scalar multiple of $$\prod_{1 \leq j < k \leq n } (z_k - z_j).$$

Once you have done this, there is no way for the product to be zero as that would mean that some $z_k = z_j$, contradicting the fact that all your complex numbers were distinct to start out with.

More on Stewart's hint: Can you see why the determinant above is a homogeneous polynomial in the variables $z_1,\ldots,z_n$ of degree $1 + 2 + \ldots + (n-1) =\frac{n(n-1)}{2}$? Once you see why it will suffice to add up the degrees of the terms along the main diagonal. Now suppose the Vandermonde determinant above is divisible by the product $\prod_{1 \leq j < k} (z_k - z_j)$.

Then if the degree of the Vandermonde determinant is equal to the degree of that product above, your problem is done by the division algorithm. Now what is the degree of the polynomial $\prod_{1 \leq j < k \leq n } (z_k - z_j)$?

The degree of that polynomial is the number of factors in the product. The number of factors is precisely the number of ways to choose two things from $n$ things without repeats (that's what the $j < k$ condition is saying). This is precisely $$\binom{n}{2} = \frac{n!}{(n-2)!2!} = \frac{n(n-1)}{2}.$$

If you're not entirely convinced of Stewart's approach above here is a proof by induction. Replace all your $z_n's$ above with $x_n's$ (sorry about this). Set $V_n$ to be equal to the $n \times n$ Vandermonde determinant above. We claim that the determinant of the $n \times n$ matrix is given by $$\text{det}(V_n) = \prod_{1\leq i < j \leq n} (x_j - x_i).$$ We prove by induction: the basis step for $n=2$ is easy enough. So suppose the formula for det$(V_n)$ in terms of a product above holds for $n=k$. Then for $n=k+1$, we perform column operations (and later, row operations) to get

$$\begin{array}{ccccc} \text{det} (V_{k+1}) &=& \text{det} \left[ \begin{array}{ccccc} 1& x_1 & x_1^2& \ldots& x_1^{k} \\ 1 &x_2 & x_2^2 & \ldots& x_2^{k} \\ \vdots &&&& \vdots \\ 1&x_{k+1} & x_{k+1}^2 &\ldots &x_{k+1}^{k} \end{array} \right] \\&=& \text{det}\left[ \begin{array}{ccccc} 1& 0 & 0& \ldots& 0\\ 1 &x_2 - x_1 & x_2(x_2 - x_1) & \ldots& x_2^{k-1}(x_2 - x_1) \\ \vdots &&&& \vdots \\ 1&x_{k+1} - x_1& x_{k+1}(x_{k+1} - x_1) &\ldots &x_{k+1}^{k-1}(x_{k+1} - x_1) \end{array} \right] \\ \\ &=& \prod_{i=2}^{k+1}(x_i - x_1) \text{det} \left[ \begin{array}{ccccc} 1& 0 & 0& \ldots& 0\\ 1 &1 & x_2 & \ldots& x_2^{k-1} \\ \vdots &&& \vdots \\ 1&1& x_{k+1} &\ldots &x_{k+1}^{k-1} \end{array} \right] \\ \\ &=& \Bigg[ \prod_{i=2}^{k+1}(x_i - x_1) \Bigg] \prod_{2 \leq i<j \leq k+1} (x_j -x_i) \quad (\text{ induction hypothesis}) \\ \\ &=& \prod_{1 \leq i<j \leq k+1} (x_j - x_i). \end{array}$$

-
This is what I was thinking; the degree of that product is precisely the same as the calculation above, right? This would imply it is completely factored, and so we're multiplying a bunch of nonzero things, thus the product is nonzero. Also, what are your thoughts about the identical columns/rows part? –  Clayton Jan 10 '13 at 15:58
@Clayton Your first sentence: Yes that is correct. Your second sentence: That is correct too that is explained in the first part of my answer. Your last sentence: If $z_1 = z_2$ say than the determinant has two identical columns which is enough to make it vanish. Recall that the determinant is non-zero iff the columns are linearly independent. I'm not so sure what the hint meant by identical rows. Presumably Stewart meant identical columns. –  fpqc Jan 10 '13 at 16:03
Thanks! You put much more formally than I could what I had in my head (as you can tell from the poor exposition of the question), and I couldn't figure out why Stewart had rows instead of columns, so I thought I was thinking about something incorrectly. –  Clayton Jan 10 '13 at 16:06
@Clayton Thanks for the kind words in your comment and thanks for accepting my answer. I have added an explanation as to why the degree of the product is equal to $\binom{n}{2}$. –  fpqc Jan 10 '13 at 16:08

Consider the cofactor matrix, call it $C$. Each column of this matrix is orthogonal to each "outer column" of the matrix $V$, the Vandermonde matrix. By "outer column" I mean every column except for the column of same index. This is easily seen since the cofactor matrix is the scale and transpose of the inverse.

Let $\mathbf{v}_i$ denote the $i$th column in $V$ and $\mathbf{c}_k$ denote the $k$th column in the cofactor matrix. From the definition of the cofactor matrix we have

$$\mathbf{v_i}^\top\mathbf{c_k} = \cases{0 \quad &for k \ne i \\ \det(V) & for k=i} \tag{1}$$

Consider them as polynomials in variable $x$, $$p_i(x) = C_{0k} +C_{1k}z + C_{2k}z^2 + \dots$$ From (1) we know it has factors $(x - z_k)$ for all $k \ne i$, or equivalently it has one factor

$$\prod_{k\ne i}(x-z_k)$$

Thus, using a scale factor $\Delta$, we may write it as $$p_i(x) = \Delta\prod_{k\ne i}(x-z_k)$$ We also know from (1) that $$p_i(z_i) = \det(V)$$ so $$p_i(z_i) = \det(V) =\Delta\prod_{k\ne i}(z_i - z_k)$$

This is sufficient to show the determinant becomes zero if $z_i = z_k$ for $k \ne i$. If you further solve for $\Delta$ you will find a very familiar formula if you have ever looked at polynomial interpolation...

-