Prove that for any $(n\times n)$ real matrix, the set of matrices $\{I,M,M^2,...,M^n\}$ are linearly dependent.
More formally, we have to prove that $$\forall M \in \mathbb{R}^{n \times n},\\ \exists (a_0,a_1,\ldots,a_n)\neq (0,0,\ldots,0) \\ \text{such that}\;\; \sum_{i=0}^n a_i M^i =0\,\,. $$
I have a solution which I will post below, but I would like to see if anyone has a more intuitive or elegant proof.
On
EDIT: @Traklon has pointed out that this does not prove the above theorem. It only proves the special case for which $M$ is diagonalizable. My bad!
We start with the expression $$\sum_{i=0}^n a_i M^i$$ and attempt to prove that there is some choice for the $\{a_i\}$ that makes this become zero.
We then diagonalize $M$, giving $M=C^{-1}DC$ where $D$ is a diagonal matrix with complex elements. Substituting this into the expression above and using the relation $M^p=C^{-1}D^pC$ for an integer $p$, we get \begin{align}\sum_{i=0}^n a_i M^i &=\sum_{i=0}^n a_i C^{-1}D^iC \\ &= C^{-1}\left\{\sum_{i=0}^n a_i D^i\right\}C\tag 2\end{align}
Since the set of matrices $\{D^0,D^1,D^2,\dots,D^n\}$ has $n+1$ elements, but only $n$ degrees of freedom (corresponding to its $n$ non-zero elements), it must be a linearly dependent set. That is to say that for some choice of the $\{a_i\}$, $$\sum_{i=0}^n a_i D^i = 0\,.$$
Plugging this into Eq (2) shows that for some choice of $\{a_i\}$, $$\sum_{i=0}^n a_i M^i=0$$ QED.
The characteristic polynomial, $$\det(M-\lambda I)=0 $$ is an order $n$ polynomial in $\lambda$, ie $$\sum_{i=0}^n a_i \lambda^i=0\,\,.$$
The Cayley-Hamilton theorem states that $M$ solves this equation which proves our theorem.