Value of Vandermonde Determinant/Formulation 1/Proof 4

Theorem

Let $V_n$ be the Vandermonde determinant of order $n$ defined as the following formulation:

$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:

$\ds 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$