Matrix Chain Multiplication

Associativity and Computational Cost

Matrix multiplication is associative, meaning (A₁ * A₂) * A₃ and A₁ * (A₂ * A₃) produce the exact same matrix result. However, multiplying an (a x b) matrix by a (b x c) matrix requires a * b * c scalar multiplications, so the choice of split points dramatically alters total arithmetic work.

Interval Dynamic Programming Recurrence

For matrices A_i of shape d_i-1 x d_i, let m[i, j] denote the minimum scalar multiplications needed to compute the subchain A_i...A_j. Base cases of length 1 satisfy m[i, i] = 0. For interval lengths L = 2, 3, 4 and split index k from i to j - 1, the recurrence evaluates m[i, j] = min(m[i, k] + m[k + 1, j] + d_i-1 * d_k * d_j). When ties occur, choosing the ASCII-lexicographically smallest parenthesized expression ensures a deterministic witness.

Worked Example

Consider four matrices with dimensions d₀ = 5, d₁ = 2, d₂ = 4, d₃ = 3, and d₄ = 6: A₁ (5x2), A₂ (2x4), A₃ (4x3), and A₄ (3x6).

1. Length 2 intervals: m[1, 2] = 5 * 2 * 4 = 40 (split k = 1); m[2, 3] = 2 * 4 * 3 = 24 (split k = 2); m[3, 4] = 4 * 3 * 6 = 72 (split k = 3).
2. Length 3 intervals: For A₁..A₃, k = 1 gives 0 + 24 + 5 * 2 * 3 = 54 and k = 2 gives 40 + 0 + 5 * 4 * 3 = 100, so m[1, 3] = 54 (k = 1). For A₂..A₄, k = 2 gives 0 + 72 + 2 * 4 * 6 = 120 and k = 3 gives 24 + 0 + 2 * 3 * 6 = 60, so m[2, 4] = 60 (k = 3).
3. Length 4 interval: For A₁..A₄, split k = 1 costs 0 + 60 + 5 * 2 * 6 = 120; split k = 2 costs 40 + 72 + 5 * 4 * 6 = 232; split k = 3 costs 54 + 0 + 5 * 3 * 6 = 144. The minimum cost is 120 with parenthesization (A1*((A2*A3)*A4)).

Experiment

Test how bottleneck interior dimensions vs outer dimensions drive optimal parenthesization in https://riano.app/module/matrix-chain-multiplication:

1. Start with default dimensions (5, 2, 4, 3, 6) and click Step six times to fill the three length-2 intervals, two length-3 intervals, and final length-4 interval in order.
2. Set alternating dimensions d₀ = 2, d₁ = 7, d₂ = 3, d₃ = 8, d₄ = 4 and click Finish to observe cost 154 and (((A1*A2)*A3)*A4).
3. Set all dimensions to 1 or all dimensions to 9 to verify tie breaking when every split candidate yields the exact same scalar multiplication count.

Limitations

This module evaluates the classical cubic-time O(n³) dynamic programming table for n = 4 matrices with integer dimensions in [1, 9] under standard textbook matrix multiplication cost, without Strassen fast matrix multiplication or hardware cache-hierarchy modeling.

Common Pitfalls

A common mistake is greedily picking the cheapest first multiplication or filling the DP table row-by-row instead of by increasing subchain length L. Because m[i, j] depends on shorter intervals m[i, k] and m[k + 1, j], computing intervals in increasing order of length is essential.

References

The interval dynamic programming recurrence and split-table reconstruction follow standard algorithm textbooks:

• OpenDSA: Dynamic Programming and Matrix Chain Multiplication