Matrix Multiplication: A Programmer’s Perspective
The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication.
\begin{aligned}\left[ \begin{matrix} F_n \\ F_{n-1} \end{matrix} \right] &= \left[ \begin{matrix} F_{n-1} + F_{n-2} \\ F_{n-1} \end{matrix} \right] \\&= \left[ \begin{matrix} 1 \times F_{n-1} + 1 \times F_{n-2} \\ 1 \times F_{n-1} + 0 \times F_{n-2} \end{matrix} \right] \\&= \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] \times \left[ \begin{matrix} F_{n-1} \\ F_{n-2} \end{matrix} \right] \\&= \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] ^{2} \times \left[ \begin{matrix} F_{n-2} \\ F_{n-3} \end{matrix} \right] \\&= \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] ^{n-1} \times \left[ \begin{matrix} F_{1} \\ F_{0} \end{matrix} \right]\end{aligned}Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is:
\begin{aligned}\left[ \begin{matrix} F_n \\ F_{n-1} \\ F_{n-2} \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right] ^{n-2} \times \left[ \begin{matrix} F_{2} \\ F_{1} \\ F_{0} \end{matrix} \right]\end{aligned}By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn).
In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose:
\begin{aligned}p &= 2x + 3y \\ q &= 3x - 7y \\ r &= -8x + 9y \end{aligned}Represent this way from transforming \begin{aligned} \left[ \begin{matrix} x \\ y \end{matrix} \right] \end{aligned} to \begin{aligned} \left[ \begin{matrix} p \\ q \\ r \end{matrix} \right] \end{aligned} by the matrix \begin{aligned} \left[ \begin{matrix} 2 & 3 \\ 3 & -7 \\ -8 & 9 \end{matrix} \right] \end{aligned}.
Now let’s transform \begin{aligned} \left[ \begin{matrix} p \\ q \\ r \end{matrix} \right] \end{aligned} to \begin{aligned} \left[ \begin{matrix} a \\ b \end{matrix} \right] \end{aligned}:
\begin{aligned}a &= 22p - 38q + 17r \\ b &= 13p + 10q + 9r \end{aligned}Represent that by the matrix
\begin{aligned} \left[ \begin{matrix} 22 & -38 & 17 \\ 13 & 10 & 9 \end{matrix} \right] \end{aligned}So we can transform \begin{aligned} \left[ \begin{matrix} x \\ y \end{matrix} \right] \end{aligned} directly to \begin{aligned} \left[ \begin{matrix} a \\ b \end{matrix} \right] \end{aligned} by multiplying matrix
\begin{aligned}\left[ \begin{matrix} a \\ b \end{matrix} \right] &= \left[ \begin{matrix} 22 & -38 & 17 \\ 13 & 10 & 9 \end{matrix} \right] \times \left[ \begin{matrix} p \\ q \\ r \end{matrix} \right] \\ &= \left[ \begin{matrix} 22 & -38 & 17 \\ 13 & 10 & 9 \end{matrix} \right] \times \left[ \begin{matrix} 2 & 3 \\ 3 & -7 \\ -8 & 9 \end{matrix} \right] \times \left[ \begin{matrix} x \\ y \end{matrix} \right] \\ &= \left[ \begin{matrix} -206 & 485 \\ -16 & 50 \end{matrix} \right] \times \left[ \begin{matrix} x \\ y \end{matrix} \right] \\ \end{aligned}So we get
\begin{aligned}a &= -206x + 485y \\b &= -16x + 50y\\ \end{aligned}Also, matrix multiplication can be visualised as scaling /rotating /skewing a geometric plane:
However, from a programmer’s perspective, matrix multiplication can be treated as a collection of operations of handling data inputs and outputs:
As an input passes an operation, it creates an output item:
