Computing Fibonacci Numbers

The Matrix (with slightly fewer action sequences)

Because we need two consecutive values to find the next value in the Fibonacci sequence, we can think of a single "step" as going from a pair of numbers $(F(n), F(n-1))$ to $(F(n+1), F(n))$.

I'll skip the derivation, but as it turns out a linear transformation on a pair of numbers $(x, y)$ can always be expressed as $ax + by$, where $a$ and $b$ are some constants. For our transformations, we have

$$\providecommand{\cone}[1]{\textcolor{147eb3}{#1}} \providecommand{\ctwo}[1]{\textcolor{29a634}{#1}} \providecommand{\cthree}[1]{\textcolor{d1980b}{#1}} \providecommand{\cfour}[1]{\textcolor{d33d17}{#1}} \providecommand{\cfive}[1]{\textcolor{9d3f9d}{#1}} \providecommand{\csix}[1]{\textcolor{00a396}{#1}} \providecommand{\cseven}[1]{\textcolor{db2c6f}{#1}} \providecommand{\ceight}[1]{\textcolor{8eb125}{#1}} \providecommand{\cnine}[1]{\textcolor{946638}{#1}} \providecommand{\cten}[1]{\textcolor{7961db}{#1}}$$

$$\begin{aligned} F(n+1) &= \cone{1} F(n) + \cone{1} F(n - 1) \\ F(n) &= \cone{1} F(n) + \cone{0} F(n - 1) \\ \end{aligned}$$

These constants are the essence of the operation we're performing. Because they're the key, we can take them out and put them in a matrix:

$$\begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} \cone{1} & \cone{1} \\ \cone{1} & \cone{0} \\ \end{pmatrix} \begin{pmatrix} F(n) \\ F(n - 1) \end{pmatrix}$$

The only thing that looks really different is that we stacked $F(n)$ and $F(n-1)$ on top of each other instead of separating them horizontally like before. The constants and the left-hand side should look very similar to before.

Matrix multiplication is simply going from this representation to the equations above. Specifically, you take rows from the first matrix and columns from the second matrix and multiply together all of the terms—the sum of those products is the value at that cell. Let's look at one example to see what this looks like.