Calculating Higher Powers of Matrices!

May 28, 2010

This post definitely could win an award for “most boring title ever,” but this is kind of a neat idea, and it’s a sweet application of the cayley-hamilton theorem.

So, here’s the problem.  You have some little matrix M and you want to calculate M^{43}, but you don’t have your trusty graphing calculator.  Yeah, this could get really, really annoying.  Especially if M is more than a 2\times 2 matrix.  Ugh.

So, let’s talk about characteristic polynomials.  Given some matrix M, we have that the characteristic polynomial is f(\lambda) = det(\lambda I - M).  One of the main results concerning characteristic polynomials is…

[Edit: here, I fell into a trap that is so common there is a wikipedia section devoted to it!  Nonetheless, because the rest of the post doesn’t depend on the proof of the Cayley-Hamilton theorem, we’re okay.  Note that it actually does takes a bit of work to pull this proof off.]


Theorem (Cayley-Hamilton): A matrix M satisfies its own characteristic polynomial; in other words, f(M) = 0.


The Cool Thing: Given some matrix M, which is some n\times n matrix, you can calculate the r-th power of the matrix M as a linear combination of powers of M, the largest power being at most n-1.

What does this mean?  Say we have M, which is a 4\times 4 matrix.  We can compute, say, M^{6553} as a linear combination that looks like this: a_{0} + a_{1}M + a_{2}M^{2} + a_{3}M^{3}.

This is kind of crazy if you think about it.  But it’s not that bad.  Let’s do an example of how to do it, and you’ll be able to generalize it.  Let’s compute something little.  Let’s let M be

\left(\begin{array}{cc} 2 & 1\\ 0 & 2 \end{array}\right)

and let’s compute M^{4}.  What’s the characteristic polynomial of M?  Compute it yourself!  We did this kind of thing in my last post: it will turn out to be


f(\lambda) = (\lambda - 2)(\lambda - 2) + 0 = \lambda^{2} - 4\lambda + 4


Now, here’s the clever part.  By cayley-hamilton, we have that


f(M) = M^{2} - 4M + 4 = 0.


So, that means that M^{2} = 4M - 4.  This means (by multiplying both sides by M and by replacing things inductively):


M^{3} = 4M^{2} - 4M


= 4(4M - 4) - 4M = 16M - 16 - 4M


= 12M - 16


and then,


M^{4} = 4M^{3} - 4M^{2}


= 4(12M - 16) - 4(4M - 4) = 48M - 64 - 16M + 16


= 32M - 48.


So, what do we have?  M^{4} = 32M - 48.  Well, this is easy to compute.

\left(\begin{array}{cc} 64 & 32\\ 0 & 64 \end{array}\right) - \left(\begin{array}{cc} 48 & 0\\ 0 & 48 \end{array}\right)

= \left(\begin{array}{cc} 16 & 20\\ 0 & 16 \end{array}\right)

and, if you check, that’s right.  Weird!  Not always useful, but certainly more do-able than multiplying a 4\times 4 matrix together four thousand times.

11 Responses to “Calculating Higher Powers of Matrices!”

  1. Student said

    Cool way of explaining it :)

  2. Anonymous said

    i was looking for a quick explanation. this worked well for me.

    Thank you ;)

    an engineering student from Turkey.

  3. Anonymous said

    very helpful article

  4. nesreen said

    is it applied to higher order matrices? 3×3 or so

  5. Anonymous said

    You’re very good at explaining this stuff. If you’re not a teacher you missed your calling.

  6. Anonymous said

    Is there a quick way to get to powers as high as 6553?

  7. Anonymous said

    thank you

  8. Anonymous said

    How we can calculate A^50?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: