Linear Algebra – Why Vandermonde Matrices are Invertible

linear algebramatricespolynomials

A Vandermonde-matrix is a matrix of this form:

$$\begin{pmatrix}
x_0^0 & \cdots & x_0^n \\
\vdots & \ddots & \vdots \\
x_n^0 & \cdots & x_n^n
\end{pmatrix} \in \mathbb{R}^{(n+1) \times (n+1)}$$.

condition ☀ : $\forall i, j\in \{0, \dots, n\}: i\neq j \Rightarrow x_i \neq x_j$

Why are Vandermonde-matrices with ☀ always invertible?

I have tried to find a short argument for that. I know some ways to show that in principle:

  • rank is equal to dimension
  • all lines / rows are linear independence
  • determinant is not zero
  • find inverse

According to proofwiki, the determinant is

$$\displaystyle V_n = \prod_{1 \le i < j \le n} \left({x_j – x_i}\right)$$

There are two proofs for this determinant, but I've wondered if there is a simpler way to show that such matrices are invertible.

Best Answer

This is not entirely dissimilar to the answer already posted by Chris Godsil, but I'll post this anyway, maybe it can provide slightly different angle for someone trying to understand this.

We want to show that the matrix
$$\begin{pmatrix} x_0^0 & \cdots & x_0^n \\ \vdots & \ddots & \vdots \\ x_n^0 & \cdots & x_n^n \end{pmatrix}$$
is invertible.

It suffices to show that the rows columns of this matrix are linearly independent.

So let us assume that $c_0v_0+c_1v_1+\dots+c_nv_n=\vec 0=(0,0,\dots,0)$, where $v_j=(x_0^j,x_1^j,\dots,x_n^j)$ is the $j$-the row column written as a vector and $c_0,\dots,c_n\in\mathbb R$.

Then we get on the $k$-th coordinate
$$c_0+c_1x_k+c_2x_k^2+\dots+c_nx_k^n=0,$$ which means that $x_k$ is a root of the polynomial $p(x)=c_0+c_1x+c_2x^2+\dots+c_nx^n$.

Now if the polynomial $p(x)$ of degree at most $n$ has $(n+1)$ different roots $x_0,x_1,\dots,x_n$, it must be the zero polynomial and we get that $c_0=c_1=\dots=c_n=0$.

This proves that the vectors $v_0,v_1,\dots,v_n$ are linearly independent. (And, in turn, we get that the given matrix is invertible.)

Related Question