Vandermonde determinant by induction

Question

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)

Answer 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.

Answer 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.

Answer 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)$.

Answer 4

Note: This answer does not use induction. I had to post it here because the other question which didn't require induction was closed. $\DeclareMathOperator{\det}{det}\DeclareMathOperator{\sgn}{sgn}$

You have this matrix over a field $\mathbb F$.

$V(x_1,\ldots, x_{n})=\begin{pmatrix}1& x_1& x_1^2&\ldots & x_{1}^{n-1}\\ 1&x_2 & x_2^2 & \ldots & x_{2}^{n-1}\\ \vdots & \vdots &\vdots &\ddots & \vdots\\ 1& x_{n}& x_n^2 &\ldots & x_{n}^{n-1}\end{pmatrix}\tag*{}$

We are trying to determine $\det(V)\in\mathbb F[x_1, \ldots, x_{n-1}]$.

Recognize that $\det(V)$ is homogeneous and has each of its terms has a degree of $(n-1)n/2$. (Why?)

For all non-zero constant $k\in\mathbb F$, we have: $\det V(kx_1, \ldots, kx_{n-1}) \\= k^{(n-1)n/2} \cdot V(x_1,\ldots, x_{n-1})\tag*{}$ This is because we can factor out $k^{j-1}$ from each column $j$ of the determinant.

Now check that $(x_1-x_2)$ is a factor of $\det V$ using factor theorem. Substituting $x_1=x_2$ in $\det V$, the second and the third columns become identical; thus, $\det V(x_2,x_2,x_3,\ldots,x_n)=0$. We conclude that $(x_1-x_2)$ is a factor of $\det V(x_1,\ldots,x_n)$.

Similarly, we would get every $(x_i-x_j)$ is a linear factor of $V$ for all $i<j$. That accounts for $(n-1)n/2$ distinct linear factors of $V$. Also, recall: what's the degree of $V$? We have: $\displaystyle \det V = \mathcal K\cdot \prod_{1 \leq i<j\leq n}(x_i-x_j)\tag{01}$ where $\mathcal K$ is a constant from $\mathbb F$.

If you have any confusion, check that $\displaystyle \bigg|\{(i,j):1\leq i<j\leq n\}\bigg|=\binom{n}{2}=\frac{n(n-1)}{2}\tag*{}$ If we attempt to expand $\det V$ directly i.e., $\displaystyle\det V= \sum_{\sigma\ \in \ S_n} \sgn(\sigma) \cdot \left(\prod_{i=1}^n v_{i \ \sigma(i)} \right)\tag*{}$ No two permutations yield like terms. We see that there will be a term $x_2\cdot x_3^2\cdot x_4^3\cdots x_{n}^{n-1}$ (from the identity permutation). Expanding the proposed factor form in (01), we get this corresponding term: $\mathcal K \cdot x_2\cdot x_3^2\cdot x_4^3\cdots x_{n}^{n-1}\tag*{}$

Thus, it must be the case that $\mathcal K \cdot x_2\cdot x_3^2\cdot x_4^3\cdots x_{n}^{n-1}=x_2\cdot x_3^2\cdot x_4^3\cdots x_{n}^{n-1}$ whence, we get $\mathcal K=1\in\mathbb F$.

Conclusion: $\boxed{\det V = \prod_{1 \leq i<j\leq n}(x_i-x_j)}\tag*{}$