Computing Fibonacci Numbers

Diagonalizing M

Diagonalization is a big topic¹, but we'll try to diagonalize $M$ here without too much magic. Strap in!

We want to find matrices $P$ and $D$ such that $PDP^{-1} = \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ and $D$ is diagonal. Let's do some rearranging:

$$\begin{aligned} PDP^{-1} &= M \\ PDP^{-1}P &= MP \\ PD &= MP \\ \end{aligned}$$

We've gotten rid of the scary inverse. Let's expand out these matrices and chug some numbers (take a second to convince yourself this is correct):

$$\begin{aligned} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} &= \begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix}a & b \\ c & d\end{pmatrix} \\ \begin{pmatrix}\lambda_1 a & \lambda_2 b \\ \lambda_1 c & \lambda_2 d \end{pmatrix} &= \begin{pmatrix} a + c & b + d \\ a & b \end{pmatrix} \\ \end{aligned}$$

This one matrix equality is really four separate equations: let's go cell by cell.