Derivation of the Determinant of the Vandermonde Matrix
Definition
For distinct $1, x_{1} , x_{2 } , \cdots , x_{n}$, the matrix $V_{n}$ defined as follows is called a Vandermonde Matrix.
$$ V_{n} := \begin{bmatrix} 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n-1} \\ 1 & x_{2} & x_{2}^{2} & \cdots & x_{2}^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & x_{n}^{2} & \cdots & x_{n}^{n-1} \end{bmatrix} $$
Formula
The determinant of $V_{n}$ is
$$ \det V_{n} = \prod_{1 \le i < j \le n } (x_{j} - x_{i}) $$
Explanation
Vandermonde matrices have a unique appearance but surprisingly appear frequently in numerical solutions of differential equations among other areas.
Assuming $1, x_{1} , x_{2 } , \cdots , x_{n}$ are distinct, $\displaystyle \prod_{ 1 \le i < j \le n } (x_{j} - x_{i}) \ne 0$, and the invertibility of $V_{n}$ is guaranteed. This fact is mainly used to demonstrate the existence of a unique solution to the system of equations $\mathbf{w} = V_{n} \mathbf{u}$.
Derivation
Strategy: Various methods can show this, especially introducing a proof using mathematical induction. This proof is preferable because it requires some mathematical knowledge but involves less calculation and is clean since it does not perform row operations. The Factor Theorem and Fundamental Theorem of Algebra that appear in the middle are important facts, but they are not critical in the context of this proof so it’s okay if you don’t know them.
Define Proposition $\displaystyle P(n) : \det V_{n} = \prod_{ 1 \le i < j \le n } (x_{j} - x_{i})$.
**Part 1. $n=1,2$
$$ P(1) : \det V_{1} = | 1 | = 1 \\ P(2) : \det V_{2} = \left| \begin{matrix} 1 & x_{1} \\ 1 & x_{2} \end{matrix} \right| = x_{2} - x_{1} $$
Therefore $P(n)$ holds when $n=1,2$.
**Part 2. $n=k$
Assume that $\displaystyle P(k) : \det V_{k} = \prod_{1 \le i < j \le k } (x_{j} - x_{i})$ holds.
**Part 3. $n=k+1$
Let’s redefine the Vandermonde matrix by adding $x$ as the $k+1$ th variable as follows.
$$ V_{k}’ := \begin{bmatrix} 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{k} & x_{k}^{2} & \cdots & x_{k}^{k} \\ 1 & x & x^{2} & \cdots & x^{k} \end{bmatrix} $$
Define the determinant $M_{ij}$ and the cofactor $C_{ij} := (-1)^{i + j} M_{ij}$ of the matrix obtained by removing the $i$th and $j$th rows of the square matrix $A_{n \times n} = (a_{ij})$. For the chosen $i$th row, $\displaystyle \det A = \sum_{j=1}^{n} a_{ij} C_{ij} $
When the $(k+1)$th row is selected, according to the Laplace expansion, the determinant of $V_{k} ' $
$$ \det V_{k} ' = 1 C_{(k+1)1} + x C_{(k+1)2} + x^2 C_{(k+1)3} + \cdots + x^{k} C_{(k+1)(k+1)} $$
can be expressed as a $k$th degree polynomial $f(x)$ in $x$. Substituting $x_{1} , \cdots , x_{k}$ for $x$, the determinant of matrix $V_{k} ' $ becomes $0$ as it results in two identical rows. In other words, using the polynomial $f(x)$
$$ f(x_{1}) = \cdots = f(x_{k}) = 0 $$
By the Factor Theorem and the Fundamental Theorem of Algebra, $f(x)$ can precisely be expressed as
$$ f(x) := C(x-x_{1})(x-x_{2}) \cdots (x-x_{k}) $$
In the meantime, the coefficient $C_{(k+1)(k+1)}$ of $x^{k}$ is the cofactor of the $(k+1)$th row and the $(k+1)$th column, so
$$ C_{(k+1)(k+1)} = (-1)^{(k+1)+(k+1)} \det \begin{bmatrix} 1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{k-1} \\ 1 & x_{2} & x_{2}^{2} & \cdots & x_{2}^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{k} & x_{k}^{2} & \cdots & x_{k}^{k-1} \end{bmatrix} =1 \cdot \prod_{1 \le i < j \le k } (x_{j} - x_{i}) $$
In other words, since $\displaystyle C = C_{(k+1)(k+1)}$,
$$ \det V_{k} ' = f(x) = \left[ \prod_{1 \le i < j \le k } (x_{j} - x_{i}) \right] \left[ (x-x_{1})(x-x_{2}) \cdots (x-x_{k}) \right] $$
If we redefine $x_{k+1} := x$ for convenience as $V_{k} ' = V_{k+1}$,
$$ P(k+1) : \det V_{k+1} = \prod_{1 \le i < j \le k+1 } (x_{j} - x_{i}) $$
it can be seen that this holds. Since $P(k)$ is true, $ P(k+1)$ is true; hence, the proof is completed by mathematical induction.
■