# Vandermonde determinant by induction

For $$n$$ variables $$x_1,\ldots,x_n$$, the determinant $$\det\left((x_i^{j-1})_{i,j=1}^n\right) = \left|\begin{matrix} 1&x_1&x_1^2&\cdots & x_1^{n-1}\\ 1&x_2&x_2^2&\cdots & x_2^{n-1} \\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_{n-1}&x_{n-1}^2&\cdots&x_{n-1}^{n-1}\\ 1 &x_n&x_n^2&\cdots&x_n^{n-1} \end{matrix}\right|$$ can be computed by induction; the image below says it shows that. I have done this before, if I submit this will I get marks?

MORE IMPORTANTLY how do I do it by induction? The "hint" is to get the first row to $$(1,0,0,...,0)$$.

I think there are the grounds of induction in there, but I'm not sure how (I'm not very confident with induction when the structure isn't shown for $$n=k$$, assume for $$n=r$$, show if $$n=r$$ then $$n=r+1$$ is true.

By the way the question is to show the determinant at the start equals the product $$\prod_{1\leq i (but again, explicitly by induction) • There's a nice non-inductive proof. Would that work for you? – Bruno Joyal Oct 14 '13 at 2:38
• Actually, my memory tricked me. There is an induction. I'm posting it below. – Bruno Joyal Oct 14 '13 at 2:52
• ProofWiki has two proofs using mathematical induction. – user1551 Oct 14 '13 at 6:42

## 3 Answers

You're facing the matrix

\begin{pmatrix} 1&1&\cdots & 1 &1\\a_1&a_2&\cdots &a_n&a_{n+1}\\\vdots&\vdots&\ddots&\vdots&\vdots\\a_1^{n-1}&a_2^{n-1}&\cdots&a_n^{n-1}& a_{n+1}^{n-1}\\a_1^{n}&a_2^{n}&\cdots&a_n^{n}&a_{n+1}^{n}\end{pmatrix}

By subtracting $a_1$ times the $i$-th row to the $i+1$-th row, you get

\begin{pmatrix} 1&1&\cdots & 1 &1\\ 0&a_2-a_1&\cdots &a_n-a_1&a_{n+1}-a_1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&a_2^{n}-a_1a_{2}^{n-1}&\cdots&a_n^n-a_1a_{n}^{n-1}& a_{n+1}^{n}-a_1a_{n+1}^{n-1}\end{pmatrix}

Expanding by the first column and factoring $a_i-a_1$ from the $i$-th column for $i=2,\ldots,n+1$, you get the determinant is

$$=\prod_{j=2}^{n+1}(a_j-a_1) \det\begin{pmatrix} 1& 1&\cdots&1\\a_2&a_3&\cdots&a_{n+1}\\ \vdots&\vdots&\ddots&\vdots\\a_2^{n-1}&a_3^{n-1}&\cdots&a_{n+1}^{n-1}\end{pmatrix}$$

You may apply your inductive hypothesis, to get this is $$=\prod_{j=2}^{n+1}(a_j-a_1) \prod_{2\leqslant i<j\leqslant n+1}(a_j-a_i)=\prod_{1\leqslant i<j\leqslant n+1}(a_j-a_i)$$ and the inductive step is complete.

• Can you please explain how it is possible to factor out $a_i - a_1$? – john.abraham Sep 2 '15 at 10:05
• $a_j^{i} - a_1 a_j^{i-1} = a_j^{i-1}(a_j - a_1)$ – D_S Oct 1 '15 at 4:59
• Even though it is clearly stated, gratuitous change of notation with respect to the question (transposing the matrix and renaming the $x_i$ to $a_i$) is not really helpful, especially in the presence of another answer that does keep the original notation (but uses $a_i$ for a different purpose). – Marc van Leeuwen Dec 3 '18 at 10:17

Let $f(T) = T^{n-1} + a_1 T^{n-2} + \dots + a_{n-1}$ be the polynomial $(T-x_2)(T-x_3)\dots (T-x_n)$. By adding to the rightmost column an appropriate linear combination of the other columns (namely the combination with coefficients $a_1, \dots, a_{n-1}$), we can make sure that the last column is replaced by the vector $(f(x_1), 0, 0, \dots, 0)$, since by construction $f(x_2) = \dots = f(x_n) =0$. Of course this doesn't change the determinant. The determinant is therefore equal to $f(x_1)$ times $D$, where $D$ is the determinant of the $(n-1) \times (n-1)$ matrix which is obtained from the original one by deleting the first row and the last column. Then, we apply the induction hypothesis, using the fact that $f(x_1) = (x_1 - x_2)(x_1-x_3) \dots (x_1-x_n)$. And we are done!

By the way, this matrix is known as a Vandermonde matrix.

I learned this trick many years ago in Marcus' Number fields.

• Sexy! I should read this book if it has more fancy tricks like that. – Patrick Da Silva Dec 24 '13 at 15:06
• You get the wrong product (it should have factors $x_j-x_i$ when $i<j$, rather than factors $x_i-x_j$, or else you should throw in a sign $(-1)^{\binom n2}$ for the Vandermonde determinant). The explanation is that you produce a factor $f(x_1)$ that is not on the main diagonal, and this means in the induction step you get a sign $(-1)^{n-1}$ in the development of the determinant. This sign could have been avoided by producing a nonzero coefficient in the last entry of the final column instead, using a monic polynomial of degree $n-1$ with roots at $x_1,\ldots,x_{n-1}$ but not at $x_n$. – Marc van Leeuwen Dec 3 '18 at 10:10

Although this does not really answer the question (in particular, I cannot tell whether you whether submitting the image will give you any marks), it does explain the evaluation of the determinant (and one can get an inductive proof from it if one really insists, though it would be rather similar to the answer by Bruno Joyal).

The most natural setting in which the Vandermonde matrix $$V_n$$ arises is the followig. Evaluating a polynomial over$$~K$$ in each of the points $$x_1,\ldots,x_n$$ of $$K$$ gives rise to a linear map $$K[X]\to K^n$$ i.e., the map $$f:P\mapsto (P[x_1],P[x_2],\ldots,P[x_n])$$ (here $$P[a]$$ denotes the result of substituting $$X:=a$$ into$$~P$$). Then $$V_n$$ is the matrix of the restriction of $$f$$ to the subspace $$\def\Kxn{K[X]_{ of polynomials of degree less than$$~n$$, relative to the basis $$[1,X,X^2,\ldots,X^{n-1}]$$ of that subspace. Any family $$[P_0,P_1,\ldots,P_{n-1}]$$ of polynomials in which $$P_i$$ is monic of degree$$~i$$ for $$i=0,1,\ldots,n-1$$ is also a basis of$$~\Kxn$$, and moreover the change of basis matrix$$~U$$ from the basis $$[1,X,X^2,\ldots,X^{n-1}]$$ to $$[P_0,P_1,\ldots,P_{n-1}]$$ will be upper triangular with diagonal entries all$$~1$$, by the definition of being monic of degree$$~i$$. So $$\det(U)=1$$, which means that the determinant of$$~V_n$$ is the same as that of the matrix$$~M$$ expressing our linear map on the basis $$[P_0,P_1,\ldots,P_{n-1}]$$ (which matrix equals $$V_n\cdot U$$).

By choosing the new basis $$[P_0,P_1,\ldots,P_{n-1}]$$ carefully, one can arrange that the basis-changed matrix is lower triangular. Concretely column$$~j$$ of$$~M$$, which describes $$f(P_{j-1})$$ (since we number columns from$$~1$$), has as entries $$(P_{j-1}[x_1],P_{j-1}[x_2],\ldots,P_{j-1}[x_n])$$, so lower-triangularity means that $$x_i$$ is a root of $$P_{j-1}$$ whenever $$i. This can be achieved by taking for $$P_k$$ the product $$(X-x_1)\ldots(X-x_k)$$, which is monic of degree $$k$$. Now the diagonal entry in column$$~j$$ of$$~M$$ is $$P_{j-1}[x_j]=(x_j-x_1)\ldots(x_j-x_{j-1})$$, and $$\det(V_n)$$ is the product of these expressions for $$j=1,\ldots,n$$, which is $$\prod_{j=1}^n\prod_{i=1}^{j-1}(x_j-x_i)=\prod_{1\leq i.