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.

-

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.

-

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.

-
My linear algebra courses are a little bit far, but you said "Since $M$ is a square matrix, it can be diagonalized, $M=C^{-1}DC$ where $D$ is a diagonal matrix with complex elements.". I think it can only be triangularized, am I wrong ? –  Traklon Jan 31 '14 at 8:46
I'm pretty sure that any real (or complex) square matrix can be diagonalized. I think this is proven by looking at the characteristic equation of the matrix. This will be a polynomial of order $n$ and by the fundamental theorem of algebra, $\lambda$ will have $n$ complex values (counted with multiplicity), corresponding to $n$ eigenvectors. –  Garrett Jan 31 '14 at 9:06
This is not true. For real matrices because not every polynomial has roots, and for complex matrices because the roots may have multiplicities > 1. A block like $(\lambda{}-1)^3$ in the characteristic polynomial doesn't imply that there are 3 lineary independant eigenvectors of eigenvalues 1, which is required to diagonalise the matrix. It only tells you that 1 is an eigenvalue. –  Traklon Jan 31 '14 at 9:14
I insist because it is very important. Not every matrix can be diagonalised. For example, consider $\begin{pmatrix} 1 & 1 \\ 0 & 1 \\ \end{pmatrix}$. The characteristic polynomial is $(\lambda{}-1)^2$, but you won't be able to find a basis formed of two linearily independant eigenvectors. This only tells you that 1 is an eigenvalue so it has at least 1 eigenvector. One consequence of this is that if all the roots of the characteristic polynomial have multiplicity 1, then the matrix is diagonalisable (it is not an equivalence, just an implication). –  Traklon Jan 31 '14 at 9:26
You're right. Thanks! –  Garrett Jan 31 '14 at 9:55