33
$\begingroup$

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)

How I did it

$\endgroup$
3
  • 5
    $\begingroup$ There's a nice non-inductive proof. Would that work for you? $\endgroup$ Commented Oct 14, 2013 at 2:38
  • $\begingroup$ Actually, my memory tricked me. There is an induction. I'm posting it below. $\endgroup$ Commented Oct 14, 2013 at 2:52
  • 1
    $\begingroup$ ProofWiki has two proofs using mathematical induction. $\endgroup$
    – user1551
    Commented Oct 14, 2013 at 6:42

3 Answers 3

60
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you please explain how it is possible to factor out $a_i - a_1$? $\endgroup$ Commented Sep 2, 2015 at 10:05
  • 3
    $\begingroup$ $a_j^{i} - a_1 a_j^{i-1} = a_j^{i-1}(a_j - a_1)$ $\endgroup$
    – D_S
    Commented Oct 1, 2015 at 4:59
  • 5
    $\begingroup$ 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). $\endgroup$ Commented Dec 3, 2018 at 10:17
18
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Sexy! I should read this book if it has more fancy tricks like that. $\endgroup$ Commented Dec 24, 2013 at 15:06
  • 3
    $\begingroup$ 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$. $\endgroup$ Commented Dec 3, 2018 at 10:10
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Would you explain what is 'restriction of $f$ to the subspace $K[X]_{<n}$ and why you mention this concept? Where is lower-triangularity coming from in the last paragraph and why does it mean that $x_{i}$ is a root of $P_{j-1}$'? BTW, I came across several answers from you, learnt a lot. May I suggest that could you elaborate more on math symbol and better with explicit examples. I believe you will get much more upvote for your excellent answers. Thanks for your time! @MarcvanLeeuwen $\endgroup$
    – Kuo
    Commented Oct 21, 2022 at 18:23
  • $\begingroup$ or maybe a reference link? $\endgroup$
    – Kuo
    Commented Oct 21, 2022 at 18:28
  • $\begingroup$ @Kuo: $f:K[X]\to K^n$ has as domain the infinite dimensional space of all polynomials; one cannot establish a finite matrix to describe it entirely. But we only need the images of the first $n$ basis vectors here, which describe the restriction of $f$ to the subspace they generate, which is $K[X]_{<n}$. Now we can form a matrix, with respect to those first $n$ basis vectors at departure, and the canonical basis of $K^n$ at arrival, and this matrix happens to be $V_n$. So if one wants to understand the determinant of $V_n$, it is the restriction of $f$ to $K[X]_{<n}$ that can be useful. $\endgroup$ Commented Oct 23, 2022 at 11:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .