# Proving determinant of Vandermonde matrix

Problem: A matrix of the form \begin{align*} A= \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\ \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-1} \end{pmatrix} \end{align*} is called a Vandermonde matrix. Prove that \begin{align*} \det(A) = \prod_{i > j} (x_i - x_j). \end{align*}

Proof: We prove this per induction on $n$.

Basic step. For $n=2$ we have \begin{align*} \det \begin{pmatrix} 1 & x_1 \\ 1 & x_2 \end{pmatrix} = x_2 - x_1. \end{align*} Induction step. Assume the statement holds for $n-1$. Then we now prove that it also holds for $n$. We can multiply the first row in the matrix $A$ with $-1$ and then add this to all other rows, without the determinant changing. Hence we get \begin{align*} A \sim \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ 0 & x_2 - x_1 & x_2^2 - x_1^2 & \cdots & x_2^{n-1} - x_1^{n-1} \\ \vdots \\ 0 & x_n - x_1 & x_n^2 - x_1^2 & \cdots & x_n^{n-1} - x_1^{n-1} \end{pmatrix}. \end{align*} Now we can also multiply column $(n-1)$ by $x_1$ and substract this from column $n$, without the determinant changing. The result is that the first row dissapears except for the first element: \begin{align*} A \sim \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & x_2 - x_1 & (x_2 - x_1)x_2 & \cdots & (x_2 - x_1)x_2^{n-3} & (x_2 - x_1)x_2^{n-2} \\ \vdots \\ 0 & x_n - x_1 & (x_n - x_1)x_n & \cdots & (x_n - x_1)x_n^{n-3} & (x_n-x_1)x_n^{n-2} \end{pmatrix}. \end{align*} We see that every row except the first one has a factor $(x_k - x_1)$ in common. We can factor this, but then we have to multiply the determinant with that factor. Let $\det(A) = \Gamma$. Then we get: \begin{align*} \Gamma = \prod_{k=2}^n (x_k - x_1) \det \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & x_2 & \cdots & x_2^{n-3} & x_2^{n-2} \\ \vdots \\ 0 & 1 & x_n & \cdots & x_n^{n-3} & x_n^{n-2} \end{pmatrix}. \end{align*} Now, from the fact that \begin{align*} \det \begin{pmatrix} 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} = \det \begin{pmatrix} a_{22} & \cdots & a_{2n} \\ \vdots \\ a_{n2} & \cdots & a_{nn} \end{pmatrix}, \end{align*} the above matrix can be simplified to: \begin{align*} \Gamma = \prod_{k=2}^n (x_k - x_1) \det \begin{pmatrix} 1 & x_2 & \cdots & x_2^{n-3} & x_2^{n-2} \\ \vdots \\ 1 & x_n & \cdots & x_n^{n-3} & x_n^{n-2} \end{pmatrix}. \end{align*}

But then I don't know how to continue. Anyone help please?

• You haven't used the induction hypothesis yet. – Matt Samuel Jun 23 '15 at 16:47
• Just use $i>j\geq 2$. – Matt Samuel Jun 23 '15 at 18:02
• @LebronJames I saw your question earlier, and I was thinking the easiest way I could think of to do it was to multiply it out and use a combinatorial bijection, only to find out I had already known an easier way to do it months ago! The question has never been edited, so it seems that they got that far, the hard part, by themselves. A simple application of the induction hypothesis solves it from there. I believe they have done the minimal required work. The minor has to be a Vandermonde matrix before you can apply the hypothesis. – Matt Samuel Nov 14 '15 at 4:02
• Also, if you don't kill the rest of the first row you have to do the whole alternating sum of the rest of the minors. – Matt Samuel Nov 14 '15 at 4:04
• @LebronJames oh, I'm wrong. Expanding along the column is enough, so you're right. – Matt Samuel Nov 14 '15 at 4:05