Vandermonde Determinant

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


Alternative Formulations

The Vandermonde determinant is given variously in the literature. Here are some alternative ways it is sometimes seen.


Knuth

Donald E. Knuth refers to the matrix itself, and calls it Vandermonde's matrix, defining it compactly as $a_{ij} = x_j^i$.

Thus, if:

$\mathbf{V} = \begin{bmatrix} x_1 & x_2 & \cdots & x_n \\ x_1^2 & x_2^2 & \cdots & x_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ x_1^n & x_2^n & \cdots & x_n^n \end{bmatrix}$


then:

$\displaystyle \det \left({\mathbf{V}}\right) = \prod_{1 \mathop \le j \mathop \le n} x_j \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right)$


The proof follows directly from that for above and the result Determinant with Row Multiplied by Constant.


Mirsky

Mirsky gives it as:

$D = \begin{vmatrix} a_1^{n-1} & a_1^{n-2} & \cdots & a_1 & 1 \\ a_2^{n-1} & a_2^{n-2} & \cdots & a_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^{n-1} & a_n^{n-2} & \cdots & a_n & 1 \\ \end{vmatrix}$


Its value is given by:

$\displaystyle D = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({a_i - a_j}\right)$


Proof 1

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} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-2} & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-2} & x_n^{n-1} \end{vmatrix}$.


By Multiple of Row Added to Row of Determinant, we can subtract row 1 from each of the other rows and leave $V_n$ unchanged:

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


Similarly without changing the value of $V_n$, we can subtract, in order:

$x_1$ times column $n-1$ from column $n$
$x_1$ times column $n-2$ from column $n-1$

and so on, till we subtract:

$x_1$ times column $1$ from column $2$.

The first row will vanish all apart from the first element $a_{11} = 1$.

On all the other rows, we get, with new $i$ and $j$:

$a_{ij} = \left({x_i^{j-1} - x_1^{j-1}}\right) - \left({x_1 x_i^{j-2} - x_1^{j-1}}\right) = \left({x_i - x_1}\right) x_i^{j-2}$:
$V_n = \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & x_2 - x_1 & \left({x_2 - x_1}\right) x_2 & \cdots & \left({x_2 - x_1}\right) x_2^{n-3} & \left({x_2 - x_1}\right) x_2^{n-2} \\ 0 & x_3 - x_1 & \left({x_3 - x_1}\right) x_3 & \cdots & \left({x_3 - x_1}\right) x_3^{n-3} & \left({x_3 - x_1}\right) x_3^{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & x_{n-1} - x_1 & \left({x_{n-1} - x_1}\right) x_{n-1} & \cdots & \left({x_{n-1} - x_1}\right) x_{n-1}^{n-3} & \left({x_{n-1} - x_1}\right) x_{n-1}^{n-2}\\ 0 & x_n - x_1 & \left({x_n - x_1}\right) x_n & \cdots & \left({x_n - x_1}\right) x_n^{n-3} & \left({x_n - x_1}\right) x_n^{n-2} \end{vmatrix}$


For all rows apart from the first, the $k$th row has the constant factor $\left({x_k - x_1}\right)$.

So we can extract all these as factors, and from Determinant with Row Multiplied by Constant, we get:

$\displaystyle V_n = \prod_{k \mathop = 2}^n \left({x_k - x_1}\right) \begin{vmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & x_2 & \cdots & x_2^{n-3} & x_2^{n-2} \\ 0 & 1 & x_3 & \cdots & x_3^{n-3} & x_3^{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 1 & x_{n-1} & \cdots & x_{n-1}^{n-3} & x_{n-1}^{n-2}\\ 0 & 1 & x_n & \cdots & x_n^{n-3} & x_n^{n-2} \end{vmatrix}$


From Determinant with Unit Element in Otherwise Zero Row, we can see that this directly gives us:

$\displaystyle V_n = \prod_{k \mathop = 2}^n \left({x_k - x_1}\right) \begin{vmatrix} 1 & x_2 & \cdots & x_2^{n-3} & x_2^{n-2} \\ 1 & x_3 & \cdots & x_3^{n-3} & x_3^{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n-1} & \cdots & x_{n-1}^{n-3} & x_{n-1}^{n-2}\\ 1 & x_n & \cdots & x_n^{n-3} & x_n^{n-2} \end{vmatrix}$

and it can be seen that:

$\displaystyle V_n = \prod_{k \mathop = 2}^n \left({x_k - x_1}\right) V_{n-1}$


$V_2$, by the time we get to it (it will concern elements $x_{n-1}$ and $x_n$), can be calculated directly using the formula for calculating a Determinant of Order 2:

$V_2 = \begin{vmatrix} 1 & x_{n-1} \\ 1 & x_n \end{vmatrix} = x_n - x_{n-1}$


The result follows.

$\blacksquare$


Proof 2

Proof by induction:

Let the Vandermonde Determinant be presented in the form as defined by Mirsky:

Let $V_n = \begin{vmatrix} a_1^{n-1} & a_1^{n-2} & \cdots & a_1 & 1 \\ a_2^{n-1} & a_2^{n-2} & \cdots & a_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^{n-1} & a_n^{n-2} & \cdots & a_n & 1 \\ \end{vmatrix}$


For all $n \in \N_{>0}$, let $P \left({n}\right)$ be the proposition:

$\displaystyle V_n = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({a_i - a_j}\right)$


$P(1)$ is true, as this just says $\begin{vmatrix} 1 \end{vmatrix} = 1$.


Basis for the Induction

$P(2)$ holds, as it is the case:

$V_2 = \begin{vmatrix} a_1 & 1 \\ a_2 & 1 \end{vmatrix}$

which evaluates to $V_2 = a_1 - a_2$.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\displaystyle V_k = \prod_{1 \mathop \le i \mathop < j \mathop \le k} \left({a_i - a_j}\right)$


Then we need to show:

$\displaystyle V_{k+1} = \prod_{1 \mathop \le i \mathop < j \mathop \le k+1} \left({a_i - a_j}\right)$


Induction Step

This is our induction step:


Take the determinant:

$V_{k+1} = \begin{vmatrix} x^k & x^{k-1} & \cdots & x^2 & x & 1 \\ a_2^k & a_2^{k-1} & \cdots & a_2^2 & a_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{k+1}^k & a_{k+1}^{k-1} & \cdots & a_{k+1}^2 & a_{k+1} & 1 \end{vmatrix}$


Let the Expansion Theorem for Determinants‎ be used to expand $V_n$ in terms of the first row

It can be seen that it is a polynomial in $x$ whose degree is no greater than $k$.

Let that polynomial be denoted $f \left({x}\right)$.

Let any $a_r$ be substituted for $x$ in the determinant.

Then two of its rows will be the same.

From Square Matrix with Duplicate Rows has Zero Determinant, the value of such a determinant will be $0$.

Such a substitution in the determinant is equivalent to substituting $a_r$ for $x$ in $f \left({x}\right)$.

Thus it follows that:

$f \left({a_2}\right) = f \left({a_3}\right) = \ldots = f \left({a_{k+1}}\right) = 0$

So $f \left({x}\right)$ is divisible by each of the factors $x - a_2, x - a_3, \ldots, x - a_{k+1}$.

All these factors are distinct, otherwise the original determinant is zero.

So:

$f \left({x}\right) = C \left({x - a_2}\right) \left({x - a_3}\right) \cdots \left({x - a_k}\right) \left({x - a_{k+1}}\right)$

As the degree of $f \left({x}\right)$ is no greater than $k$, it follows that $C$ is independent of $x$.


From the Expansion Theorem for Determinants‎, the coefficient of $x^k$ is:

$\begin{vmatrix} a_2^{k-1} & \cdots & a_2^2 & a_2 & 1 \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ a_{k+1}^{k-1} & \cdots & a_{k+1}^2 & a_{k+1} & 1 \end{vmatrix}$.

By the induction hypothesis, this is equal to:

$\displaystyle \prod_{2 \mathop \le i \mathop < j \mathop \le k+1} \left({a_i - a_j}\right)$

This must be our value of $C$.

So we have:

$\displaystyle f \left({x}\right) = \left({x - a_2}\right) \left({x - a_3}\right) \cdots \left({x - a_k}\right) \left({x - a_{k+1}}\right) \prod_{2 \mathop \le i \mathop < j \mathop \le k+1} \left({a_i - a_j}\right)$

Substituting $a_1$ for $x$, we retrieve the proposition $P \left({k+1}\right)$.


So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle V_n = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({a_i - a_j}\right)$

$\blacksquare$


Proof 3

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} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-2} & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \\ 1 & x_n & x_n^2 & \cdots & x_n^{n-2} & x_n^{n-1} \end{vmatrix}$.


Start by replacing number $x_n$ in $V_n$ with the unknown $x$.

Thus $V_n$ is made into a function of $x$.

$P \left({x}\right) = \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} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-2} & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \\ 1 & x & x^2 & \cdots & x^{n-2} & x^{n-1} \end{vmatrix}$.

Let $x$ equal a value from the set $\set {x_1,\ldots,x_{n-1} }$.

Then determinant $\map P {x}$ has equal rows, giving:

\(\displaystyle \map P {x}\) \(=\) \(\displaystyle 0\) for $x = x_1, \ldots, x_{n-1}$

Perform row expansion by the last row.

Then $P \left({x}\right)$ is seen to be a polynomial of degree $n-1$:

$P \left({x}\right) = \begin{vmatrix} x_1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\ x_2 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\ x_3 & x_3^2 & \cdots & x_3^{n-2} & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \end{vmatrix} + \begin{vmatrix} 1 & x_1^2 & \cdots & x_1^{n-2} & x_1^{n-1} \\ 1 & x_2^2 & \cdots & x_2^{n-2} & x_2^{n-1} \\ 1 & x_3^2 & \cdots & x_3^{n-2} & x_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \end{vmatrix}x \ \ + \ \ \cdots \ \ + \ \ \begin{vmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{n-2} \\ 1 & x_2 & x_2^2 & \cdots & x_2^{n-2} \\ 1 & x_3 & x_3^2 & \cdots & x_3^{n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-2} \end{vmatrix}x^{n-1}$.

By the Polynomial Factor Theorem:

$P \left({x}\right) = C \left({x - x_1}\right) \left({x - x_2}\right) \dotsm \left({x - x_{n-1} }\right)$

where $C$ is the leading coefficient (with $x^{n-1}$ power).


Thus:

$P \left({x}\right) = V_{n-1} \left({x - x_1}\right) \left({x - x_2}\right) \dotsm \left({x - x_{n-1} }\right)$

which by evaluating at $x = x_n$ gives:

$V_n = V_{n-1} \left({x_n - x_1}\right) \left({x_n - x_2}\right) \dotsm \left({x_n - x_{n-1} }\right)$


Repeating the process:

\(\displaystyle V_n\) \(=\) \(\displaystyle \prod_{1 \mathop \le i \mathop < n} \left({x_n - x_i}\right) V_{n-1}\)
\(\displaystyle \) \(=\) \(\displaystyle \prod_{1 \mathop \le i \mathop < n} \left({x_n - x_i}\right) \prod_{1 \mathop \le i \mathop < n-1} \left({x_{n-1} - x_i}\right) V_{n-2}\)
\(\displaystyle \) \(=\) \(\displaystyle \dotsm\)
\(\displaystyle \) \(=\) \(\displaystyle \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right)\)


which establishes the solution.

$\blacksquare$


Proof 4

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

\(\displaystyle \map f {x}\) \(=\) \(\displaystyle x^{n-1} + \sum_{i \mathop = 0}^{n-2} a_i x^i\)

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

\(\displaystyle V_n\) \(=\) \(\displaystyle W\)

where

\(\displaystyle W\) \(=\) \(\displaystyle \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:

\(\displaystyle \map f {x}\) \(=\) \(\displaystyle \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 $\det \paren {W}$ by cofactors along the last column to prove

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

Let statement $\map P n$ be:

$\displaystyle V_n = \prod_{1 \mathop \le i \mathop \lt j \mathop \leq n} \paren { x_j - x_i }\quad$ for $n \ge 2$

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

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

Induction Step

Assume $\map P n$ is true. To prove $\map P {n+1}$ is true:

\(\displaystyle V_{n+1}\) \(=\) \(\displaystyle V_{n}\, \prod_{k \mathop = 1}^{n} \paren { x_{n+1} - x_k }\) by equation (1) with $n \to n+1$
\(\displaystyle \) \(=\) \(\displaystyle \prod_{1 \mathop \le m \mathop \lt k \mathop \leq n} \paren { x_k - x_m }\, \prod_{k \mathop = 1}^{n} \paren { x_{n+1} - x_k }\) Inducton hypothesis with new indexing symbols: $i \to m, j \to k$
\(\displaystyle \) \(=\) \(\displaystyle \prod_{1 \mathop \le i \mathop \lt j \mathop \leq n+1} \paren { x_j - x_i }\) simplified, $\map P {n+1}$ is true

The induction is complete. $\blacksquare$


Source of Name

This entry was named for Alexandre-Théophile Vandermonde.


Sources