How does associativity of matrix multiplication let you cut the cost of a three-matrix chain?

## The law For conformable matrices, `(AB)C = A(BC)`. The two sides are equal entry for entry, and the proof is a swap of summation order: entry `(i,l)` of either side is the double sum over `j` and `k` of `A[i,j]*B[j,k]*C[k,l]`, and finite sums may be reordered freely. Because the result is the same, the expression is usually written `ABC` with no brackets at all. It is worth being precise about what associativity does and does not permit. It permits **regrouping**: choosing which adjacent pair to multiply first. It does not permit **reordering**: the sequence of factors is fixed, because matrix multiplication is not commutative. `ABC` and `ACB` are different expressions, and may not even be conformable. ## Cost depends on the grouping Multiplying an `m x n` matrix by an `n x p` matrix produces `m*p` entries, each a dot product of length `n`, so the standard algorithm performs about `m*n*p` multiply-add operations. Both the output size and the shared inner dimension drive the count. Work a concrete chain. Let `A` be `10 x 100`, `B` be `100 x 5`, `C` be `5 x 50`. **Grouping one, `(AB)C`:** ``` AB : (10 x 100)(100 x 5) -> 10 x 5, cost 10*100*5 = 5,000 (AB)C : (10 x 5)(5 x 50) -> 10 x 50, cost 10*5*50 = 2,500 total ~ 7,500 ``` **Grouping two, `A(BC)`:** ``` BC : (100 x 5)(5 x 50) -> 100 x 50, cost 100*5*50 = 25,000 A(BC) : (10 x 100)(100 x 50) -> 10 x 50, cost 10*100*50 = 50,000 total ~ 75,000 ``` Ten times the work, and a `100 x 50` intermediate instead of a `10 x 5` one, for a bit-for-bit identical answer. The pattern generalises: the cheap grouping is the one that squeezes through the narrow dimension early, so the intermediate stays small. On longer chains the choice of the best parenthesisation becomes a genuine optimisation problem — there are many possible groupings, and the standard approach is dynamic programming over the sequence of dimensions. ## The rank-one case, where it matters most The most dramatic version involves an outer product. Let `u`, `v`, `x` all be column vectors of length `n`. Then `u v^T` is an `n x n` matrix, and the expression `(u v^T) x` is legal: ``` u v^T : (n x 1)(1 x n) -> n x n, cost ~ n^2, memory ~ n^2 (u v^T) x : (n x n)(n x 1) -> n x 1, cost ~ n^2 ``` Regroup instead: ``` v^T x : (1 x n)(n x 1) -> 1 x 1, cost ~ n u (v^T x) : scale the vector u by that single number, cost ~ n ``` About `2n` operations and no large intermediate, versus about `2n^2` operations plus an `n x n` array. For `n = 1,000` that is roughly two thousand operations against two million, and the memory difference is the more painful of the two: the naive grouping allocates a million numbers that the answer never needed. Recognising "I am building a big matrix only to hit it with a vector" is one of the most reliable performance wins in numerical work, and interviewers like it because it tests whether you read expressions structurally rather than left to right. ## Making the judgment in practice A workable procedure when you meet a chain: 1. Write the shape chain end to end and confirm every adjacent pair is conformable. 2. For each candidate grouping, multiply the three dimensions involved in each step and add up the totals. 3. Prefer the grouping that keeps intermediates smallest — especially one that reduces something to a scalar or a thin vector early. 4. Sanity-check memory separately from operation count; an intermediate that does not fit is a harder failure than one that is merely slow. 5. Only then think about whether the numbers are worth the change — for a chain evaluated once on small matrices, the difference is noise. That last point matters. Regrouping is free to try and costs nothing in correctness, but it earns its keep on the expressions in an inner loop, on the large dimensions, and where a materialised intermediate would dominate memory. Optimising a chain executed once on `3 x 3` matrices is wasted effort and clutters the expression. ## Caveats worth mentioning Associativity is exact in arithmetic but only approximate in finite precision: different groupings sum floating-point numbers in different orders and can return slightly different results in the last digits. This is almost never a correctness problem, but it does explain why two mathematically identical groupings can produce results that fail an exact-equality comparison, and it is a good detail to volunteer. Also remember the boundary: associativity licenses regrouping only. If your regrouping accidentally moved a factor across another, that is a different expression, and the shape chain will usually — though not always — catch it.