Why are Vandermonde matrices invertible?

Solution 1:

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

Solution 2:

Let $V$ be your Vandermonde matrix. If $p(t)=a_0+a_1t+\cdots+a_nt^n$ and $\alpha$ is the vector of coefficients of $p$, then the entries of $V\alpha$ are the values of $p$ on the points $x_0,\ldots,x_n$.

Now for $r=0,\ldots,n$ choose polynomials $p_r$ of degree $n$ so that $p(x_r)=1$ and $p(x_s)=0$ if $s\ne r$. Then the matrix with the coefficients of the polynomials $p_r$ as its columns is the inverse of $V$.

This is, of course, just a way of viewing Lagrange interpolation.

Solution 3:

For any $n+1$ distinct numbers $x_0, \ldots, x_n \in \mathbb{R}$, let $V(x_0,\ldots,x_n)$ and $D(x_0,\ldots,x_n)$ be a Vandermonde matrix and its determinant:

$$V(x_0,\ldots,x_n) = \begin{pmatrix} x_0^0 & \cdots & x_0^n \\ \vdots & \ddots & \vdots \\ x_n^0 & \cdots & x_n^n \end{pmatrix}\quad\text{ and }\quad D(x_0,\ldots,x_n) = \det V(x_0,\ldots,x_n) $$

It is clear $D(x_0) = 1 \ne 0$. Let us assume $D(x_0,\ldots,x_{m}) \ne 0$ for some $m < n$ and consider what happens to $D(x_0,\ldots,x_{m+1})$.

Viewed as a function of its last argument $x_{m+1}$, $D(x_0,\ldots,x_m,x)$ is a polynomial in $x$ with degree at most $m+1$. Since this polynomial vanishes at $m+1$ different values $x_0, \ldots, x_{m}$ already, it cannot vanish on any other $x$ (in particular at $x_{m+1}$). Otherwise, $D(x_0,\ldots,x_m,x)$ will be identically zero.

We know that $D(x_0,\ldots,x_m,x)$ isn't the zero polynomial. The leading coefficient of $x^{m+1}$ in $D(x_0,\ldots,x_m,x)$ is proportional to $D(x_0,\ldots,x_m)$ which is non-zero by induction assumption.

By induction, we can conclude $D(x_0,\ldots,x_n) \ne 0$ and hence $V(x_0,\ldots,x_n)$ is invertible.