I.2Matrix-Matrix Multiplication AB

The one idea

AB can be computed four different ways, all giving the same matrix:

1. Entry by entry: row i of A dotted with column j of B. The version you were taught, and the least useful here.
2. Column by column: each column of AB is A times the corresponding column of B. This is just I.1 applied repeatedly.
3. Row by row: each row of AB is the corresponding row of A times B.
4. Columns times rows: the one that matters:

AB = a₁b₁ᵀ + a₂b₂ᵀ + ⋯ + aₙbₙᵀ

where aₖ is column k of A and bₖᵀ is row k of B.

Read that last one carefully. Each term aₖbₖᵀ is a column times a row, which produces a full-size matrix of rank one. So AB is not one indivisible object; it is a sum of rank-one layers, and there are only as many layers as the inner dimension.

Why it matters later

This decomposition is the skeleton of the whole book.

• The SVD (I.8) writes A = σ₁u₁v₁ᵀ + σ₂u₂v₂ᵀ + ⋯. That is exactly the columns-times-rows form, with the layers ordered so the most important comes first.
• Eckart-Young (I.9) then says: keep the first k layers and you have the best possible rank-k approximation. “Best” is only a meaningful claim because you already understand a matrix as a stack of rank-one pieces you can truncate.
• Randomized multiplication (II.4) samples a subset of those n layers instead of computing all of them. That only makes sense if you see AB as a sum you could sample from.
• Low-rank updates (III.1) modify a matrix by adding one such layer.

If you take one thing from Part I into Part III, take the habit of seeing a matrix as a sum of rank-one terms.

What to actually do

1. Take two 3×2 and 2×3 matrices. Compute AB the standard way. Then compute it as a₁b₁ᵀ + a₂b₂ᵀ and confirm you get the same 3×3 result.
2. Look at the rank of what you produced. Two rank-one matrices were added and the result is at most rank 2, even though it is a 3×3 matrix. Convince yourself why it can never be 3.
3. Count multiplications for an m×n times n×p product. You should get mnp, and you should get the same count whichever of the four ways you use. Same work, different bookkeeping.

Check yourself

• Why is aₖbₖᵀ always rank one, no matter how large the vectors are?
• If A is m×n and B is n×p, how many rank-one layers are in the sum, and what upper bound does that put on rank(AB)?
• Which of the four ways is most natural if B has only one column? If A has only one row?

Common sticking points

Mixing up aᵀb and abᵀ. The first is an inner product, a single number. The second is an outer product, a whole matrix. They are written almost identically and mean entirely different things. When you see a transpose in this book, check which side it is on before reading further.

Assuming rank adds. rank(A + B) is at most rank(A) + rank(B), but it can be less, and for products rank(AB) ≤ min(rank A, rank B). Multiplying can only lose rank, never create it. This is why low-rank structure survives through long chains of matrix operations, a fact Part III leans on heavily.

---

This is the second of the three sections MIT publishes in full. Read Strang’s version, then do step 1 above by hand. The columns-times-rows identity is worth being able to write from memory.