Motivation
Matrix multiplication is associative, so compatible matrices can be multiplied in different parenthesizations without changing the mathematical product. The number of scalar multiplications, however, can change dramatically. Dynamic programming avoids enumerating every parenthesization by recording the best cost for each consecutive interval. The state must retain both endpoints: a matrix in the middle of the chain can participate in many different subproblems with different dimensions and costs.
The objective in this unit counts scalar multiplications in the standard three-loop matrix multiplication algorithm. It does not count additions, memory traffic, numerical roundoff, or optimized hardware operations. An order optimal for this cost model need not be fastest in a real implementation.
Definitions
Definition 2.2.1
(Matrix chain and interval cost)
Let be matrices with , where has dimensions and every is a positive integer. Every consecutive product has dimensions regardless of its parenthesization. Multiplying an matrix by a matrix costs scalar multiplications in the standard algorithm.
For , let be the minimum cost of fully parenthesizing . A single matrix needs no multiplication, so . For , the last operation must split the interval after some with . Its two inputs are the products of the left and right consecutive subchains.
Theorems
Theorem 2.2.2
(Optimal substructure and recurrence)
For ,
Recording any minimizing split for each interval permits reconstruction of an optimal parenthesization.
Theorem 2.2.3
(Cost of the dynamic program)
Filling the table by increasing interval length evaluates candidate splits, uses arithmetic operations and table entries, and produces an optimal value. Storing a minimizing split for each interval uses another entries.
Proof sketch or proof idea
Proof
(Last split and optimal substructure)
Fix an interval and a last split . By associativity, the two operands are exactly the left and right subchain products. Their dimensions are and , so the last multiplication has the displayed cost independently of how either subchain was parenthesized. If an allegedly optimal full parenthesization used a nonoptimal left subchain, replacing it by a cheaper one would keep the same dimensions and final multiplication cost, contradicting optimality. The same argument applies to the right subchain.
Thus every parenthesization with last split costs at least the corresponding recurrence candidate. Conversely, choose optimal parenthesizations for the two strictly shorter subchains and multiply their results: this attains the candidate. Taking the minimum over all possible last splits proves equality. The argument is well founded by induction on interval length, starting with one matrix.
For reconstruction, save a minimizing for each interval. Recursively reconstruct the left and right intervals and put parentheses around their product. Each recursive call decreases interval length and therefore terminates. The recurrence proof shows that the reconstructed cost is the table value; ties may be broken arbitrarily and can yield different optimal parenthesizations.
Proof X-ray
Why replacement works
A subchain's result dimensions depend on its endpoints, not on its internal parentheses. Replacing it with a cheaper parenthesization therefore does not alter the cost of the last multiplication. That invariant is what makes the optimal-substructure argument valid. The hypothesis is used in exactly one place: the cost of the last multiplication must not depend on how either subchain was built. The argument closes by induction on interval length, because both subchains are strictly shorter and a single matrix is the base case with cost zero; ties do not matter, since only the minimum value is claimed. If the combining cost did depend on the internal construction, a cheaper subchain could be replaced by a dearer one that makes the last step cheaper, and the recurrence would no longer be an equality.
Proof
(Counting the candidate splits and table entries)
A length- interval has possible splits and there are such intervals. Their sum over equals : each candidate is uniquely represented by three indices , or equivalently three distinct cut positions from . The table has relevant entries. Filling increasing lengths ensures that both subproblems have already been computed. If dimensions are encoded in binary, the table entries can exceed a machine word; the arithmetic-operation count is not automatically a bit-complexity bound.
Worked examples
Worked example 2.2.4
(A dramatic choice of parentheses)
Let dimensions be , , and . Multiplying the first two and then the third costs . Multiplying the last two first costs . Both results have dimensions , but the first order uses one tenth as many scalar multiplications.
Worked example 2.2.5
(A four-matrix table)
Take dimensions . Length-two costs are , , and . For length three, and . Finally the three candidates for are , , and . The optimum is , with split : .
Worked example 2.2.6
(A tie)
If all three matrices are , either parenthesization costs . Both last splits are minimizers. Saving the first minimizing index gives one correct answer; the algorithm is not required to list every optimum.
Common mistakes
Counterexample mode
Choose the cheapest immediate product
Take dimensions . The unique cheapest initial adjacent product is , costing . After this multiplication the remaining dimensions are ; the cheapest next product costs , and the last multiplication costs , for total . Instead, multiplying first costs and leaves dimensions . Multiplying the first two remaining matrices then costs , and the last multiplication costs . The total is . Therefore selecting the cheapest immediate product is not always optimal; the recurrence considers every possible last split.
Common mistake
(Mixing up the dimension at the split)
In the candidate for an interval split after , the last multiplication has operand dimensions and , so its cost is , not . For with dimensions and , the only split is and the cost is ; using would give , which is not a product of matching dimensions. The outer dimensions of a subchain are fixed by its endpoints. Also, a table entry is a cost, not a matrix: to obtain the product, reconstruct the order and then execute the multiplications.
Filling the table without missing dependencies
Initialize every diagonal entry to zero. Then process lengths . For each start index from through , set and evaluate every split . Both subintervals have length smaller than , so their entries are available. Set to the smallest candidate and store an index attaining it. The answer is . When , the loops over lengths do not execute and the answer is the already initialized zero.
The order of entries within a fixed length is irrelevant because they depend only on shorter intervals. In contrast, filling rows from left to right without checking dependencies can read an entry that has not yet been computed. A dependency graph makes this visible: draw an edge from each state to the states needed by a candidate. Every such edge points to shorter intervals, so interval length is a topological ordering. The recurrence is not a circular definition even though it refers to the same table.
Worked example 2.2.7
(Reconstructing from stored splits)
In the four-matrix example, the stored split for is . Recursing gives intervals and ; each has only one possible split. The reconstruction therefore prints . To check it independently, the first two intermediate costs are and , and their result dimensions are and . The final multiplication costs , so the sum is , agreeing with the table.
A cost table alone can sometimes be used to recover a split by recomputing candidates and finding one that matches the stored minimum. Saving splits avoids that extra search and makes tie handling explicit. When multiple split indices attain the same cost, any one is sufficient to reconstruct one optimum. Listing all optimal parenthesizations is a different output problem: their number can be very large even though the cost table is quadratic in size.
Why a local choice is insufficient
The cheapest adjacent multiplication looks attractive because its cost is known immediately. But the product has new dimensions and changes the cost of later multiplications. In the counterexample above, the cheapest first step leaves a less favorable pair of dimensions. An exchange argument would need to show that replacing the first step of some global optimum by the cheapest adjacent pair never increases the total future cost. The explicit counterexample proves that such a general argument cannot exist for this rule.
The dynamic program avoids guessing the first step. Instead it classifies complete parenthesizations by their last multiplication. Once that split is fixed, the dimensions of both resulting subproducts are known, making the final charge independent of their internal order. The recurrence pays for both subproblems and the final multiplication before comparing candidates. This is the precise reason its local comparison is safe, while comparing immediate multiplication costs alone is not.
The number of possible fully parenthesized products grows rapidly with , but the number of intervals is only quadratic. Many candidate full parenthesizations use the same interval, so tabulation reuses its optimum instead of solving it repeatedly. The cubic operation count includes all split choices for all intervals; it does not require enumerating all complete parenthesizations. Memoized recursion with the same states and recurrence has the same asymptotic state and split count if every state is computed at most once.
Inputs and model limits
The dimensions must match in the original order: the number of columns of must equal the number of rows of . If not, the full product is undefined and this recurrence does not repair the input.
Common mistake
(Reordering the matrices to save multiplications)
Associativity lets the parentheses move but not the matrices. Let be and be : the product is defined and has size , but is not defined, since has columns and has rows. Sorting the chain by size therefore changes the problem or makes it meaningless; the recurrence only chooses the parentheses for the given order.
The counts use the standard cost for multiplying and matrices. Other multiplication algorithms or a model that charges additions differently can change the recurrence's local cost. The same dynamic-programming structure remains valid only when the replacement property survives: the relevant result size and the cost of combining subresults must depend on information included in the state. With numerical floating-point arithmetic, changing parentheses can also change the rounded result even though exact matrix multiplication is associative. The notes optimize the exact algebraic product under the declared scalar-multiplication model.
The cubic operation bound assumes arithmetic on table entries has unit cost. If input dimensions are large, each cost is an integer potentially much larger than any dimension. Exact comparison and addition then have bit costs depending on their lengths. The recurrence remains correct with arbitrary-precision integers; the machine model affects only the running-time accounting. This distinction is useful whenever a numeric parameter is supplied in binary rather than as an actual list of that many objects.
Understanding the count of candidates
There is a useful direct way to see the binomial coefficient. Represent a candidate by the three cut positions , chosen from with . Conversely, any three increasing cut positions determine exactly one interval and one valid split. Hence the candidate count is the number of three-element subsets of positions. For this yields ten, matching the explicit count of three length-two, four length-three and three length-four candidates. The count covers comparison candidates, not scalar multiplications used to evaluate the actual matrix product.
Concept lensCombinatorial
Parenthesizations as triangulations of a polygon
For , place the cut positions as the vertices of a convex polygon with vertices. Matrix corresponds to the side joining vertices and , and one closing side joins and . A full parenthesization of is then a triangulation of the polygon: the last split of an interval after is the triangle with vertices , whose cost is exactly , and the two subchains are the two sub-polygons cut off by the sides and . The total cost of a parenthesization is the sum of over its triangles, so the recurrence is the standard recurrence for a minimum-weight triangulation, and the three-element subsets of counted above are exactly the possible triangles.
When implementing the minimum, an interval has at least one candidate because its length exceeds one. Initialize its best value to the first candidate, then compare the remaining candidates; the diagonal is handled separately. This avoids confusing an uninitialized table value with a legitimate zero cost. Positive dimensions ensure that any nontrivial multiplication has positive cost in this model, although the algorithm does not need that positivity for its induction once valid local costs are given.
The proof also explains why the same general technique applies to other interval problems only after the state is chosen carefully. If the cost of combining two subsolutions depended on a hidden property that changed with their internal construction, storing only the cheapest cost could discard a more expensive subsolution that enables a much cheaper later combination. Here no such hidden dimension exists: every parenthesization of yields the same matrix dimensions. That fact should be established before writing the recurrence, not assumed as a consequence of the recurrence itself.
Summary
Every parenthesization has a final split. The two resulting subchains can be optimized independently because their result dimensions are fixed by their endpoints. Increasing interval length computes the recurrence in cubic arithmetic operations, and recorded splits reconstruct an optimal order.
Exercises
Quick check
(Compute both costs for dimensions and choose an optimum.)
Compute the cost of each of the two parenthesizations separately.
Solution · Answer
Left first costs ; right first costs . Left first is optimal.
Quick check
(What is and why?)
Recall what the recurrence says about an interval containing one matrix.
Solution · Answer
It is zero because one matrix is already its own product and no scalar multiplication is needed.
Quick check
(How many split candidates does the table evaluate when ?)
Count the candidates for each interval length and add.
Solution · Answer
The count is : three candidates for intervals of length two, four for length three, and three for length four.
Quick check
(If every matrix is , what is the cost of any full parenthesization of matrices?)
Count the binary multiplications first.
Solution · Answer
Every full parenthesization uses exactly binary matrix multiplications, each costing , so the total is .