Matrix Chain Order: DP Recurrence, Table and a 4-Matrix Worked Example

Multiplying compatible matrices in different valid orders gives the same final matrix, but the scalar-multiplication work can differ sharply. A correct-looking left-to-right calculation may therefore be far from the cheapest one. The chain A1: 5 x 10, A2: 10 x 3, A3: 3 x 12, A4: 12 x 5 has five parenthesizations; the DP tables recover (A1A2)(A3A4) as the order with cost 405. We choose an order only, not calculate the matrix entries.

Matrix Chain Order: what is being optimised

A compatible chain A1, A2, ..., An is represented by a dimension array p[0..n], where Ai has size p[i-1] x p[i]. Here, p = [5, 10, 3, 12, 5], which gives the four dimensions listed above.

Multiplying an r x s matrix by an s x t matrix costs r*s*t scalar multiplications and produces an r x t matrix. Thus, A1A2 costs 5*10*3 = 150 and produces 5 x 3. Similarly, A2A3 costs 10*3*12 = 360 and produces 10 x 12.

Associativity makes every full parenthesization return the same 5 x 5 result. Multiplication is not commutative, so the matrices cannot be reordered. Every order uses n-1 matrix-matrix multiplications; we minimise their scalar cost.

Why Matrix Chain Order parenthesization matters

Four matrices have C3 = 5 full parenthesizations. Their costs are:

The best costs 405, the worst 1260, though both use three matrix-matrix multiplications and produce 5 x 5.

The search space is the Catalan number C(n-1): six matrices have 42 orders, and ten have 4862. Exhaustive evaluation grows quickly and repeats contiguous subchains.

The Matrix Chain Order recurrence and optimal substructure

Let m[i,j] be the minimum scalar cost for Ai...Aj. A single matrix needs no multiplication, so m[i,i] = 0. If the final split is after Ak, the left result has size p[i-1] x p[k], the right result has size p[k] x p[j], and joining them costs p[i-1]*p[k]*p[j].

The recurrence is:

m[i,j] = min over i <= k < j of {m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]}

A second table, s[i,j], stores the best split k. Every top-level parenthesization has one final split, so trying every k covers all possibilities.

If an optimum used a non-optimal subchain, replacing that part with a cheaper order would reduce the total, a contradiction. Intervals also overlap across choices. For the shared foundations of optimal substructure and overlapping subproblems, see Dynamic Programming Explained: 0/1 Knapsack. Its take-or-skip state differs from the interval-and-split state used for matrix chains here.

Fill the Matrix Chain Order DP table

Initialise the length-1 diagonal to zero, then process L = 2, 3, 4, ensuring shorter intervals are ready first.

For length 2:

• m[1,2] = 5*10*3 = 150, so s[1,2] = 1.

• m[2,3] = 10*3*12 = 360, so s[2,3] = 2.

• m[3,4] = 3*12*5 = 180, so s[3,4] = 3.

For length 3, m[1,3] has candidates 0 + 360 + 5*10*12 = 960 at k=1, and 150 + 0 + 5*3*12 = 330 at k=2. Hence m[1,3] = 330 and s[1,3] = 2. For m[2,4], the candidates are 0 + 180 + 10*3*5 = 330 at k=2, and 360 + 0 + 10*12*5 = 960 at k=3. Hence m[2,4] = 330 and s[2,4] = 2.

For length 4, the three m[1,4] candidates are:

• k=1: 0 + 330 + 5*10*5 = 580

• k=2: 150 + 180 + 5*3*5 = 405

• k=3: 330 + 0 + 5*12*5 = 630

Therefore, m[1,4] = 405 and s[1,4] = 2.

The non-diagonal split values are s12=1, s23=2, s34=3, s13=2, s24=2, and s14=2.

Reconstruct the optimal order and verify 405

Read the split table recursively. s[1,4] = 2 divides at A1...A2 and A3...A4; s[1,2] = 1 and s[3,4] = 3 then give (A1A2)(A3A4).

The dimensions verify it: (5x10)(10x3) -> 5x3, and (3x12)(12x5) -> 3x5. The root is (5x3)(3x5) -> 5x5. Its independent cost check is 150 + 180 + 5*3*5 = 150 + 180 + 75 = 405, matching both m[1,4] and the five-order table.

The m table gives the minimum cost; s recovers an optimal parenthesization. With tied splits, store one for one optimum or all to enumerate every optimum.

Matrix Chain Order algorithm and complexity

The bottom-up algorithm is compact:

set m[i,i] = 0 for every i
for L from 2 to n
  for each valid i, set j = i + L - 1
    try every k from i to j - 1
      candidate = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
      if candidate improves m[i,j], update m[i,j] and s[i,j]

There are O(n^2) intervals and up to O(n) splits each, giving O(n^3) time and O(n^2) table space. Reconstruction follows a binary tree with n leaves, taking O(n) output work. Top-down memoisation uses the same states and recurrence.

This classical cost model omits memory layout, specialised kernels, parallelism, and alternative multiplication algorithms. Use it unless another model is supplied. For adjacent complexity revision, see Sorting Algorithms: Complexity and Comparison.

Matrix Chain Order traps and question forms

Remember each error with its correction:

• Reordering matrices changes the product. Change parentheses only.

• Using p[i]*p[k]*p[j] creates an off-by-one cost. Use p[i-1]*p[k]*p[j].

• Filling arbitrary cells can read unfinished intervals. Fill by increasing chain length.

• Setting m[i,i] to a dimension invents work. Set it to 0.

• Returning only 405 omits the order when reconstruction is requested. Use s.

Tasks may compare orders, fill an m or s cell, select the recurrence, reconstruct parentheses, derive complexity, or count orders. Rapid check: for A:8x20, B:20x5, C:5x10, (AB)C costs 8*20*5 + 8*5*10 = 1200; A(BC) costs 20*5*10 + 8*20*10 = 2600, so choose (AB)C. For the main chain, m[1,4]=405, s[1,4]=2, and four matrices have C3=5 orders.

KnowledgeGate has about 20 Matrix Chain Order questions that are live in its practice bank. Use GATE CS Exam Preparation as a broader study route, not as evidence of official frequency or weightage.

Matrix Chain Order in short and the next step

Recall six moves: write p; set diagonals to 0; grow intervals by length; try every split k; store the best cost and split; recurse through s. The checkpoint is p=[5,10,3,12,5] -> m[1,4]=405 -> s[1,4]=2 -> (A1A2)(A3A4).

Now test B1:10x5, B2:5x2, B3:2x20 without looking ahead. The check is (B1B2)B3 = 10*5*2 + 10*2*20 = 500, while B1(B2B3) = 5*2*20 + 10*5*20 = 1200, so the first order wins.

Rebuild both tables from the dimension array without the filled values. For a structured route through Dynamic Programming and Algorithms, GATE Guidance by Sanchit Sir is an optional next step.