Matrix Multiplication

Matrix multiplication builds a grid of dot products: entry C[i][j] of C = AB is row i of A dotted with column j of B. That one rule forces everything else. The product exists only when A's rows and B's columns have the same length, an (m×n)(n×p) product costs m·n·p multiplications, and BA is usually a different grid.

The row-times-column rule looks arbitrary the first time you see it, as if someone flipped a coin over which index goes where. It isn't. A row of A is one input, a column of B is one set of weights, and their dot product is the score from the previous lesson. Matrix multiplication just computes all of those scores at once: every input against every set of weights, laid out so that row i and column j meet at cell (i, j). Once you read it that way, the shape rule stops being a rule to memorize. A dot product needs two lists of the same length, and that's all the shape rule says.

How Matrix Multiplication Works

Put A on the left and B above the spot where the answer will go. Row i of A now runs straight across into row i of C, and column j of B runs straight down into column j of C. The cell where they cross is C[i][j], and its value is the dot product of the two: walk the row and the column together, multiply the k-th entry of one by the k-th entry of the other, and add.

$$C_{ij} = \sum_{k=0}^{n-1} A_{ik},B_{kj}$$

Three facts fall out of this:

• The inner sizes must match. The row has as many entries as A has columns (n); the column has as many entries as B has rows. Those two lists are zipped together term by term, so they must be the same length. If they aren't, some entry has no partner and the product does not exist.
• The outer sizes give the shape. C gets one row for each row of A and one column for each column of B: (m×n)(n×p) is m×p. The shared n disappears into the sums.
• Order matters. BA pairs B's rows with A's columns, a different set of lists entirely. It may have a different shape, it may not exist at all, and when it does exist with the same shape, its numbers are usually different. AB = BA is the exception, not the rule: it happens for special pairs such as B = I (the identity) or B = A.

In a neural network the same picture has names. Stack a batch of inputs as the rows of X and a layer's weight vectors as the columns of W; then XW holds every input's score under every weight vector, one dot product per cell. That is what a linear layer computes before its bias and activation.

Matrix Multiplication Step by Step

The default input is A (2×3) = [[1, 2, 3], [4, 0, 1]] and B (3×2) = [[2, 1], [1, 0], [3, 2]]. Indices start at 0, as in NumPy and PyTorch.

1. Check the shapes. A's rows have 3 entries and B's columns have 3, so they pair up: 3 = 3. The outer sizes give C's shape, 2×2, and an empty 2×2 grid appears where A's rows and B's columns cross.
2. Line up the first cell. C[0][0] needs row 0 of A, (1, 2, 3), and column 0 of B, (2, 1, 3). Copies of both fly into the workbench and pair up entry by entry.
3. Multiply term by term. 1 × 2 = 2, running sum 2. Then 2 × 1 = 2, running sum 4. Then 3 × 3 = 9, running sum 13. The multiplication counter reads 3 of 12.
4. Write the cell. The sum lands in C[0][0] = 13. One cell, one dot product.
5. Sweep the rest of C. The same rule fills each remaining cell in row order. C[0][1] keeps row 0 and moves to column 1: 1×1 + 2×0 + 3×2 = 7. C[1][0] = 4×2 + 0×1 + 1×3 = 11. C[1][1] = 4×1 + 0×0 + 1×2 = 6. The zero in A still costs a multiplication.
6. Read the product. AB = [[13, 7], [11, 6]]: 4 cells × 3 terms = 12 multiplications.
7. Swap the order. A and B trade places: B moves to the left and A to the top, and the finished AB grid parks to the side. Now B's rows (2 entries) meet A's columns (2 entries): 2 = 2, so BA exists, and it is 3×3.
8. Fill BA. Nine cells, each a dot product of length 2: BA = [[6, 4, 7], [1, 2, 3], [11, 6, 11]], at 18 multiplications.
9. Compare. AB is 2×2 at 12 multiplications; BA is 3×3 at 18. Same two matrices, swapped order, a different grid. AB ≠ BA.

On the canvas, watch the two outlined bands: one across a row of the left matrix, one down a column of the top matrix. Dashed guides run from each band to the cell being computed, where the two lines of sight meet. Above the stage, the header counter climbs by n with every cell until it reaches m·n·p.

Time and Space Complexity

The time complexity of the textbook method is O(m·n·p): one dot product of length n for each of the m·p cells. For square n×n matrices that is O(n³), so doubling n makes the product eight times as much work. Algorithms such as Strassen's lower the exponent below 3 by trading multiplications for extra additions, but practical libraries mostly run the plain method, blocked and vectorized for the hardware. GPUs and TPUs run it fast because it is so regular: thousands of independent dot products, no branches.

The order of a product also changes its cost. For the default input, AB takes 12 multiplications and BA takes 18, because the shared inner size moves from 3 to 2 while the output grows from 4 cells to 9. In a chain like ABC, where you put the parentheses changes the total work even though the answer is the same, and choosing them well is a classic dynamic-programming problem. The everyday version of the rule: multiply toward the narrow side first. For n×n matrices A and B and a vector v, A(Bv) costs 2n² multiplications, while (AB)v costs n³ + n².

Edge Cases

• Mismatched inner sizes. A (2×3) times B (2×2) pairs a 3-entry row with a 2-entry column; the third entry has no partner, so AB does not exist. Flip the order and B (2×2) times A (2×3) works, giving a 2×3 result. The shape-error preset shows both.
• A batch through a layer. X (4×3) times W (3×2) gives 4 inputs × 2 scores. WX would need 2 = 4 and fails: this is the mat1 and mat2 shapes cannot be multiplied error PyTorch raises when the operands are written in the wrong order.
• Row times column, column times row. A 1×3 row times a 3×1 column is a single number, the dot product (13 in the row-times-column preset). The same vectors in the other order give a 3×3 grid, the outer product, at 9 multiplications and no additions.
• Same shape, still different. For A = [[1, 2], [3, 4]] and the swap matrix B = [[0, 1], [1, 0]], AB swaps A's columns while BA swaps A's rows. Both are 2×2 and cost 8 multiplications, and they disagree in every cell.
• Commuting pairs. If AB and BA really are equal (B = I, B = A, or two 1×1 matrices), the comparison says so instead of claiming they differ.

Common Mistakes

• Multiplying entry by entry. NumPy's A * B multiplies elementwise and accepts different shapes when they are broadcast-compatible. With equal shapes, this is the Hadamard product. The matrix product is A @ B.
• Pairing row with row. Computing C[i][j] from row i of A and row j of B gives A·Bᵀ, which needs A and B to have the same number of columns. It is a real operation (attention's QKᵀ is exactly this), just not AB.
• Assuming AB = BA. Reordering a product silently changes the result, even when the shapes happen to allow it. Keep the order from the math, and transpose explicitly when you mean to.
• Checking the wrong sizes. The sizes that must agree are the inner ones, A's column count and B's row count. Matching the outer ones (A's rows with B's columns) is a frequent off-by-a-transpose bug.
• Reading the counter as additions. Each cell of length n needs n multiplications but only n − 1 additions; the canvas counts multiplications, m·n·p in total.