Difficulty: Advanced | Prerequisites: Dynamic programming basics, matrix multiplication dimensions, recurrence relations
Matrix chain multiplication is the textbook dynamic programming problem. The standard version asks for the minimum number of scalar multiplications; this exam question flips it and asks for the maximum. The DP structure is identical, only the optimisation direction changes (take max instead of min). This topic sits at the heart of COSC 3320's dynamic programming unit and connects to optimal substructure, overlapping subproblems, and bottom-up table filling. If you have not yet studied the standard (minimum) version, do that first.
Given a chain of matrices, different parenthesisations lead to different numbers of scalar multiplications. The DP table S[i,j] stores the maximum cost of multiplying matrices i through j. You fill it diagonally (increasing chain length) and trace back to find the worst parenthesisation. For the exam problem M(9x3) * M(3x9) * M(9x1) * M(1x8) * M(8x4), the maximum is 1,251 scalar multiplications.
Matrix chain multiplication
The problem of determining the most (or least) expensive order to multiply a sequence of matrices. The matrices themselves do not change; only the grouping (parenthesisation) changes. Think of it as choosing where to put the brackets.
Parenthesisation
A way of grouping a chain of matrix multiplications using brackets. Different parenthesisations yield the same result matrix but require different numbers of scalar multiplications.
Scalar multiplication
A single multiply operation between two numbers. Multiplying an (a x b) matrix by a (b x c) matrix requires a x b x c scalar multiplications.
S[i,j] (the DP table)
The entry storing the maximum (or minimum, in the standard version) number of scalar multiplications needed to compute the product of matrices i through j. S[i,i] = 0 because a single matrix requires no multiplication.
Optimal substructure
The property that the optimal solution to the whole problem contains optimal solutions to its subproblems. In simple terms, the best (or worst) way to multiply a chain includes the best (or worst) way to multiply each sub-chain.
For matrices M1, M2, ..., Mn with dimensions n1 x n2, n2 x n3, ..., nn x n(n+1):
S[i,i] = 0 for all i (base case)
S[i,j] = max over k from i to j-1 of: (n_i * n_(k+1) * n_(j+1) + S[i,k] + S[k+1,j])
This is identical to the standard minimum version, except "min" is replaced with "max."
The chain is M(9x3) * M(3x9) * M(9x1) * M(1x8) * M(8x4).
Dimensions: n1=9, n2=3, n3=9, n4=1, n5=8, n6=4.
Label the matrices 1 through 5.
Diagonal 1 (chains of length 2):
S[1,2] = 9 x 3 x 9 = 243
S[2,3] = 3 x 9 x 1 = 27
S[3,4] = 9 x 1 x 8 = 72
S[4,5] = 1 x 8 x 4 = 32
Diagonal 2 (chains of length 3):
S[1,3]: k=1 gives 9x3x1 + 0 + 27 = 54; k=2 gives 9x9x1 + 243 + 0 = 324. Max = 324
S[2,4]: k=2 gives 3x9x8 + 0 + 72 = 288; k=3 gives 3x1x8 + 27 + 0 = 51. Max = 288
S[3,5]: k=3 gives 9x1x4 + 0 + 32 = 68; k=4 gives 9x8x4 + 72 + 0 = 360. Max = 360
Diagonal 3 (chains of length 4):
S[1,4]: k=1 gives 9x3x8 + 0 + 288 = 504; k=2 gives 9x9x8 + 243 + 72 = 963; k=3 gives 9x1x8 + 324 + 0 = 396. Max = 963
S[2,5]: k=2 gives 3x9x4 + 0 + 360 = 468; k=3 gives 3x1x4 + 27 + 32 = 71; k=4 gives 3x8x4 + 288 + 0 = 384. Max = 468
Diagonal 4 (full chain):
S[1,5]: k=1 gives 9x3x4 + 0 + 468 = 576; k=2 gives 9x9x4 + 243 + 360 = 927; k=3 gives 9x1x4 + 324 + 32 = 392; k=4 gives 9x8x4 + 963 + 0 = 1251. Max = 1,251
S[1,5] achieves its max at k=4, splitting into S[1,4] and S[5,5]:
(M1 * M2 * M3 * M4) * (M5)
S[1,4] achieves its max at k=2, splitting into S[1,2] and S[3,4]:
((M1 * M2) * (M3 * M4)) * (M5)
The worst parenthesisation is ((M(9,3) * M(3,9)) * (M(9,1) * M(1,8))) * M(8,4) with 1,251 scalar multiplications.
M(9,3) * M(3,9) = 9 x 3 x 9 = 243 multiplications, producing M(9,9)
M(9,1) * M(1,8) = 9 x 1 x 8 = 72 multiplications, producing M(9,8)
M(9,9) * M(9,8) = 9 x 9 x 8 = 648 multiplications, producing M(9,8)
M(9,8) * M(8,4) = 9 x 8 x 4 = 288 multiplications, producing M(9,4)
Total: 243 + 72 + 648 + 288 = 1,251
S[i,j] = \max_{i \le k < j} \bigl( n_i \cdot n_{k+1} \cdot n_{j+1} + S[i,k] + S[k+1,j] \bigr)S[i,i] = 0 \quad \text{for all } iThe first formula is the recurrence for the maximum-cost version. For each possible split point k, compute the cost of the resulting multiplication plus the cost of each sub-chain. Take the maximum across all k. The second formula is the base case: a single matrix has zero multiplication cost.
Matrix chain ordering matters in scientific computing, computer graphics (composing transformation matrices), and machine learning (chaining linear layers). Choosing the wrong order for a chain of large matrices can make a computation take hours instead of minutes. The same DP structure appears in optimal binary search tree construction and polygon triangulation.
Students often forget to change "min" to "max" for the maximum-cost version. The table structure, base cases, and filling order are all identical; only the comparison operator changes.
A common mistake is confusing the dimension indices. For a matrix M(a x b), the number of rows is a and the number of columns is b. When multiplying M(a x b) by M(b x c), the cost is a x b x c, not a x c.
Students sometimes fill the table row by row instead of diagonal by diagonal. The table must be filled by increasing chain length (diagonal by diagonal) because S[i,j] depends on shorter sub-chains.
Forgetting the traceback is a frequent exam error. The question asks for the parenthesisation, not just the number. You need to record which k gave the max at each S[i,j].
This was worth 25% of the exam. Expect to fill in the entire DP table and show all intermediate calculations.
The exam may ask for maximum or minimum. Read the question carefully.
Verification (multiplying out the final parenthesisation and checking the total) is a good way to catch arithmetic errors and can earn partial credit even if the table has mistakes.
True or False: S[i,i] = 1 for all i in the matrix chain DP table.
Fill in the blank: To multiply an (a x b) matrix by a (b x c) matrix requires ___ scalar multiplications.
True or False: The DP table for the maximum version is filled in the same order as the minimum version.
Fill in the blank: For five matrices in a chain, the full-chain answer is stored in S[,].
Q: For the chain M(2x3) * M(3x4) * M(4x2), compute S[1,3] for the maximum-cost version.
A: S[1,2] = 2x3x4 = 24. S[2,3] = 3x4x2 = 24. S[1,3] at k=1: 2x3x2 + 0 + 24 = 36. At k=2: 2x4x2 + 24 + 0 = 40. Max = 40.
Q: Why does the order of multiplication matter if the result is the same matrix?
A: Matrix multiplication is associative (the result is the same regardless of grouping) but the number of arithmetic operations changes dramatically with different groupings. A poor grouping can cost orders of magnitude more computation.
Q: In the exam problem, what is the worst parenthesisation and how many scalar multiplications does it require?
A: ((M(9,3) * M(3,9)) * (M(9,1) * M(1,8))) * M(8,4), requiring 1,251 scalar multiplications. The split at k=4 for the full chain, then k=2 for the left sub-chain of length 4.
Q: How do you verify the final answer?
A: Multiply out the parenthesised chain step by step, computing the cost and resulting dimensions at each step, then sum all costs. This should match S[1,n].
This is the quintessential dynamic programming problem and connects to every other DP topic in the course (optimal BST, longest common subsequence, knapsack). The table-filling and traceback pattern is reused in all of them. It also connects to the virtual memory question on this exam: matrix multiplication is one of the operations most affected by memory access patterns, so the page transfer analysis from Question 2 becomes relevant when these multiplications are carried out on real hardware.
Matrix chain multiplication, matrix chain ordering, parenthesisation, optimal parenthesisation, worst parenthesisation, scalar multiplications, dynamic programming, DP table, bottom-up DP, optimal substructure, overlapping subproblems, traceback, COSC 3320, algorithm design