Computing Fibonacci Numbers

Call the inverse of a square matrix¹ $M$, denoted $M^{-1}$, the matrix such that $M^{-1}M = MM^{-1} = I$. It's the equivalent of $\frac{1}{x}$ for real numbers.

Let's suppose we can find some matrix $P$ such that $M = PDP^{-1}$, where $D$ is a diagonal matrix.

If we expand out, for instance, $M^2$, a funny thing happens: $$\begin{aligned} M &= PDP^{-1} \\ M^2 &= (PDP^{-1})(PDP^{-1}) \\ &= PD(P^{-1}P)DP^{-1} \\ &= PDIDP^{-1} \\ &= PDDP^{-1} \\ &= P(D^2)P^{-1} \end{aligned}$$

The extra copies of $P$ and $P^{-1}$ just vanish. In general, we have that $(PDP^{-1})^n = P(D^n)P^{-1}$. All of those cancellations save us a lot of work: recall that $D^n$ is relatively easy to compute. So, for the price of just two extra multiplications, we can use this representation, called a diagonalization of $M$, to efficiently compute $M^n$.