Vandermonde Determinant

From ProofWiki
Jump to: navigation, 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} \left({x_j - x_i}\right)$


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


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


We can see that statement $P \left({x}\right) = 0$ holds true for all $x_1, x_2, \cdots x_{n-1}$ because if $x=x_1, x_2, \cdots x_{n-1}$ starting determinant would have two equal rows and by Square Matrix with Duplicate Rows has Zero Determinant would $V_n = 0$.


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 returning $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}\) $\quad$ $\quad$
\(\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}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dotsm\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \prod_{1 \mathop \le i \mathop < j \mathop \le n} \left({x_j - x_i}\right)\) $\quad$ $\quad$


which establishes the solution.

$\blacksquare$


Source of Name

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