Compute the 100th power of a given matrix

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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$