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?

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$
