ml.lab
Python sleeps until you run code
02 Matrices are machines

Lesson 2 of 4

Matrix multiplication

Doing one transformation after another is again a transformation, and its matrix is the product. The row-times-column rule falls out of that, along with three ways to read a product and a way to count its cost.

About 75 minutes
By the end you can
  • Derive the rule for multiplying matrices from composing two transformations.

  • Compute products by hand, including non-square ones, and read them as dot products, column combinations and sums of outer products.

  • Show with an example that AB≠BA\mathbf{AB} \ne \mathbf{BA}, and explain why grouping never changes a product.

  • Count the multiply-adds in a product and choose the cheaper grouping of a chain.

  • Implement matrix multiplication three ways and compare it with numpy.

A neural network applies one layer after another. Set the biases and nonlinearities aside for a moment and each layer is a matrix, so two layers mean: multiply by W1\mathbf{W}_1, then multiply the result by W2\mathbf{W}_2. Is that the same as multiplying by a single matrix? If so, which one?

Here is the same question in the plane. Turn the picture a quarter turn, then shear it. Each step keeps the grid a grid, so doing both in a row keeps it a grid too. The combination is linear, and by the last lesson it has a matrix. Finding that matrix is what matrix multiplication is. The row-times-column rule you may remember from school is not an arbitrary definition. It is what composition forces, and seeing it that way makes the rest of this module, and backpropagation later, much easier to follow.

The lesson goes in four steps: build the product from composition; read the same product three ways; see that order matters but grouping does not; and count what a product costs, which is most of what a neural network spends its time on.

Doing one map after another

Everything else in this lesson rests on one definition, so we start there.

Take two matrices B\mathbf{B} and A\mathbf{A}. Apply B\mathbf{B} to a vector, then apply A\mathbf{A} to the result: x↦A(Bx)\mathbf{x} \mapsto \mathbf{A}(\mathbf{B}\mathbf{x}). This combined map is called the composition, and it is linear, because each step carries linear combinations through. The first equals sign below uses that B\mathbf{B} is linear, the second that A\mathbf{A} is:

A(B(c1u+c2v))=A(c1Bu+c2Bv)=c1A(Bu)+c2A(Bv).\mathbf{A}\big(\mathbf{B}(c_1\mathbf{u} + c_2\mathbf{v})\big) = \mathbf{A}(c_1\mathbf{B}\mathbf{u} + c_2\mathbf{B}\mathbf{v}) = c_1\mathbf{A}(\mathbf{B}\mathbf{u}) + c_2\mathbf{A}(\mathbf{B}\mathbf{v}).

So the composition has a matrix. We call it AB\mathbf{AB}, the product, and define it by (AB)x=A(Bx)(\mathbf{AB})\mathbf{x} = \mathbf{A}(\mathbf{B}\mathbf{x}) for every x\mathbf{x}.

To find it, use the key fact from the last lesson: a matrix's columns are where the basis vectors land. Write ej\mathbf{e}_j for the jj-th basis vector, with a 1 in place jj and zeros elsewhere (in the plane, e1=ı^\mathbf{e}_1 = \hat{\imath} and e2=ȷ^\mathbf{e}_2 = \hat{\jmath}), and bj\mathbf{b}_j for column jj of B\mathbf{B}. Multiplying B\mathbf{B} by ej\mathbf{e}_j takes 1 of column jj and 0 of every other column, so Bej=bj\mathbf{B}\mathbf{e}_j = \mathbf{b}_j. Then A\mathbf{A} sends that on to Abj\mathbf{A}\mathbf{b}_j. So the jj-th basis vector ends up at Abj\mathbf{A}\mathbf{b}_j, and that is the jj-th column of the product:

column j of AB=A bj.\text{column } j \text{ of } \mathbf{AB} = \mathbf{A}\,\mathbf{b}_j .

A worked example. Let R=[0−110]\mathbf{R} = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} be the quarter turn counterclockwise from the last lesson's gallery, and S=[1101]\mathbf{S} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} the shear that slides ȷ^\hat{\jmath} to (1,1)(1,\allowbreak 1). "Rotate, then shear" is SR\mathbf{SR}: the rotation acts first, so it sits on the right, next to the vector. The columns of R\mathbf{R} are (0,1)(0,\allowbreak 1) and (−1,0)(-1,\allowbreak 0). Apply S\mathbf{S} to each one, as a combination of the columns of S\mathbf{S}, which are (1,0)(1,\allowbreak 0) and (1,1)(1,\allowbreak 1):

S[01]=0[10]+1[11]=[11],S[−10]=−1[10]+0[11]=[−10].\mathbf{S}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = 0\begin{bmatrix} 1 \\ 0 \end{bmatrix} + 1\begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \qquad \mathbf{S}\begin{bmatrix} -1 \\ 0 \end{bmatrix} = -1\begin{bmatrix} 1 \\ 0 \end{bmatrix} + 0\begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -1 \\ 0 \end{bmatrix}.

So SR=[1−110]\mathbf{SR} = \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix}. Check it on x=(1,2)\mathbf{x} = (1,\allowbreak 2) the long way, one matrix at a time. First Rx=1 (0,1)+2 (−1,0)=(0−2, 1+0)=(−2,1)\mathbf{R}\mathbf{x} = 1\,(0,\allowbreak 1) + 2\,(-1,\allowbreak 0) = (0 - 2,\allowbreak \ 1 + 0) = (-2,\allowbreak 1). Then S(−2,1)=−2 (1,0)+1 (1,1)=(−2+1, 0+1)=(−1,1)\mathbf{S}(-2,\allowbreak 1) = -2\,(1,\allowbreak 0) + 1\,(1,\allowbreak 1) = (-2 + 1,\allowbreak \ 0 + 1) = (-1,\allowbreak 1). The short way uses the single matrix: SR x=1 (1,1)+2 (−1,0)=(1−2, 1+0)=(−1,1)\mathbf{SR}\,\mathbf{x} = 1\,(1,\allowbreak 1) + 2\,(-1,\allowbreak 0) = (1 - 2,\allowbreak \ 1 + 0) = (-1,\allowbreak 1). Same point, one matrix instead of two.

The stepper below builds SR\mathbf{SR} the same way, one column per step, and answers the question: where does each number of the product come from? R\mathbf{R} sits above the result SR\mathbf{SR} and S\mathbf{S} sits to its left, so row ii of S\mathbf{S} and column jj of R\mathbf{R} meet at entry (i,j)(i,\allowbreak j) of SR\mathbf{SR}. Under the grids, the current step is broken down into its multiplications, and a sentence says what the step shows. Step and Back move one step at a time, and the switch labelled "Read it as" changes the view.

Composition as multiplication is one of the main threads of the course. In Jacobians and the chain rule, every smooth function gets a matrix that describes it near a point, and the chain rule turns out to be the product of those matrices. Backpropagation is that product, computed in the cheapest order (the last section of this lesson shows why order affects the cost).

The entry rule falls out

The dot view in the stepper was not a coincidence. Zoom in on a single entry. Column jj of AB\mathbf{AB} is Abj\mathbf{A}\mathbf{b}_j, and by the row view from the last lesson, entry ii of Abj\mathbf{A}\mathbf{b}_j is row ii of A\mathbf{A} dotted with bj\mathbf{b}_j. So

(AB)ij=(row i of A)⋅(column j of B)=∑kAikBkj.(\mathbf{AB})_{ij} = (\text{row } i \text{ of } \mathbf{A})\cdot(\text{column } j \text{ of } \mathbf{B}) = \sum_{k} A_{ik}B_{kj}.

That is the row-times-column rule, derived rather than decreed. The index kk runs along the row of A\mathbf{A} and down the column of B\mathbf{B} at the same time. In the example, entry (1,2)(1,\allowbreak 2) of SR\mathbf{SR} is row 1 of S\mathbf{S}, which is (1,1)(1,\allowbreak 1), dotted with column 2 of R\mathbf{R}, which is (−1,0)(-1,\allowbreak 0): (1)(−1)+(1)(0)=−1(1)(-1) + (1)(0) = -1, as it should be.

Go slower: The entry rule from composition, with indices

Let A\mathbf{A} be m×nm \times n and B\mathbf{B} be n×pn \times p, and let x\mathbf{x} have pp entries.

Step 1. By the row view, entry kk of Bx\mathbf{B}\mathbf{x} is (Bx)k=∑j=1pBkjxj(\mathbf{B}\mathbf{x})_k = \sum_{j=1}^{p} B_{kj}x_j, for k=1,…,nk = 1,\allowbreak \ldots,\allowbreak n.

Step 2. Apply A\mathbf{A} to that vector. By the row view again, entry ii of the result is row ii of A\mathbf{A} dotted with Bx\mathbf{B}\mathbf{x}. Then substitute Step 1 for (Bx)k(\mathbf{B}\mathbf{x})_k: (A(Bx))i=∑k=1nAik (Bx)k=∑k=1nAik∑j=1pBkjxj.(\mathbf{A}(\mathbf{B}\mathbf{x}))_i = \sum_{k=1}^{n} A_{ik}\,(\mathbf{B}\mathbf{x})_k = \sum_{k=1}^{n} A_{ik}\sum_{j=1}^{p} B_{kj}x_j .

Step 3. Multiply out: AikA_{ik} does not depend on jj, so it can move inside the inner sum, next to each term: ∑k=1nAik∑j=1pBkjxj=∑k=1n∑j=1pAikBkjxj.\sum_{k=1}^{n} A_{ik}\sum_{j=1}^{p} B_{kj}x_j = \sum_{k=1}^{n}\sum_{j=1}^{p} A_{ik}B_{kj}x_j .

Step 4. Swap the order of the two sums, so that jj is on the outside. Both orders add up the same finite set of terms, so the total does not change: ∑k=1n∑j=1pAikBkjxj=∑j=1p∑k=1nAikBkjxj.\sum_{k=1}^{n}\sum_{j=1}^{p} A_{ik}B_{kj}x_j = \sum_{j=1}^{p}\sum_{k=1}^{n} A_{ik}B_{kj}x_j .

Step 5. Factor out xjx_j. It does not depend on kk, so it can come out of the inner sum, the reverse of Step 3: ∑j=1p∑k=1nAikBkjxj=∑j=1p(∑k=1nAikBkj)xj.\sum_{j=1}^{p}\sum_{k=1}^{n} A_{ik}B_{kj}x_j = \sum_{j=1}^{p}\Big(\sum_{k=1}^{n} A_{ik}B_{kj}\Big)x_j .

Step 6. Compare with the row view for a single matrix C\mathbf{C}, (Cx)i=∑jCijxj(\mathbf{C}\mathbf{x})_i = \sum_j C_{ij}x_j. The two agree for every x\mathbf{x} exactly when every coefficient of xjx_j matches (to see that they must, take x=ej\mathbf{x} = \mathbf{e}_j, which leaves only the jj-th term on each side): Cij=∑k=1nAikBkj.C_{ij} = \sum_{k=1}^{n} A_{ik}B_{kj}.

The index kk runs over the columns of A\mathbf{A} and the rows of B\mathbf{B} at the same time, so those two counts must be equal. That is the shape rule: (m×n)(n×p)(m \times n)(n \times p) gives m×pm \times p, and the inner sizes must match. Shapes, transposes and batches turns this into a habit.

To recap: AB\mathbf{AB} is "B\mathbf{B}, then A\mathbf{A}"; its columns are A\mathbf{A} times the columns of B\mathbf{B}; and its entries are rows of A\mathbf{A} dotted with columns of B\mathbf{B}. Now compute three products by hand with the entry rule. The first two use the same pair of matrices in both orders.

On paperThree products by hand

Compute each product by hand. Write every entry as a row of the left matrix dotted with a column of the right one: entry (i,j)(i,\allowbreak j) uses row ii of the left matrix and column jj of the right one.

  1. [1234][0110]\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
  2. [0110][1234]\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}
  3. [102−131][312110]\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix}\begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix}

Then say in words what multiplying by [0110]\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} did in parts 1 and 2, and what shape the product in part 3 would have in the other order. To check, enter the 2×22 \times 2 product from part 3 row by row.

Work it on real paper: writing each step is the point. Then check your final answer here and compare your working with the walk-through.

The product in part 3

One entry per box, row by row (Tab moves along a row). 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

Three ways to read one product

The formula (AB)ij=∑kAikBkj(\mathbf{AB})_{ij} = \sum_k A_{ik}B_{kj} has three indices: ii picks a row of A\mathbf{A}, jj a column of B\mathbf{B}, and kk runs along the shared inner dimension. The product is always the same collection of small multiplications AikBkjA_{ik}B_{kj}, one for every choice of ii, jj and kk, but you can choose which index to hold fixed while you add them up. Each choice is a different way to see the same product, and each one shows up again later in the course.

The dot view fixes ii and jj and adds over kk: every entry is a row of A\mathbf{A} dotted with a column of B\mathbf{B}. Use it to compute a single entry, or to read the product as a table of similarities: if the rows of A\mathbf{A} are one set of vectors and the columns of B\mathbf{B} are another, AB\mathbf{AB} lists every pairwise dot product.

The column view fixes jj: column jj of the product is A\mathbf{A} times column jj of B\mathbf{B}, which is where we started. If the columns of B\mathbf{B} are separate inputs, AB\mathbf{AB} applies A\mathbf{A} to all of them in one operation. Its mirror image is the row view: row ii of AB\mathbf{AB} is row ii of A\mathbf{A} times B\mathbf{B}. To check it, take entry jj of that row: it is row ii of A\mathbf{A} dotted with column jj of B\mathbf{B}, which is (AB)ij(\mathbf{AB})_{ij} by the entry rule.

The outer-product view fixes kk, and it needs one new product first. For a column vector u\mathbf{u} with mm entries and a row vector with pp entries, written v⊤\mathbf{v}^\top, the outer product uv⊤\mathbf{u}\mathbf{v}^\top is the m×pm \times p matrix whose entry (i,j)(i,\allowbreak j) is uivju_i v_j. (The ⊤\top is the transpose, which turns the column v\mathbf{v} into a row; the next lesson treats it properly.) For example, with u=(1,2)\mathbf{u} = (1,\allowbreak 2) and v=(3,4)\mathbf{v} = (3,\allowbreak 4):

uv⊤=[12][34]=[1⋅31⋅42⋅32⋅4]=[3468].\mathbf{u}\mathbf{v}^\top = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\begin{bmatrix} 3 & 4 \end{bmatrix} = \begin{bmatrix} 1 \cdot 3 & 1 \cdot 4 \\ 2 \cdot 3 & 2 \cdot 4 \end{bmatrix} = \begin{bmatrix} 3 & 4 \\ 6 & 8 \end{bmatrix}.

Row 1 is 1 times (3,4)(3,\allowbreak 4) and row 2 is 2 times (3,4)(3,\allowbreak 4); column 1 is 3 times u\mathbf{u} and column 2 is 4 times u\mathbf{u}. Every row of an outer product is a multiple of v⊤\mathbf{v}^\top and every column is a multiple of u\mathbf{u}, which makes it the simplest kind of nonzero matrix; module 3 calls it rank one. The outer-product view says

AB=∑k=1n(column k of A) (row k of B).\mathbf{AB} = \sum_{k=1}^{n} (\text{column } k \text{ of } \mathbf{A})\,(\text{row } k \text{ of } \mathbf{B}).

The reason, in two moves. Entry (i,j)(i,\allowbreak j) of the kk-th outer product is (entry ii of column kk of A\mathbf{A}) times (entry jj of row kk of B\mathbf{B}), which is AikBkjA_{ik}B_{kj}. Adding the outer products over kk therefore adds AikBkjA_{ik}B_{kj} over kk in every entry at once, and that sum is (AB)ij(\mathbf{AB})_{ij}. For our example, column kk of S\mathbf{S} times row kk of R\mathbf{R}, for k=1k = 1 and k=2k = 2:

SR=[10][0−1]+[11][10]=[0−100]+[1010]=[1−110].\mathbf{SR} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\begin{bmatrix} 0 & -1 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & -1 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix}.

The stepper below runs all three views on a non-square product, a 2×32 \times 3 matrix A\mathbf{A} times a 3×23 \times 2 matrix B\mathbf{B}, so you can watch the same 2⋅3⋅2=122 \cdot 3 \cdot 2 = 12 multiplications grouped three ways. The inner size is 3: a row of A\mathbf{A} and a column of B\mathbf{B} have 3 entries each. The lines in the empty top-left corner join column kk of A\mathbf{A} to row kk of B\mathbf{B}, for k=1,2,3k = 1,\allowbreak 2,\allowbreak 3.

To recap: the dot view builds one entry at a time, the column view one column at a time, and the outer view adds a whole layer to every entry at once. All three do the same multiplications and only add them up in a different order.

Why keep three views? Because each one turns up later. The dot view is a table of similarities, and attention builds exactly such a table of scores, between every pair of positions in a sequence (Attention). The column view and its mirror, the row view, are batching: stack many inputs side by side and one product handles them all. The next lesson does this with the inputs stored as rows, the way code does. And the outer-product view looks like a curiosity until you train a network. The gradient of a layer's weight matrix turns out to be a sum of outer products, one per example in the batch (Backpropagation). A matrix built from only a few outer products is low-rank (Rank and low-rank updates), the idea behind LoRA, which fine-tunes a large model by learning a weight update made of two thin matrices (Preferences, rewards and adapters).

Now use the column view with no numbers at all, only shapes.

Quick checkOne column of a product

A\mathbf{A} is 3×43 \times 4 and B\mathbf{B} is 4×54 \times 5. What is column 2 of AB\mathbf{AB}?

Choose one answer, then check.

Order matters, grouping does not

Two facts about products get used constantly: you cannot swap the two factors, but you can regroup a long chain however you like. Both come straight from composition.

Rotate then shear gave SR=[1−110]\mathbf{SR} = \begin{bmatrix} 1 & -1 \\ 1 & 0 \end{bmatrix}. Now shear first and rotate second, which is RS\mathbf{RS}. Its columns are R\mathbf{R} applied to the columns of S\mathbf{S}. Column 1: R(1,0)=(0,1)\mathbf{R}(1,\allowbreak 0) = (0,\allowbreak 1), the first column of R\mathbf{R}. Column 2: R(1,1)=1 (0,1)+1 (−1,0)=(−1,1)\mathbf{R}(1,\allowbreak 1) = 1\,(0,\allowbreak 1) + 1\,(-1,\allowbreak 0) = (-1,\allowbreak 1). So

RS=[0−110][1101]=[0−111].\mathbf{RS} = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & -1 \\ 1 & 1 \end{bmatrix}.

A different matrix. Follow ȷ^\hat{\jmath} to see why. Rotating first turns it to (−1,0)(-1,\allowbreak 0), which the shear leaves alone, because the shear slides points sideways in proportion to their height and (−1,0)(-1,\allowbreak 0) has height 0. Shearing first slides it to (1,1)(1,\allowbreak 1), and the rotation then turns that to (−1,1)(-1,\allowbreak 1). Two different endpoints, so two different second columns.

The transformation widget from the last lesson shows both orders as pictures. It starts on RS\mathbf{RS}, shear then rotate, with the unit square shaded where it lands and the area readout beside it.

Matrix multiplication is not commutative: in general AB≠BA\mathbf{AB} \ne \mathbf{BA}. Some pairs do commute. A uniform scaling kIk\mathbf{I} commutes with every matrix: (kI)Ax=k Ax(k\mathbf{I})\mathbf{A}\mathbf{x} = k\,\mathbf{A}\mathbf{x}, and A(kI)x=A(k x)=k Ax\mathbf{A}(k\mathbf{I})\mathbf{x} = \mathbf{A}(k\,\mathbf{x}) = k\,\mathbf{A}\mathbf{x} by the scaling rule. Two rotations of the plane commute too: turning by 30∘30^\circ then 60∘60^\circ and turning by 60∘60^\circ then 30∘30^\circ both turn by 90∘90^\circ. But never assume it.

The identity matrix I\mathbf{I} is the map that moves nothing. Its columns are the basis vectors themselves: I=[1001]\mathbf{I} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} in the plane, and in general ones on the diagonal and zeros everywhere else. Doing nothing before or after A\mathbf{A} changes nothing, so AI=IA=A\mathbf{AI} = \mathbf{IA} = \mathbf{A}. (If A\mathbf{A} is not square, the two identities have different sizes: for a 2×32 \times 3 matrix, AI\mathbf{AI} uses the 3×33 \times 3 identity and IA\mathbf{IA} the 2×22 \times 2 one.)

Order matters, but grouping does not:

(AB)C=A(BC).(\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC}).

Both sides are the single map "apply C\mathbf{C}, then B\mathbf{B}, then A\mathbf{A}", so they are the same matrix. This property, associativity, is why we can write a long chain such as ABCDx\mathbf{ABCD}\mathbf{x} without parentheses and compute it in whatever grouping is convenient. It is also the key step in showing that a stack of layers without nonlinearities collapses into a single matrix: W3(W2(W1x))=(W3W2W1)x\mathbf{W}_3(\mathbf{W}_2(\mathbf{W}_1\mathbf{x})) = (\mathbf{W}_3\mathbf{W}_2\mathbf{W}_1)\mathbf{x}. Layers and parameter counts works this out with biases included, and Neurons and layers builds on it.

Go slower: Associativity with indices

Let A\mathbf{A} be m×nm \times n, B\mathbf{B} be n×pn \times p and C\mathbf{C} be p×qp \times q.

Left grouping. Use the entry rule for the product of AB\mathbf{AB} and C\mathbf{C}, then the entry rule again for (AB)il(\mathbf{AB})_{il}, and multiply CljC_{lj} into the inner sum: ((AB)C)ij=∑l=1p(AB)il Clj=∑l=1p(∑k=1nAikBkl)Clj=∑l=1p∑k=1nAikBklClj.((\mathbf{AB})\mathbf{C})_{ij} = \sum_{l=1}^{p} (\mathbf{AB})_{il}\,C_{lj} = \sum_{l=1}^{p}\Big(\sum_{k=1}^{n} A_{ik}B_{kl}\Big)C_{lj} = \sum_{l=1}^{p}\sum_{k=1}^{n} A_{ik}B_{kl}C_{lj}.

Right grouping. The same three moves, with BC\mathbf{BC} as the inner product: (A(BC))ij=∑k=1nAik (BC)kj=∑k=1nAik(∑l=1pBklClj)=∑k=1n∑l=1pAikBklClj.(\mathbf{A}(\mathbf{BC}))_{ij} = \sum_{k=1}^{n} A_{ik}\,(\mathbf{BC})_{kj} = \sum_{k=1}^{n} A_{ik}\Big(\sum_{l=1}^{p} B_{kl}C_{lj}\Big) = \sum_{k=1}^{n}\sum_{l=1}^{p} A_{ik}B_{kl}C_{lj}.

Compare. Both are the sum of AikBklCljA_{ik}B_{kl}C_{lj} over every pair (k,l)(k,\allowbreak l), added in a different order, and a finite sum does not depend on the order of its terms.

To recap: swapping the two factors usually changes the map, grouping a chain never does, and the identity changes nothing on either side. Now find a product where the order is the whole question.

Work it outReflect, then rotate

Find the single matrix that first reflects across the xx-axis and then rotates a quarter turn counterclockwise. The reflection is F=[100−1]\mathbf{F} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} and the rotation is R=[0−110]\mathbf{R} = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}. Enter the 2×22 \times 2 matrix row by row.

RF

One entry per box, row by row (Tab moves along a row). 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

What it costs

Grouping never changes the answer, but it can change the amount of work enormously. So we need to count.

Multiplying an m×nm \times n matrix by an n×pn \times p matrix produces mpmp entries. Each entry is a dot product of length nn: nn multiplications and n−1n - 1 additions. Count each multiplication together with the addition that accumulates it as one multiply-add (hardware has a single instruction for exactly this), and each entry costs nn multiply-adds. So

cost of (m×n)(n×p)=mp entries×n multiply-adds each=mnp multiply-adds.\text{cost of } (m \times n)(n \times p) = mp \text{ entries} \times n \text{ multiply-adds each} = mnp \text{ multiply-adds}.

For two n×nn \times n matrices that is n⋅n⋅n=n3n \cdot n \cdot n = n^3. Double the size and the work becomes (2n)3=8n3(2n)^3 = 8n^3: eight times as much. A matrix times a vector is the case p=1p = 1 and costs mnmn.

Now the grouping. Let A\mathbf{A} and B\mathbf{B} be 1000×10001000 \times 1000 and let x\mathbf{x} have 1000 entries, so it is a 1000×11000 \times 1 matrix.

  • (AB)x(\mathbf{AB})\mathbf{x}. Forming AB\mathbf{AB} costs 1000⋅1000⋅1000=1091000 \cdot 1000 \cdot 1000 = 10^9 multiply-adds. Then the 1000×10001000 \times 1000 result times x\mathbf{x} costs 1000⋅1000=1061000 \cdot 1000 = 10^6. Total: 1,001,000,0001{,}001{,}000{,}000.
  • A(Bx)\mathbf{A}(\mathbf{B}\mathbf{x}). First Bx\mathbf{B}\mathbf{x} costs 10610^6 and gives a vector. Then A\mathbf{A} times that vector costs another 10610^6. Total: 2,000,0002{,}000{,}000.

Same vector, about 1,001,000,000/2,000,000≈5001{,}001{,}000{,}000 / 2{,}000{,}000 \approx 500 times less work. The rule of thumb: when a chain ends in a vector, multiply from the vector outwards, so that every step is a cheap matrix-vector product. For a chain of matrices with no vector, there is no one-line rule, but the counting still decides: add up mnpmnp for each product in each grouping and compare. Groupings that keep the intermediate results small win.

Backpropagation makes exactly this choice. The chain rule for a network is a long product of matrices (Jacobians and the chain rule calls them Jacobians). Because the loss is a single number, one end of that chain is a vector, and backpropagation starts from that end, carrying a single gradient vector backwards through the chain instead of ever multiplying two of those large matrices together.

The code below prints the two orders of the rotation and the shear, then times both groupings on 300×300300 \times 300 matrices. The exact times depend on your machine, but A(Bx)\mathbf{A}(\mathbf{B}\mathbf{x}) should come out far faster, and the last check should print True.

⌘+Enter runs · edit freelyPython sleeps until you run code

Now count a chain with rectangular matrices yourself.

Work it outSame answer, different bill

A\mathbf{A} is 1000×5001000 \times 500, B\mathbf{B} is 500×2000500 \times 2000, and x\mathbf{x} has 2000 entries. The groupings (AB)x(\mathbf{AB})\mathbf{x} and A(Bx)\mathbf{A}(\mathbf{B}\mathbf{x}) give the same vector. Count the multiply-adds of each grouping, then give the ratio: the cost of (AB)x(\mathbf{AB})\mathbf{x} divided by the cost of A(Bx)\mathbf{A}(\mathbf{B}\mathbf{x}). It comes out as a whole number; enter it as one.

ratio

Type a number: 0.25, -2, 3/4 and sqrt(2) all work. Enter checks.

Why does this counting matter for machine learning? Because nearly all of the arithmetic in a neural network is matrix multiplication. Take one 4096×40964096 \times 4096 weight matrix and apply it to 2,048 token vectors at once, one batch of text: that is 2048×4096×4096=211⋅212⋅212=235≈34.42048 \times 4096 \times 4096 = 2^{11} \cdot 2^{12} \cdot 2^{12} = 2^{35} \approx 34.4 billion multiply-adds, for one matrix in one layer. Inside its 32 layers, the 7-billion-parameter design counted in Layers and parameter counts has 224 weight matrices: 128 of exactly this size and 96 that are about 2.7 times larger.

Now build it yourself: the loops for all three views, and a timing comparison with numpy.

Code itMatrix multiplication three ways

Write matrix multiplication three ways, one for each view in this lesson, then compare the loop version with numpy.

  • matmul(A, B): three nested loops, entry by entry, with no @ or np.dot.
  • matmul_columns(A, B): column j of the result is A @ B[:, j].
  • matmul_outer(A, B): the sum over k of the outer product of column k of A with row k of B.

All three raise ValueError when the inner sizes differ, before doing any arithmetic. The code at the bottom times your loops against numpy's @ on 50×5050 \times 50 matrices; read the ratio it prints.

⌘+Enter runsPython sleeps until you run code
Write your code where the starter says raise NotImplementedError, then press Run tests. Each check says what it expects.

A few quick products by hand, with new numbers each time, keep the entry rule sharp.

Practice setMatrix product reps
3 correct in a row completes the set. A miss starts the count again.

Compute AB\mathbf{A}\mathbf{B} for A=[00−2−220]\mathbf{A} = \begin{bmatrix}0 & 0 \\ -2 & -2 \\ 2 & 0\end{bmatrix} and B=[13−1−213]\mathbf{B} = \begin{bmatrix}1 & 3 & -1 \\ -2 & 1 & 3\end{bmatrix}.

AB

One entry per box, row by row (Tab moves along a row). 0.25, -2, 3/4 and sqrt(2) all work. Enter moves to the next empty box and checks once all are filled.

To finish, explain the whole chain of reasoning in your own words, from composition to the entry rule.

In your own wordsWhy row times column

Explain to a colleague, starting from what AB\mathbf{AB} does to a vector, why column jj of AB\mathbf{AB} is A\mathbf{A} times column jj of B\mathbf{B}, and why entry (i,j)(i,\allowbreak j) is row ii of A\mathbf{A} dotted with column jj of B\mathbf{B}. Then say why AB\mathbf{AB} and BA\mathbf{BA} usually differ.

A few sentences first: 0 of 60 characters.

Saved in this browser as you type.