# Vandermonde matrix: if c is a solution to $Vx = 0$, then the coefficients $c_1, c_2, \dots, c_n$ must all be zero

Here is my problem:

Given a vector x $\in \mathbb{R}^{n+1}$, the $(n + 1) \times (n + 1)$ matrix $V$ defined by

$$v_{ij} = \begin{cases} 1 & \text{if } j = 1 \\ x_i^{j - 1} & \text{for } j = 2, \dots, n + 1 \end{cases}$$

is called the Vandermonde matrix.

Suppose that $x_1, x_2, \dots, x_{n+1}$ are all distinct. Show that if c is a solution to $V$ x = 0, then the coefficients $c_1, c_2, \dots, c_{n+1}$ must all be zero, and hence $V$ must be nonsingular.

Each entry of $V$ c is an $n$th degree polynomial, so if $c_1, c_2, \dots, c_{n+1}$ were not all zero, then $x_1, x_2, \dots, x_{n+1}$ would have to be the roots of the polynomial. But it's perfectly possible for an $n$th degree polynomial to have $n$ roots, so I'm not sure how I can get this to work.

-
There are $n+1$ $x_i$s and BTW $(n+1)$ $c_j$s (typo?). – martini Mar 22 '12 at 17:15
If you will write out the matrix explicitly on paper rather than in LaTeX, you might see that the entries of $Vc$ are the values of a polynomial $c_0+c_1x + c_2x^2 + \cdots + c_nx^n$ at $n+1$ different points $x_1, x_2, \ldots, x_{n+1}$. – Dilip Sarwate Mar 22 '12 at 17:22
Yeah, you're right. There are $n+1$ elements in c – Matt Gregory Mar 22 '12 at 17:22
@Dilip: What if $x_1, x_2, \dots, x_{n+1}$ are the roots of this polynomial? Then that doesn't prove anything. – Matt Gregory Mar 22 '12 at 17:26
@MattGregory: It does prove everything :). Since the polynomial is of degree $n$, it can't have $n+1$ zeros $x_1, \ldots, x_{n+1}$ besides it is the zero polynomial. – martini Mar 22 '12 at 17:32

Hints:

1. The determinant of $V$ is given by $\operatorname{det}(V) =\, \color{red}{??}$

2. If $x_i$'s are all distinct, then what can you say about $(x_i - x_j)$ and $\operatorname{det}(V)$?

3. If $det(A) \neq 0$ then ${\rm nullity}(A) =\, \color{red}{??}$, and what are the solutions to $Ax = 0$?

4. If $c^{T} = \begin{pmatrix} c_0 & c_1 & \ldots & c_n \end{pmatrix}$ then $$Vc = \begin{pmatrix} f(\color{red}{??}) \\ f(\color{red}{??}) \\ \vdots \\ f(\color{red}{??}) \\ \end{pmatrix}$$ where $f(x) = c_0 + c_1 x + \ldots + c_{n} x^n.$

5. If ${\rm deg}(f(x)) = n,$ then how many distinct points does it take to uniquely interpolate $f(x)$?

-