Tools Matter

The problem find the n_th 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 A_n = A_n-1 + A_n-2 + A_n-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: