Matrix Multiplication: The Strange Rule That Runs the World

Matrix multiplication wasn't invented for neural networks. Neural networks inherited it from a mathematical idea that is centuries old, as I wrote in Matrix. Matrices represent transformations, and matrix multiplication represents applying or composing them. This whole note is me unpacking that one sentence.

First, what is a matrix?

A matrix is a grid of numbers with rows and columns. That is it. A spreadsheet is a matrix. A grayscale image is a matrix. A table of "how much of each ingredient in each recipe" is a matrix.

A vector is a matrix with a single column, like a point (x, y) or a list of features.

We say a matrix is $m\times n$ when it has $m$ rows and $n$ columns. Rows first, columns second.

The rule everyone learns first

Here is the mechanical rule. To multiply $A\times B$, take a row of $A$ and a column of $B$, multiply them pair by pair, and add up. That number goes into one cell of the answer.

Let me finish the whole example so you can check yourself:

The top-left is $1\cdot 7+2\cdot 9+3\cdot 11=58$. The bottom-right is $4\cdot 8+5\cdot 10+6\cdot 12=154$. Every cell is one row meeting one column.

Will the shapes fit?

A row of $A$ and a column of $B$ can only be paired up if they have the same length. So the number of columns in $A$ must equal the number of rows in $B$.

In code

def matmul(A, B):
    m, n, p = len(A), len(B), len(B[0])
    C = [[0] * p for _ in range(m)]
    for i in range(m):
        for j in range(p):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

Three loops, and that is where the cost comes from (more on that later). In real life you never write this yourself:

import numpy as np
C = A @ B      # the @ operator is matrix multiplication

But why this weird rule?

When I first saw this I asked: why not just multiply matching cells, like addition? That would be simpler. The answer took me a while to accept, and it is the most important part of this note.

A matrix is a machine that moves space

Think of a matrix as a function: you feed it a point, and it gives back a new point. It stretches, squishes, rotates or flips the whole plane.

The trick to reading a matrix is this: its columns tell you where the basic arrows $i=(1,0)$ and $j=(0,1)$ land. Once you know where those two go, you know where everything goes, because every point is just some amount of $i$ plus some amount of $j$.

Take $R=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$. Its first column $(0,1)$ is where $i$ lands. Its second column $(-1,0)$ is where $j$ lands. That is a 90 degree turn to the left. No mystery, the numbers just describe the move.

Multiplying matrices means chaining the moves

Now suppose I rotate the plane, then stretch it. Two moves. I could apply them one after another to every point, or I could combine them into one matrix first and apply that once.

That combined matrix is exactly the product. And the strange row-times-column rule is not arbitrary. It is precisely the arithmetic you get when you ask: "if $A$ sends $j$ to some column, where does $B$ send that?" Working it out gives dot products of rows and columns. The rule is what falls out of wanting $(BA)v=B(Av)$ to be true.

That is why order matters

Let $S$ stretch things twice as wide, and $R$ be the rotation above.

Different answers. Rotating then stretching is not the same as stretching then rotating, just like putting on socks then shoes is not the same as shoes then socks. So in general:

This is the biggest difference from ordinary number multiplication.

The rules of the game

The associative rule is the secret to speed. If you must compute $ABC$ and $A$ is huge but $C$ is a single column, grouping as $A(BC)$ can be thousands of times cheaper than $(AB)C$.

Three ways to look at the same multiplication

Same answer, three mental pictures. Use whichever helps.

1. Row times column: each cell is a dot product. Good for computing.
2. Combination of columns: $A\times v$ is a mix of the columns of $A$, with the entries of $v$ as amounts. Good for understanding transformations.
3. Sum of layers: $AB$ is a sum of (column of $A$) times (row of $B$) pieces. Good for understanding compression and low-rank ideas.

Why do we need it? Everywhere.

Here is the part that convinced me it is worth learning. The same operation keeps appearing in fields that seem unrelated.

1. Graphics and games

Every rotation, scaling, and camera move of a 3D model is a matrix. A game might chain a dozen moves. Instead of applying a dozen matrices to each of a million vertices, it multiplies the dozen into one matrix once and applies that. Your GPU does this billions of times a second.

2. Solving equations

Systems like $2x+3y=8$ and $x-y=1$ become $A\mathbf{x}=\mathbf{b}$. Engineering, physics simulation and economics all reduce to this shape.

3. State machines and Markov chains

This one ties back to my note on State Machines Explained. A Markov chain is a state machine where transitions have probabilities, stored in a matrix $P$. Multiplying gives multi-step behavior for free:

$P^2$ is the chance of going from any state to any other in two steps. $P^{100}$ is a hundred steps. That is a state machine's future, computed by repeated matrix multiplication.

4. Graphs

Remember Graphs. Store a graph as an adjacency matrix (1 if two nodes are connected). Square it, and each cell counts the walks of length two between nodes. Cube it for length three. Path counting, without ever walking the graph.

5. Neural networks

A layer of a neural network takes some inputs and produces some outputs. Every input connects to every output with its own weight. Stack all those weights into a matrix $W$ and the whole layer is one multiplication:

The magic is batching. Feeding 1000 examples at once is still a single multiply, $(1000\times 3)(3\times 2)$. And a deep network is just this repeated: multiply, add a bend (an activation like ReLU), multiply again. Without the bend, stacked layers would collapse into a single matrix, because a chain of moves is itself one move. That is exactly the composition idea from above.

This is the connection to my state machine note too: an RNN's update $h_t=f(W_h{h}_{t-1}+W_x{x}_t)$ is two matrix multiplies per step.

6. Attention in transformers

The engine of modern language models is built from matrix multiplies:

Turn each word into a row of numbers. Multiply the queries $Q$ by the keys $K^T$ to get a score for every pair of words. Softmax them into weights. Multiply by the values $V$ to blend information. That is it. A model reading a page is mostly doing this, layer after layer.

How expensive is it?

Multiplying two $n\times n$ matrices with the three loops above takes about $n^3$ operations. Double the size and the work becomes 8 times bigger. That adds up fast, which is why it is worth optimizing.

• Strassen (1969) showed you can do better than $n^3$, roughly $n^{2.81}$, by cleverly using fewer multiplications.
• Researchers have pushed the theoretical exponent lower still, though those methods are rarely practical.
• In practice, speed comes from using the hardware well: block the matrices to fit in cache, use vector instructions, and run on GPUs and dedicated tensor cores.

Why it keeps coming back

Try it yourself

• Multiply a $2\times 2$ by a $2\times 2$ by hand, then check with A @ B
• Verify $AB\ne BA$ with two small matrices of your own
• Rotate the point $(1,0)$ by $R$ twice and see where it lands ($R^2$)
• Build the adjacency matrix of a triangle and square it
• Write a one-layer neural network forward pass with only @ and max(0, x)
• Time your three-loop matmul against NumPy on $200\times 200$ matrices

Related: Matrix, State Machines Explained, Graphs, Data Structures Explained