Matrices and Matrix Multiplication

In this lesson, we’ll build up matrix multiplication from what it means to what it costs. It is the operation sitting underneath almost every ML computation: a linear layer, an attention score, a covariance matrix, and a PCA projection are all matrix products. By the end you’ll be able to say when a product is defined, compute any entry of it by hand, and reason about how expensive it is to run.

Shapes and when the product exists

A matrix is a grid of numbers with a shape (rows × columns). Before we compute anything, we check whether the product is even legal, because that check catches most mistakes early. The product A B is defined only when the inner dimensions match: an (m × n) matrix times an (n × p) matrix yields an (m × p) matrix.

flowchart LR
  A["A<br/>(m x n)"] --> P["A B<br/>(m x p)"]
  B["B<br/>(n x p)"] --> P

The diagram captures a bookkeeping rule: the shared n is consumed, and the outer m and p survive. If the inner dimensions disagree, the product does not exist, full stop. This is the single most common source of bugs in ML code, so we track shapes at every step.

Naming what this forces: once we know a product is legal, we need to know what each of its entries actually is.

The definition

Entry (i, j) of the product is the dot product of row i of A with column j of B:

(AB)[i][j] = sum over k = 1..n of A[i][k] * B[k][j]

The intuition is worth stating before the formalism: a dot product multiplies two equal-length vectors element by element and sums the results, producing one number. So a matrix product is nothing more than a grid of dot products: we pair every row of A with every column of B, and each pairing fills in one cell.

Let’s watch it happen once with tiny numbers. Take row i of A equal to [1, 2] and column j of B equal to [3, 4]. The entry is 1*3 + 2*4 = 11, a single number that lands in cell (i, j). Do that for every row-column pair and the whole product is filled.

flowchart TD
  RowA["Row i of A<br/>(length n)"] --> Dot["Dot product<br/>sum of element-wise products"]
  ColB["Column j of B<br/>(length n)"] --> Dot
  Dot --> Entry["Entry (i, j) of A B<br/>(one number)"]

A useful special case is the matrix-vector product A x, which takes a vector and returns a new vector. This is exactly what a linear layer computes: y = W x + b maps an input vector to an output vector, and training learns the entries of W. That single fact is why matrix multiplication is worth this much attention, and it forces the next question: which algebraic rules carry over from ordinary numbers, and which do not.

Properties to keep straight

Numbers let you reorder and regroup freely; matrices do not, and interviewers probe exactly where the analogy breaks. Keep these straight:

Not commutative. A B and B A are generally different, and one may not even be defined. Order matters.
Associative. (A B) C = A (B C). You may regroup, which lets you pick the cheapest multiplication order.
Distributive. A (B + C) = A B + A C.
Identity. The identity matrix I (ones on the diagonal, zeros elsewhere) satisfies A I = I A = A.
Transpose. Flipping rows and columns reverses a product: (A B)^T = B^T A^T.

The one to internalize is associativity: regrouping never changes the answer, so we are free to choose the grouping that costs the least. That freedom only pays off once we know what a multiplication costs.

Cost

Multiplying (m × n) by (n × p) computes m·p output entries, each a dot product of length n, so the naive cost is O(m·n·p) multiply-adds. The reason is direct: there are m·p cells to fill, and filling each one runs a sum of n products. For two n × n matrices that is O(n³). Fast algorithms (Strassen and successors) lower the exponent below 3 but are rarely used in practice; real speedups come from hardware that runs the multiply-adds in parallel (GPUs, TPUs), which is why ML workloads are expressed as large matrix products in the first place.

The takeaway that forces the next section: because the real work is a flood of independent multiply-adds, we want to hand the hardware big regular arrays, and that means being careful about one operation that looks like multiplication but is not.

Broadcasting

Numerical libraries let you combine arrays of different shapes by broadcasting: a smaller array is virtually stretched to match a larger one along size-1 dimensions. Adding a bias vector of shape (p,) to a batch of outputs shaped (m × p) adds it to every row without an explicit loop. Broadcasting is not matrix multiplication, it is elementwise, but the two are constantly used together, so we keep the distinction clear. Mistaking one for the other produces a result with the wrong shape or, worse, a plausible-looking wrong answer.

Conclusion

A product A B exists only when the inner dimensions match; an (m × n) times an (n × p) gives an (m × p). Tracking shapes catches most bugs.
Each output entry is a dot product of a row of A with a column of B, so the whole product is a grid of dot products.
The product is associative and distributive but not commutative: order matters.
Naive cost is O(m·n·p) multiply-adds (O(n³) for square matrices). In practice parallel hardware, not a lower exponent, is what makes it fast, which is why ML work is cast as large matrix products.