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