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 \le i < j \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 \le j \le n} x_j \prod_{1 \le i < j \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 \le i < j \le n} \left({a_i - a_j}\right)$

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

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

$V_n = \prod_{k=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:

$V_n = \prod_{k=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=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.

Alternative Proof

Proof by induction:

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

(It's written that way round to make the proof come out easier. This is how Mirsky derives the result.)

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition that $V_n = \prod_{1 \le i < j \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 \le i < j \le k} \left({a_i - a_j}\right)$.

Then we need to show:

$\displaystyle V_{k+1} = \prod_{1 \le i < j \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}$

If you use the Expansion Theorem for Determinants‎ to expand it in terms of the first row, you can see it is a polynomial in $x$ whose degree is no greater than $k$.

Call that polynomial $f \left({x}\right)$.

If you substitute any $a_r$ for $x$ in the determinant, two of its rows will be the same.

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

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$ as well.

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‎, we can see that 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 \le i < j \le k+1} \left({a_i - a_j}\right)$.

So this has to 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 \le i < j \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 \le i < j \le n} \left({a_i - a_j}\right)$

Source of Name

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

Sources

• L. Mirsky: An Introduction to Linear Algebra (1955): $\text{I}, \ \S 1.4: \ 1.4.5$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.3$: Exercise $37$