Vandermonde Determinant/Proof 4

From ProofWiki
Jump to navigation Jump to search

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$