With a given matrix $A \in M_3(\mathbb{R})$ show that $A^{2009} + A^{2008} = 2 ^{2008} (A + I_3)$. I am given the matrix:
$$A = \begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\end{pmatrix}$$
I have to show that the following is true:
$$A ^ {2009} + A ^ {2008} = 2 ^ {2008} (A + I_3)$$
I calcucalted $A^2, A^3, A^4,...$ in hopes that I would find some kind of pattern, but I didn't.
 A: Hint
$$A+I_3=\begin{pmatrix}
1& 1 & 1 \\
1 & 1& 1 \\
1 & 1 & 1\\
\end{pmatrix}$$
Call this matrix $B$. Find a pattern for $A^nB$.
A: HInts.


*

*show that the eigenvalues of $A$ are $2,-1,-1$

*justify that $A$ can be diagonalized , so $A=PDP^{-1}$ for some $P$, and $D$ is diagonal, with dagonal entries $2,-1,-1$

*Show that the relation you need to prove is equivalent to $D^{2009}+D^{2008}=2^{2008}(D+I_3)$

*Conclude
A: More generally, $A^{n+1} + A^{n} = 2 ^{n} (A + I)$ for all $n \in \mathbb N$. This is proved by induction using that the minimal polynomial of $A$ is $x^2-  x - 2=(x-2)(x+1)$ and so $A^2=A+2I$:
$$
A^{n+2} + A^{n+1} = A(A^{n+1} + A^{n})= A(2^{n} (A + I))=2^n(A^2+A)= 2^n(2A+2I)=2^{n+1} (A + I)
$$
(The characteristic polynomial of $A$ is $x^3-3x-2=(x - 2) (x + 1)^2$. So the minimal polynomial of $A$ is either $(x - 2) (x + 1)^2$ or $(x - 2) (x + 1)$.)
A: Your matrix is symmetric, so you can take a few short-cuts. In general a matrix is diagonalizable iff for every eigenvalue, the algebraic multiplicity of the eigenvalue in the characteristic equation is equal to the dimension of the corresponding eigenspace. However, a symmetric matrix has 3 special properties (i) all the eigenvalues are real, so we don't have to work with complex numbers on the diagonal or anywhere else. (ii) the matrix is diagonalizable $i.e.$ it is guaranteed the every eigenspace has the "right" dimension [(iii) it is orthogonally diagonalizable I'll say a bit about that at the end, since we can do your problem wihout using that property.]Unfortunately, knowing that a matrix is diagonalizable isn't enough-we have to actually $do$ the diagonalization. Your matrix has eigenvalues 2, with algebraic multiplicity 1 and -1 with algebraic multiplicity 2. A basis for the eigenspace for eigenvalue 2 is $$\left\{\begin{bmatrix}1\\1\\1\end{bmatrix}\right\}$$ A basis for the eigenspace for eigenvalue -1 is $$\left\{\begin{bmatrix}1\\0\\-1\end{bmatrix},\begin{bmatrix}0\\1\\-1\end{bmatrix}\right\}.$$ Let $$P=\begin{bmatrix}1&1&0\\1&0&1\\1&-1&-1\end{bmatrix}$$ Let $$D=\begin{bmatrix}2&0&0\\0&-1&0\\0&0&-1\end{bmatrix}. $$ Then $P^{-1}AP=D,A=PAP^{-1}$ $$ A^n=PD^nP^{-1}$$
$$=P\begin{bmatrix}2^n&0&0\\0&(-1)^n&0\\0&0&(-1)^n\end{bmatrix}P^{-1}$$ All that remains for you to do is calculate $P^{-1}$ and stick in the appropriate values for $n.$ If you find the calculation of $P^{-1}$ tedious, a slight variation, which which works for symmetric matrices, is to use their third property above. Find an orthonormal basis for each eigenspace($e.g.$ by the Gram-Schmidt procedure) and write them side-by-side to give an orthogonal matrix matrix $ P'$ such that $A=P'D(P')^{-1}$. Then 
$(P')^{-1}=P'^T,$ which is much easier to calculate.
