Vandermonde Determinant/Proof 4

Theorem

The Vandermonde determinant of order $n$ is the determinant defined as follows:

$V_n = \begin {vmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n - 2} & x_1^{n - 1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n - 2} & x_2^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n - 2} & x_n^{n - 1} \end {vmatrix}$

Its value is given by:

$\displaystyle V_n = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}$

Proof

Let:

$V_n = \begin{vmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n - 2} & x_1^{n - 1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n - 2} & x_2^{n - 1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n - 2} & x_n^{n - 1} \end{vmatrix}$

Let $\map f x$ be any monic polynomial of degree $n - 1$:

$\ds \map f x = x^{n - 1} + \sum_{i \mathop = 0}^{n - 2} a_i x^i$

Apply elementary column operations to $V_n$ repeatedly to show:

$V_n = W$

where:

$W = \begin{vmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n - 2} & \map f {x_1} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n - 2} & \map f {x_2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^{n - 2} & \map f {x_n} \end{vmatrix}$

Select a specific degree $n - 1$ monic polynomial:

$\ds \map f x = \prod_{k \mathop = 1}^{n - 1} \paren {x - x_k}$

The selected polynomial is zero at all values $x_1, \ldots, x_{n - 1}$.

Then the last column of $W$ is all zeros except the entry $\map f {x_n}$.

Expand $\map \det W$ by cofactors along the last column to prove:

 $\text {(1)}: \quad$ $\ds V_n$ $=$ $\ds \map f {x_n} V_{n - 1}$ Expansion Theorem for Determinants for columns $\ds$ $=$ $\ds V_{n - 1} \prod_{k \mathop = 1}^{n - 1} \paren {x_n - x_k}$

For $n \ge 2$, let $\map P n$ be the statement:

$\ds V_n = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}$

Mathematical induction will be applied.

Basis for the Induction

By definition, determinant $V_1 = 1$.

To prove $\map P 2$ is true, use equation $(1)$ with $n = 2$:

$V_2 = \paren {x_2 - x_1} V_1$

This is the basis for the induction.

Induction Step

This is the induction step:

Let $\map P n$ is be assumed true.

We are to prove that $\map P {n + 1}$ is true.

As follows:

 $\ds V_{n + 1}$ $=$ $\ds V_n \prod_{k \mathop = 1}^n \paren {x_{n + 1} - x_k}$ from $(1)$, setting $n \to n + 1$ $\ds$ $=$ $\ds \prod_{1 \mathop \le m \mathop < k \mathop \le n} \paren {x_k - x_m} \prod_{k \mathop = 1}^n \paren {x_{n + 1} - x_k}$ Induction hypothesis with new indexing symbols: $i \to m, j \to k$ $\ds$ $=$ $\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n + 1} \paren {x_j - x_i}$ simplifying

Thus $\map P {n + 1}$ has been shown to be true.

The induction is complete.

$\blacksquare$