Computing Fibonacci Numbers

Diagonalization

The identity matrix is the matrix with all 1s on the main diagonal (top-left to bottom-right) and 0s everywhere else. Multiplying by the identity matrix always does nothing.

If instead of 1s we have different numbers on the main diagonal, with everything else still 0, multiplication does something interesting:

$$\begin{aligned} I &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ I^2 = I^3 = I^n &= I \\ D &= \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} \\ D^2 &= \begin{pmatrix} a^2 & 0 \\ 0 & b^2 \end{pmatrix} \\ D^n &= \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix} \\ \end{aligned}$$

I highly recommend working out $D^2$ for yourself if you aren't comfortable with the logic behind it. For diagonal matrices, it seems like exponentiation is a lot simpler than it is for generic matrices.

But the matrix $M = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ isn't diagonal. How can we apply this special case when our matrix doesn't fit it?