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, 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, then multiply the result by W2. 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.
Everything else in this lesson rests on one definition, so we start there.
Take two matrices B and A. Apply B to a vector, then apply A to the result: x↦A(Bx). 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 is linear, the second that A is:
A(B(c1u+c2v))=A(c1Bu+c2Bv)=c1A(Bu)+c2A(Bv).
So the composition has a matrix. We call it AB, the product, and define it by (AB)x=A(Bx) for every x.
To find it, use the key fact from the last lesson: a matrix's columns are where the basis vectors land. Write ej for the j-th basis vector, with a 1 in place j and zeros elsewhere (in the plane, e1=^ and e2=^), and bj for column j of B. Multiplying B by ej takes 1 of column j and 0 of every other column, so Bej=bj. Then A sends that on to Abj. So the j-th basis vector ends up at Abj, and that is the j-th column of the product:
column j of AB=Abj.
A worked example. Let R=[01−10] be the quarter turn counterclockwise from the last lesson's gallery, and S=[1011] the shear that slides ^ to (1,1). "Rotate, then shear" is SR: the rotation acts first, so it sits on the right, next to the vector. The columns of R are (0,1) and (−1,0). Apply S to each one, as a combination of the columns of S, which are (1,0) and (1,1):
So SR=[11−10]. Check it on x=(1,2) the long way, one matrix at a time. First Rx=1(0,1)+2(−1,0)=(0−2,1+0)=(−2,1). Then S(−2,1)=−2(1,0)+1(1,1)=(−2+1,0+1)=(−1,1). The short way uses the single matrix: SRx=1(1,1)+2(−1,0)=(1−2,1+0)=(−1,1). Same point, one matrix instead of two.
The stepper below builds SR the same way, one column per step, and answers the question: where does each number of the product come from? R sits above the result SR and S sits to its left, so row i of S and column j of R meet at entry (i,j) of 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 j of AB is Abj, and by the row view from the last lesson, entry i of Abj is row i of A dotted with bj. So
(AB)ij=(row i of A)⋅(column j of B)=k∑AikBkj.
That is the row-times-column rule, derived rather than decreed. The index k runs along the row of A and down the column of B at the same time. In the example, entry (1,2) of SR is row 1 of S, which is (1,1), dotted with column 2 of R, which is (−1,0): (1)(−1)+(1)(0)=−1, as it should be.
Go slower: The entry rule from composition, with indices
Let A be m×n and B be n×p, and let x have p entries.
Step 1. By the row view, entry k of Bx is (Bx)k=∑j=1pBkjxj, for k=1,…,n.
Step 2. Apply A to that vector. By the row view again, entry i of the result is row i of A dotted with Bx. Then substitute Step 1 for (Bx)k:
(A(Bx))i=∑k=1nAik(Bx)k=∑k=1nAik∑j=1pBkjxj.
Step 3. Multiply out: Aik does not depend on j, so it can move inside the inner sum, next to each term:
∑k=1nAik∑j=1pBkjxj=∑k=1n∑j=1pAikBkjxj.
Step 4. Swap the order of the two sums, so that j 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.
Step 5. Factor out xj. It does not depend on k, so it can come out of the inner sum, the reverse of Step 3:
∑j=1p∑k=1nAikBkjxj=∑j=1p(∑k=1nAikBkj)xj.
Step 6. Compare with the row view for a single matrix C, (Cx)i=∑jCijxj. The two agree for every x exactly when every coefficient of xj matches (to see that they must, take x=ej, which leaves only the j-th term on each side):
Cij=∑k=1nAikBkj.
The index k runs over the columns of A and the rows of B at the same time, so those two counts must be equal. That is the shape rule: (m×n)(n×p) gives m×p, and the inner sizes must match. Shapes, transposes and batches turns this into a habit.
To recap: AB is "B, then A"; its columns are A times the columns of B; and its entries are rows of A dotted with columns of 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) uses row i of the left matrix and column j of the right one.
[1324][0110]
[0110][1324]
[1−10321]321110
Then say in words what multiplying by [0110] 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×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.
The formula (AB)ij=∑kAikBkj has three indices: i picks a row of A, j a column of B, and k runs along the shared inner dimension. The product is always the same collection of small multiplications AikBkj, one for every choice of i, j and k, 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 i and j and adds over k: every entry is a row of A dotted with a column of B. Use it to compute a single entry, or to read the product as a table of similarities: if the rows of A are one set of vectors and the columns of B are another, AB lists every pairwise dot product.
The column view fixes j: column j of the product is A times column j of B, which is where we started. If the columns of B are separate inputs, AB applies A to all of them in one operation. Its mirror image is the row view: row i of AB is row i of A times B. To check it, take entry j of that row: it is row i of A dotted with column j of B, which is (AB)ij by the entry rule.
The outer-product view fixes k, and it needs one new product first. For a column vector u with m entries and a row vector with p entries, written v⊤, the outer productuv⊤ is the m×p matrix whose entry (i,j) is uivj. (The ⊤ is the transpose, which turns the column v into a row; the next lesson treats it properly.) For example, with u=(1,2) and v=(3,4):
uv⊤=[12][34]=[1⋅32⋅31⋅42⋅4]=[3648].
Row 1 is 1 times (3,4) and row 2 is 2 times (3,4); column 1 is 3 times u and column 2 is 4 times u. Every row of an outer product is a multiple of v⊤ and every column is a multiple of u, which makes it the simplest kind of nonzero matrix; module 3 calls it rank one. The outer-product view says
AB=k=1∑n(column k of A)(row k of B).
The reason, in two moves. Entry (i,j) of the k-th outer product is (entry i of column k of A) times (entry j of row k of B), which is AikBkj. Adding the outer products over k therefore adds AikBkj over k in every entry at once, and that sum is (AB)ij. For our example, column k of S times row k of R, for k=1 and k=2:
The stepper below runs all three views on a non-square product, a 2×3 matrix A times a 3×2 matrix B, so you can watch the same 2⋅3⋅2=12 multiplications grouped three ways. The inner size is 3: a row of A and a column of B have 3 entries each. The lines in the empty top-left corner join column k of A to row k of B, for k=1,2,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.
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=[11−10]. Now shear first and rotate second, which is RS. Its columns are R applied to the columns of S. Column 1: R(1,0)=(0,1), the first column of R. Column 2: R(1,1)=1(0,1)+1(−1,0)=(−1,1). So
RS=[01−10][1011]=[01−11].
A different matrix. Follow ^ to see why. Rotating first turns it to (−1,0), which the shear leaves alone, because the shear slides points sideways in proportion to their height and (−1,0) has height 0. Shearing first slides it to (1,1), and the rotation then turns that to (−1,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, 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. Some pairs do commute. A uniform scaling kI commutes with every matrix: (kI)Ax=kAx, and A(kI)x=A(kx)=kAx by the scaling rule. Two rotations of the plane commute too: turning by 30∘ then 60∘ and turning by 60∘ then 30∘ both turn by 90∘. But never assume it.
The identity matrixI is the map that moves nothing. Its columns are the basis vectors themselves: I=[1001] in the plane, and in general ones on the diagonal and zeros everywhere else. Doing nothing before or after A changes nothing, so AI=IA=A. (If A is not square, the two identities have different sizes: for a 2×3 matrix, AI uses the 3×3 identity and IA the 2×2 one.)
Order matters, but grouping does not:
(AB)C=A(BC).
Both sides are the single map "apply C, then B, then A", so they are the same matrix. This property, associativity, is why we can write a long chain such as ABCDx 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. Layers and parameter counts works this out with biases included, and Neurons and layers builds on it.
Go slower: Associativity with indices
Let A be m×n, B be n×p and C be p×q.
Left grouping. Use the entry rule for the product of AB and C, then the entry rule again for (AB)il, and multiply Clj into the inner sum:
((AB)C)ij=∑l=1p(AB)ilClj=∑l=1p(∑k=1nAikBkl)Clj=∑l=1p∑k=1nAikBklClj.
Right grouping. The same three moves, with BC as the inner product:
(A(BC))ij=∑k=1nAik(BC)kj=∑k=1nAik(∑l=1pBklClj)=∑k=1n∑l=1pAikBklClj.
Compare. Both are the sum of AikBklClj over every pair (k,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 x-axis and then rotates a quarter turn counterclockwise. The reflection is F=[100−1] and the rotation is R=[01−10]. Enter the 2×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.
Grouping never changes the answer, but it can change the amount of work enormously. So we need to count.
Multiplying an m×n matrix by an n×p matrix produces mp entries. Each entry is a dot product of length n: n multiplications and n−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 n multiply-adds. So
cost of (m×n)(n×p)=mp entries×n multiply-adds each=mnp multiply-adds.
For two n×n matrices that is n⋅n⋅n=n3. Double the size and the work becomes (2n)3=8n3: eight times as much. A matrix times a vector is the case p=1 and costs mn.
Now the grouping. Let A and B be 1000×1000 and let x have 1000 entries, so it is a 1000×1 matrix.
(AB)x. Forming AB costs 1000⋅1000⋅1000=109 multiply-adds. Then the 1000×1000 result times x costs 1000⋅1000=106. Total: 1,001,000,000.
A(Bx). First Bx costs 106 and gives a vector. Then A times that vector costs another 106. Total: 2,000,000.
Same vector, about 1,001,000,000/2,000,000≈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 mnp 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×300 matrices. The exact times depend on your machine, but A(Bx) 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 is 1000×500, B is 500×2000, and x has 2000 entries. The groupings (AB)x and A(Bx) give the same vector. Count the multiply-adds of each grouping, then give the ratio: the cost of (AB)x divided by the cost of A(Bx). 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×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.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×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 for A=0−220−20 and B=[1−231−13].
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 does to a vector, why column j of AB is A times column j of B, and why entry (i,j) is row i of A dotted with column j of B. Then say why AB and BA usually differ.