# Vandermonde Determinant

## 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.