Matrix power series has linearly dependent terms 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.
 A: 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.
A: 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.
