Compute the 100th power of a given matrix So, I was asked this question in an interview. 
Given a matrix 
$$M = \begin{bmatrix} 0 & 1& 1 \\ 1& 0& 1 \\ 1&1& 0\end{bmatrix},$$ 
find $M^{100}$. 
How does one approach this question using pen and paper only?
 A: This is a common and neat trick.  If you diagonalize $M$ then you get $M=U^{-1} D U$, where $D$ is diagonal.  Now, consider $M^2$.  This equals $U^{-1} D U U^{-1} D U$.  But $ U U^{-1} = I$.  Therefore, $M^2= U^{-1} D^2 U$.  Hopefully you can see now (and it's easy to prove) that $M^N = U^{-1} D^N U$.  To compute $D^N$, just raise each diagonal element to the $N^{th}$ power.
A: If you are lucky enough after a couple of matrix multiplications you will discover
$$
\begin{cases}
M^n_{d}=\frac{2^{n}-2}{3},\quad M^n_o=\frac{2^{n}+1}{3};& n -\text{odd},\\
M^n_{d}=\frac{2^{n}+2}{3},\quad M^n_o=\frac{2^{n}-1}{3};& n -\text{even},\\
\end{cases}
$$
where $M^n_d$ and $M^n_o$ are diagonal and off-diagonal elements of the matrix $M^n$, respectively.
The observations leading to the result look like:
$$
M^{n+2}_d=2M^{n+1}_o=2(M^n_o+M^n_d)=2M^n_o+2M^n_d=M^{n+1}_d+2M^{n}_d,
$$
and similarly for $M_o$. 
A: Trying to avoid orthogonal diagonalization and square roots. The matrix of all ones has eigenvalues $(3,0,0),$ with eigenvectors (NOT normalized) as the columns of
$$
W =
\left(
\begin{array}{ccc}
1 & -1 & -1 \\
1 & 1 & -1 \\
1 & 0 & 2
\end{array}
\right)
$$
Oh, we need the inverse,
$$
W^{-1} = \frac{1}{6}
\left(
\begin{array}{ccc}
2 & 2 & 2 \\
-3 & 3 & 0 \\
-1 & -1 & 2
\end{array}
\right)
$$
Your matrix $M$ has the same eigenvectors with eigenvalues $(2,-1,-1).$ Therefore $M^{100}$ has the same eigenvectors with eigenvalues $(B,1,1),$ where $B = 2^{100}$ stands for BIG. We have the matrix equation for $M^{100} W,$ namely
$$
M^{100}
\left(
\begin{array}{ccc}
1 & -1 & -1 \\
1 & 1 & -1 \\
1 & 0 & 2
\end{array}
\right) =
\left(
\begin{array}{ccc}
B & -1 & -1 \\
B & 1 & -1 \\
B & 0 & 2
\end{array}
\right)
$$
We multiply both sides on the right by $W^{-1},$ I got it wrong the first time,
$$
M^{100} = \frac{1}{6}
\left(
\begin{array}{ccc}
B & -1 & -1 \\
B & 1 & -1 \\
B & 0 & 2
\end{array}
\right)
\left(
\begin{array}{ccc}
2 & 2 & 2 \\
-3 & 3 & 0 \\
-1 & -1 & 2
\end{array}
\right) =
 \frac{1}{6}
\left(
\begin{array}{ccc}
2B+4 & 2B-2 & 2B-2 \\
2B-2 & 2B+4 & 2B-2 \\
2B-2 & 2B-2 & 2B+4
\end{array}
\right) =
 \frac{1}{3}
\left(
\begin{array}{ccc}
B+2 & B-1 & B-1 \\
B-1 & B+2 & B-1 \\
B-1 & B-1 & B+2
\end{array}
\right)
$$
This is all integers as $ B = 2^{100} = 4^{50}  \equiv 1^{50} \equiv 1 \pmod 3$
A: Here's another trick. Denote 
$$
\mathbf 1 = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1& 1 & 1\end{bmatrix}, $$ 
and let $I=\mathrm{diag}(1,1,1)$ be the identity matrix. Then by the binomial formula 
$$
M^{100}=(\mathbf 1 - I)^{100}=\sum_{k=0}^{100} \binom{100}{k}(-1)^k \mathbf 1^{100-k}, $$ 
so we are led to considering powers of $\mathbf 1$, which are easy to compute: 
$$\mathbf 1^{j}=\begin{cases} 3^{j-1}\mathbf 1, & j\ge 1 \\ I & j=0.\end{cases}$$ 
We conclude that $M^{100} = \big(\sum_{k=0}^{99} \binom{100}{k}(-1)^k 3^{100-k-1}\big)\mathbf 1 + I, $ and the binomial sum can be computed by observing that 
$$
(3-1)^{100}=\sum_{k=0}^{100} (-1)^k \binom{100}{k}3^{100-k}.$$ 
We conclude that 
$$
M^{100}=\begin{bmatrix} \frac{2^{100}+2}3 & \frac{2^{100}-1}3 & \frac{2^{100}-1}3  \\ \frac{2^{100}-1}3 & \frac{2^{100}+2}3 & \frac{2^{100}-1}3  \\ \frac{2^{100}-1}3 & \frac{2^{100}-1}3 & \frac{2^{100}+2}3 \end{bmatrix}.$$
