# Matrix to power $2012$

How to calculate $A^{2012}$?

$A = \left[\begin{array}{ccc}3&-1&-2\\2&0&-2\\2&-1&-1\end{array}\right]$

How can one calculate this? It must be tricky or something, cause there was only 1 point for solving this.

-
BTW, matrices like this are called idempotent. en.wikipedia.org/wiki/Idempotent_matrix –  p.s. Jun 27 '13 at 3:50

Observe that $A^2$ is $A$.

So $A^{\large2012}$ is $A$ too.

-
How do you observe this? –  ᴊ ᴀ s ᴏ ɴ Jun 26 '13 at 13:29
just multiply A with A –  MSKfdaswplwq Jun 26 '13 at 13:33
(+1) nice observation. –  Mhenni Benghorbal Jun 26 '13 at 13:42

$$A = \left[\begin{array}{ccc}3&-1&-2\\2&0&-2\\2&-1&-1\end{array}\right]$$ $$A^2=\left[\begin{array}{ccc}3&-1&-2\\2&0&-2\\2&-1&-1\end{array}\right]\cdot \left[\begin{array}{ccc}3&-1&-2\\2&0&-2\\2&-1&-1\end{array}\right]$$

$$A^2 = \left[\begin{array}{ccc}{9-2-4}&{-3+2}&{-6+2+2}\\{6-4}&{-2+2}&{-4+2}\\{6-2}&{-2+1}&{-4+2+1}\end{array}\right]$$ $$A^2 = \left[\begin{array}{ccc}3&-1&-2\\2&0&-2\\2&-1&-1\end{array}\right]$$ $$A^2=A$$

$$A=A^2=A^3=\cdots =A^n,n\in N$$

so $$A^{2012}=A$$

-
(+1) nice answer. –  Mhenni Benghorbal Jun 26 '13 at 14:04

Hints:

• Diagonalize (Jordan Normal Form) the matrix $A = P J P^{-1}$
• Take advantage of the diagonalization, such that $A^{2012} = P J^{2012} P^{-1}$
-
Awesome hints! $+1^{2012}$ –  amWhy Jun 27 '13 at 0:08
This was my first thought as well, and it's one of the more general approaches for problems of this type, but as others have pointed out there's a shortcut in this specific case. –  user3490 Jun 28 '13 at 7:11
+1 Wow, great approach –  Dylan Yott Nov 9 '13 at 4:19
@DylanYott: thanks, regards –  Amzoti Nov 9 '13 at 4:26

This particular example, as noted above, is easy.

More generally, you could use a technique called "exponentiation via squaring." (Since the first step of this operation is to square $A$, it would lead you immediately to see that $A^2=A$, so you wouldn't have to do the entire operation.)

Or you could write out the characteristic polynomial $p(x)=\det(x I-A)$. Then divide the polynomial $x^{2012}$ by $p(x)$ to get a polynomial of degree $\leq 2$. That is:

$$x^{2012} = p(x)q(x) + r(x)$$

Then $A^{2012} = r(A)$. So you only have to compute $A^2$ to and $r(x)$ to figure out $A^{2012}$.

(The polynomial division might seem like it requires more operations than the "exponentiation by squaring," but it's actually pretty much equivalent, I believe - there is a way to compute $r(x)$ that is equivalent to "exponentiation by squaring.")

-
I don't think your last parenthesised sentence is correct. Provided $p(x)$ has easy and distinct roots, you can find $r(x)$ by substituting the three roots (which makes the term $p(x)q(x)$ vanish) and solving the resulting linear system for the coefficients of $r(x)$. This is not equivalent to repeated squaring, but rather to diagonalising $A$ and evaluating $A^{2012}$ that way. There is a variation of the method for repeated roots, just like one can manage eigenvalues with multiplicity, but the eigenvalues themselves have to be simple for this to be doable. –  Marc van Leeuwen Jul 18 '13 at 16:15
@MarcvanLeeuwen Sure, if you have "easy and distinct roots." I was talking about the general case, and the fact that the division algorithm is at least as easy as the repeated squaring. In some instances, you can make it faster, definitely. –  Thomas Andrews Jul 18 '13 at 16:18

This particular matrix satisfies $A^2 = A$. Thus $A^{2012} = A$ as well.

-

Write $A$ as: $$A=C^{-1}BC$$

where $B$ is a diagonal matrix with eigenvalues.

Then do the computation.

-