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_{i j} = 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 \map \det {\mathbf V} = \prod_{1 \mathop \le j \mathop \le n} x_j \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}$


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} \paren {a_i - a_j}$


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

$\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\) \(\displaystyle 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}\)

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:

\(\displaystyle V_{n + 1}\) \(=\) \(\displaystyle V_n \prod_{k \mathop = 1}^n \paren {x_{n + 1} - x_k}\) from $(1)$, setting $n \to n + 1$
\(\displaystyle \) \(=\) \(\displaystyle \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$
\(\displaystyle \) \(=\) \(\displaystyle \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$


Source of Name

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


Sources