Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 2 more comments

1 Answer 1

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)$?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.