Does the method change the order of the matrices?

No. It changes parentheses while preserving their sequence.

Is the cheapest arithmetic plan always the fastest in practice?

No. The cost model is a guide that should be checked against the implementation.

Does the planner need the numerical entries?

The classical dense multiplication-count model needs only compatible dimensions.

AI Glossary / Mathematics and optimization / Intermediate

Matrix chain multiplication

Definition

Matrix chain multiplication is the problem of choosing how to place parentheses in an ordered product of compatible matrices so that evaluating the product has minimum cost under a specified model. The classical model counts scalar multiplications for ordinary dense matrix multiplication. The order of the matrices stays fixed; the choice concerns which adjacent subproducts are computed first.

What it means

The expressions (AB)C and A(BC) represent the same matrix in exact arithmetic. Their intermediate matrices can have very different sizes, however, which changes how much arithmetic is needed. Parenthesization is therefore a computational planning decision.
This is useful whenever an expression contains several consecutive matrix products. It is not permission to rearrange A, B, and C, and it does not apply across arbitrary nonlinear operations between products. In floating-point arithmetic, different evaluation orders can also produce slightly different rounded answers, even though the underlying exact expression is unchanged.

How it works

For matrices with dimensions p_0-by-p_1, p_1-by-p_2, and so on, consider a subchain from matrix i through matrix j. If its final multiplication splits after k, the left result has shape p_(i−1)-by-p_k and the right result has shape p_k-by-p_j. Combining them costs p_(i−1)p_kp_j scalar multiplications in the classical model.
A dynamic program stores the cheapest cost for each consecutive subchain. A single matrix has cost zero. For longer subchains, compare every possible final split: the cost of its left part, plus its right part, plus the final multiplication. Recording the winning splits reconstructs a complete plan. This familiar implementation takes cubic planning time in the number of matrices and quadratic storage; it is not the fastest known algorithm for the classical problem.

Three practical examples

A numerical application can choose a cheaper evaluation order for several dense linear transformations applied together.
An analytics developer can avoid forming an unnecessarily large intermediate matrix when a product ends with a narrow matrix or vector.
A compiler or numerical library can plan repeated matrix expressions using known dimensions, then evaluate the selected sequence on actual data.

Think of it this way

Think of an assembly sequence in which combining two parts creates a temporary component of a particular size. A good sequence avoids building an oversized component when a smaller intermediate would suffice. The analogy stops at the fixed matrix order: arbitrary rearrangement of the original components is generally invalid, even if it appears convenient.

Worked example

Consider an original chain with A of size 8-by-60, B of size 60-by-3, and C of size 3-by-20. First evaluate (AB)C. Forming AB costs 8×60×3=1,440 scalar multiplications and creates an 8-by-3 intermediate. Multiplying that result by C costs 8×3×20=480. The total is 1,920.
Now evaluate A(BC). Forming BC costs 60×3×20=3,600 and creates a 60-by-20 intermediate. Multiplying A by that result costs 8×60×20=9,600. The total is 13,200. Both plans produce an 8-by-20 final matrix, but the first uses 11,280 fewer scalar multiplications under the stated model.
The intermediate contains 24 entries in the first plan and 1,200 in the second. Those are intermediate sizes, not complete peak-memory measurements, because input storage, output storage, temporary buffers, and the execution schedule also matter.
For a four-matrix extension, append D of size 20-by-2. The five possible parenthesizations have costs 2,240 for ((AB)C)D, 13,520 for (A(BC))D, 1,608 for (AB)(CD), 6,960 for A((BC)D), and 1,440 for A(B(CD)). The last plan wins: CD costs 120, B(CD) costs 360, and the final multiplication costs 960. A plan that was best for the first three matrices therefore need not describe how the full expression should begin.

Illustrative case study

In a fictional research consultancy, a nightly calculation repeatedly evaluates the four-matrix expression above. An engineer first records the dimensions and compares all five plans. The team then benchmarks the chosen plan using its actual numerical library and checks the resulting values within an appropriate tolerance. This separates the arithmetic argument from the deployment measurement. The case is illustrative; the operation counts do not represent observed runtime or a promised reduction in cloud charges.

Common misconceptions and mistakes

A common mistake is treating fewer scalar multiplications as a guaranteed proportional speedup. Hardware, memory traffic, parallel execution, and optimized kernels can change actual timing. Sparse matrices introduce further considerations because dimensions alone do not describe their computational cost.
Another mistake is selecting the cheapest immediate pair and assuming that choice must be globally optimal. Intermediate dimensions influence later work, so the complete chain matters. Finally, the textbook cubic dynamic program should not be described as the best possible planning complexity; specialized faster algorithms exist for the classical cost model.

Business use

For a business team, the practical value is reducing unnecessary computation in a repeated numerical workflow. Record the dimensions, data types, expected sparsity, and accuracy requirements before changing evaluation order. Measure end-to-end performance on representative inputs. A modest planning cost can be worthwhile when the same shapes recur, but that decision depends on the workload and the execution environment.

Check your understanding

Why does the best plan for the four-matrix example start with CD?

Answer: That multiplication creates a small 3-by-2 result, keeping the subsequent products narrow and bringing the total cost to 1,440.

Related terms

Dynamic programming
Computational complexity
Sparse matrix
Matrix multiplication
Associativity
Floating-point arithmetic
Tensor contraction

Learn next

Change D to size 20-by-100 and recalculate the five costs. Observe how changing only the final dimension can change which intermediate shapes are attractive.

Sources

Primary sources: López, Karlsson, and Bientinesi, original matrix-chain research: https://arxiv.org/html/2303.17352v2 . Official NumPy documentation for automatic product parenthesization: https://numpy.org/doc/stable/reference/generated/numpy.linalg.multi_dot.html . Numerical examples here are original.

Previous: Matrix calculus Next: Matrix Chernoff bound