If $n>k$ show that the $\mathrm{rank}(X)=k+1$ (Vandermonde matrix)

I have been given a formula for a polynomial regression

$$yt=\beta_0+\beta_1t+\cdots+\beta_kt^k+ut\text{ for }t=1\cdots n$$

I know that when writing this system in matrix form that this matrix is a Vandermonde matrix $X$. I've been told that if $n>k$ that $\mathrm{rank}(X)=k+1$. I was wondering how I would be able to show that.

• Welcome to MathSE. Please state your question in a clear and understandable way. Furthermore, please provide some context and show us what you have already tried and where are you stuck. Oct 15 '16 at 17:15
• What is "ut" in your formula ? Oct 15 '16 at 17:18
• @jeanMarie ut is the residual or the error vector sometimes represented with an epsilon.
– Nick
Oct 15 '16 at 17:48
• @polfosol thank you for your reply, the problem where i am stuck is there is not to much information on why this is true. the formula is a polynomial regression modell where Yt is a vector (dependant variable) and t a vector (indepentent variable) the t by the y and the u is used an index. I am just learning code now so i cant write it clearer.
– Nick
Oct 15 '16 at 18:24
• @styx is there no mathematical way to show this.
– Nick
Oct 15 '16 at 18:25

This is because a polynomial of degree n that has more than n roots is the zero polynomial. Thus a polynomial of degree n is uniquely defined by the images of n+1 distinct values, which therefor makes your Vandermonde matrix of rank n+1.

EDIT: A more detailed version of what i wrote previously

Let $P = \beta_0 + \beta_1 X + ... + \beta_n X^n$ be your polynomial of degree at most n

$A = \left| \begin{array}{ c c c} t_0^0 & ... & t_k^0\\ ... & & ...\\ t_0^k & ... & t_k^k\\ \end{array} \right| = [t_i^j]_{i, j \in [0, k]}$ be the Vandermonde matrix of k+1 of your distinct computed values,

$B= \left| \begin{array}{ c } \beta_0\\ ...\\ \beta_n \end{array} \right|$ be the matrix of your polynomial's coefficient and

$Y = \left| \begin{array}{ c } y_0\\ ...\\ y_n \end{array} \right|$ be the matrix of the images of your the different $t_n$ ($y_i = P(t_i)$ for $i \in [0, n]$).

You then have $AB = Y$.

Now let $Q, R \in \Bbb C_n[X]$ be complex polynomials of degree at most n. The D'Alembert-gauss theorem (which i will not prove here) states that any complex polynomial of degree >0 has at least 1 complex root. It follows that if a polynomial of degree at most n has more than n+1 roots, it is the zero polynomial.

Thus if $Q$ and $R$ match on $n+1$ values, $Q-R$ has $n+1$ roots so $Q-R = 0$ ie $Q=R$. This mean that P is uniquely defined by $y_0, ..., y_n$ and $A$ is therfore inversible and $B=A^{-1} Y$.

This means that $rank(A) = n+1$. Adding collumns (ie $t_{n+1}, t_{n+2}, ...$) can only increase the rank of your matrix, thus the rank of your matrix is n+1.

Another proof is :

Let $a_1, ..., a_n \in \Bbb C^n$ and $V_k = V_k (a_1, ..., a_k) = \left| \begin{array}{ c c c} a_1^0 & ... & a_k^0\\ ... & & ...\\ a_1^{k-1} & ... & a_k^{k-1}\\ \end{array} \right|$.

Prove by induction that : $${V_k} = \prod_{1 \le i \lt j\le k}(a_j-a_i)$$

Basis : $V_2 = \left| \begin{array}{ c c } 1 & 1 \\ a_1 & a_2 \end{array} \right| = a_2 - a_1$ which is what we want.

Inductive step : Assume that :$${V_k} = \prod_{1 \le i \lt j\le k}(a_j-a_i)$$

If there exists $i, j \in [1, k-1]$ such that $i \ne j$ and $a_i = a_j$, therefore two collumns of your matrix are equal thus $V_k = 0$ which is what we want.

Otherwise notice that $V_{k+1}(a_1, ..., a_{k}, x) = \left| \begin{array}{ c c c} a_1^0 & ... & x^0\\ ... & & ...\\ a_1^{k} & ... & x^{k}\\ \end{array} \right|$ is a polynomial in x of degree at most k. It follows that $V_{k+1}(a_1, ..., a_{k}, x)$ is zero for $x\in {a_1, ..., a_k}$, thus you can factor $$V_k(a_1, ..., a_{k-1}, x) = c \prod_{i=1}^k(x-a_i)$$, c being the leading coefficient of the polynomial.

However some properties of the determinant (of which the english name is unknown to me) give you that: $$V_k(a_1, ..., a_{k-1}, x) = \sum_{i=0}^{k} x^i \Delta_{i, k}$$ where $\Delta_{i, k}$ is the cofactor of your matrix. It follows that the leading coefficient is $\Delta_{i, k} = V_k$.

Thus $$V_{k+1}(a_1, ..., a_k, x) = \prod_{1 \le i \lt j\le k}(a_j-a_i) \prod_{i=1}^k(x-a_i)$$

Finally, compute for $x= a_k$ to get :

$$V_{k+1} = V_{k+1}(a_1, ..., a_k, a_{k+1}) = \prod_{1 \le i \lt j\le k+1}(a_j-a_i)$$

Which concludes the proof.

It is then obvious that the vandermonde matrix is inversible (ie its determinant is non-zero) iif $a_1, ..., a_k$ are distinct, and an inversible matrix of size n has rank n.