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.

  • $\begingroup$ 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. $\endgroup$ – polfosol Oct 15 '16 at 17:15
  • $\begingroup$ What is "ut" in your formula ? $\endgroup$ – Jean Marie Oct 15 '16 at 17:18
  • $\begingroup$ @jeanMarie ut is the residual or the error vector sometimes represented with an epsilon. $\endgroup$ – Nick Oct 15 '16 at 17:48
  • $\begingroup$ @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. $\endgroup$ – Nick Oct 15 '16 at 18:24
  • $\begingroup$ @styx is there no mathematical way to show this. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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