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<j\leq n}(x_j-x_i)$$ (but again, explicitly by induction)

Solution 1:

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.

Solution 2:

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.

Solution 3:

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 following. 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]_{<n}}\Kxn$ 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<j$. 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<j\leq n}(x_j-x_i)$.