Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
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 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 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 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 at 9:26
You're right. Thanks! –  Garrett Jan 31 at 9:55
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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