Matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ to a large power

Question

Compute $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^{99}$

What is the easier way to do this other than multiplying the entire thing out?

Thanks

Answer 1

Following the comment of Matt Samuel: $$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} $$

$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^3 = \begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix} $$

$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & n+1 \\ 0 & 1 \end{pmatrix} $$

Answer 2

Hint One option that avoids explicit use of induction is to write the matrix as $$I + J,$$ where $$J := \pmatrix{0 & 1\\0 & 0}.$$ Since $J^2 = 0$, each term in the expansion of $$(I + J)^{99}$$ with two or more factors of $J$ is zero.

Edit As Will points out, since $I$ and $J$ commute, we can expand the power as \begin{align}\require{cancel} (I + J)^{99} &= \sum_{a = 0}^{99} {99 \choose a} I^{99 - a} J^a \\ &= I + 99 J + \sum_{a = 2}^{99} {99 \choose a} J^a \\ &= I + 99 J + \cancelto{0}{J^2 \sum_{a = 2}^{99} {99 \choose a}J^{a - 2}} \\ &= I + 99 J . \end{align}

Answer 3

Consider the case of a general $2 \times 2$ matrix times $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$:

$\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \times \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) = \left( \begin{matrix} a & a + b \\ c & c + d \end{matrix} \right) $.

Thus, we see that multiplying any $2 \times 2$ matrix by $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ once leaves the entries in the first column unchanged and increments the entries in the second column by the corresponding entries from the first column. Since our lower-left entry was zero and the upper-left entry was one, this has the effect of simply incrementing the upper-right entry by one but leaving the rest unchanged.

Therefore, since we begin with $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ and multiply it by $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ 98 times, we see that $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{99} = \left( \begin{matrix} 1 & 99 \\ 0 & 1 \end{matrix} \right) $.

Answer 4

There is a well-known general technique to raise something to a natural-number power. We first translate from base $10$ to base $2$:

$$99_{10} = 1100011_2$$

You can calculate the matrix to a power of two with a tower of squaring.

\begin{align} \left(m^{2}\right)^2 &= m^{4} \\ \left(m^{4}\right)^2 &= m^{8} \\ \left(m^{8}\right)^2 &= m^{16} \\ \end{align} So with $8$ squarings you can calculate all the factors needed. Then multiply the ones corresponding to a $1$ bit in the binary representation of $99$, and you have your answer. So $8 + 3$ multiplications would be required.

This method does not depend on the value of the matrix.