TAOCP 1.2.3 Exercise 37

Exercise 37. ▶ [M24] Show that the determinant of Vandermonde’s matrix is

$$\prod_{1 \le j \le n} x_j \prod_{1 \le i < j \le n} (x_j - x_i).$$

Verified: yes
Solve time: 33s

Solution

Let $V_n = (a_{ij}){1 \le i,j \le n}$ denote the $n \times n$ Vandermonde matrix, where $a{ij} = x_j^i$. We aim to show that

$\det(V_n) = \prod_{1 \le j \le n} x_j \prod_{1 \le i < j \le n} (x_j - x_i).$

We proceed by induction on $n$.

Base case $n = 1$. Then $V_1 = (x_1)$, and $\det(V_1) = x_1$. The formula gives

$\prod_{1 \le j \le 1} x_j \prod_{1 \le i < j \le 1} (x_j - x_i) = x_1 \cdot 1 = x_1,$

which agrees.

Induction step. Assume the formula holds for $n-1 \ge 1$. Consider $V_n$. Subtract $x_1$ times row $i-1$ from row $i$ for $i = 2, \dots, n$; that is, perform the row operations

$R_i \leftarrow R_i - x_1 R_{i-1}, \quad i=2,\dots,n.$

Each operation leaves the determinant unchanged except possibly by a factor of $1$, since we are only adding multiples of other rows. After this operation, the first column becomes

$\begin{pmatrix} x_1 \ 0 \ \vdots \ 0 \end{pmatrix},$

because $x_1^i - x_1 \cdot x_1^{i-1} = x_1^i - x_1^i = 0$ for $i \ge 2$.

Expanding the determinant along the first column using the cofactor expansion, we obtain

$\det(V_n) = x_1 \det(V_{n-1}'),$

where $V_{n-1}'$ is the $(n-1) \times (n-1)$ matrix obtained by deleting the first row and first column. The entries of $V_{n-1}'$ are

$a_{ij}' = x_{j+1}^i - x_1 x_{j+1}^{i-1} = x_{j+1}^{i-1} (x_{j+1} - x_1), \quad 1 \le i,j \le n-1.$

Factor $x_{j+1} - x_1$ from each column $j$, $1 \le j \le n-1$, to obtain

$\det(V_{n-1}') = \prod_{j=2}^n (x_j - x_1) \det\bigl((x_j^{i-1})_{1 \le i,j \le n-1}\bigr).$

But the remaining matrix $(x_j^{i-1})_{1 \le i,j \le n-1}$ is itself a Vandermonde matrix of order $n-1$ on $x_2, \dots, x_n$. By the induction hypothesis, its determinant is

$\prod_{j=2}^n x_j \prod_{2 \le i < j \le n} (x_j - x_i).$

Combining the factors, we obtain

$$ \begin{aligned} \det(V_n) &= x_1 \prod_{j=2}^n (x_j - x_1) \prod_{j=2}^n x_j \prod_{2 \le i < j \le n} (x_j - x_i) \ &= \prod_{j=1}^n x_j \prod_{1 \le i < j \le n} (x_j - x_i), \end{aligned} $$

as desired.

This completes the proof.

∎