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?

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}.$$
