Computing Fibonacci Numbers

On the side we have a sample matrix multiplication. Here $A$ is a $2 \times 2$ matrix, and B is a $2 \times 3$ matrix (rows $\times$ columns). Matrices only multiply when the rows of the first match up with the columns of the second. The number of rows is given by the number of rows in the left matrix, and the number of columns is given by the number of columns in the right matrix. Succinctly, we have that

$$(m \times n)(n \times p) \Rightarrow m \times p$$

Here, we have a $\cone{2} \times \ctwo{2}$ matrix times a $\ctwo{2} \times \cthree{3}$ matrix, which gives us a $\cone{2} \times \cthree{3}$ matrix. Note that $BA$ isn't even a valid multiplication, because $B$ has 3 values per row but $A$ has 2 values per column. Matrix multiplication is not commutative! (It is associative: $ABC = (AB)C = A(BC)$.)

If this is new to you, take a second to look at what's being multiplied by what. To get the cell at row $i$ and column $j$ of the output, we take row $i$ from $A$ and column $j$ from $B$, multiply them together pairwise, and then sum them up.

If we think of matrices as transformations, like the Fibonacci stepping, then the shape of the matrix tells us how many values it takes in and how many it spits out. $B$ is a $2 \times 3$ matrix, so it can be multiplied by a $3 \times 1$ list of numbers to get a $2 \times 1$ of outputs: it takes three inputs and gives you two back. The recurrence $F(n + 1) = F(n) + F(n - 1)$ is represented by $\begin{pmatrix} 1 & 1 \end{pmatrix}$, a $1 \times 2$ matrix. The full version that gives you $F(n + 1)$ and $F(n)$ is just this row stacked on top of another row describing how we get $F(n)$.