Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for \{4,10,3,12,20,7\} | AI Research

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

Verified Sources

May 25, 2026

We are given a matrix chain with dimension array $p=\{4,10,3,12,20,7\}$ . This means the matrices are2:

$A_1: 4 \times 10$
$A_2: 10 \times 3$
$A_3: 3 \times 12$
$A_4: 12 \times 20$
$A_5: 20 \times 7$

The goal of matrix chain multiplication is not to change the final product, since matrix multiplication is associative, but to minimize the total number of scalar multiplications required.2

If a matrix of size $a \times b$ is multiplied by a matrix of size $b \times c$ , then the cost is:

a \cdot b \cdot c

Dynamic programming is used because the problem has optimal substructure and overlapping subproblems.2

We define:

m[i,j] = \text{minimum cost of multiplying } A_iA_{i+1}\cdots A_j

with recurrence2:

m[i,j] = \min_{i \le k < j}\Big(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j\Big)

Base case:

m[i,i] = 0

The dynamic programming table-filling algorithm runs in $O(n^3)$ time and uses $O(n^2)$ space, where $n$ is the number of matrices.2

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity.
Matrix chain multiplication - Wikipedia - Overview of the optimization problem and why parenthesization matters.
Matrix Chain Multiplication - GeeksforGeeks - Summary of recurrence, DP table method, and $O(n^3)$ complexity.

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵
Matrix chain multiplication - Wikipedia - Overview of the problem, associativity, and Catalan-number growth of parenthesizations. ↩ ↩² ↩³
Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩ ↩² ↩³ ↩⁴ ↩⁵

Matrix Chain Multiplication - Dynamic Programming

Key Observation

The dimensions determine the multiplication cost, not the values inside the matrices. Different valid parenthesizations can have very different costs.2

Matrix chain multiplication - Wikipedia - Overview of the problem, associativity, and Catalan-number growth of parenthesizations. ↩
Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

Let us encode the matrices more formally using the dimension array $p=\{4,10,3,12,20,7\}$ :

Matrix	Size
$A_1$	$4 \times 10$
$A_2$	$10 \times 3$
$A_3$	$3 \times 12$
$A_4$	$12 \times 20$
$A_5$	$20 \times 7$

Thus there are $n=5$ matrices. A brute-force strategy would examine all full parenthesizations, whose count grows according to the Catalan number sequence and is exponential in effect for this problem size growth. Dynamic programming avoids recomputing the same subchains by filling tables diagonally by chain length.2

We maintain two tables:

$m[i,j]$ : minimum multiplication cost for $A_i \cdots A_j$
$s[i,j]$ : the best split index $k$ where the optimal split occurs

For this instance, we will compute all chain lengths from $2$ to $5$ .

Matrix chain multiplication - Wikipedia - Overview of the problem, associativity, and Catalan-number growth of parenthesizations. ↩
Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩ ↩²
Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

Dynamic Programming Solution: Fill the Cost Table

1
Step 1
Set all diagonal entries to zero because multiplying one matrix requires no multiplication: $m[i,i]=0$ for $1 \le i \le 5$ .2

Footnotes

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩

Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩
2
Step 2
For each adjacent pair, compute one direct multiplication cost using $p_{i-1}p_ip_{i+1}$ . This gives: $m[1,2]=4\cdot10\cdot3=120$ , $m[2,3]=10\cdot3\cdot12=360$ , $m[3,4]=3\cdot12\cdot20=720$ , and $m[4,5]=12\cdot20\cdot7=1680$ .
3
Step 3
For each subchain of 3 matrices, try both possible split points and keep the minimum. For example, for $m[1,3]$ , compare splitting after $A_1$ versus after $A_2$ .
4
Step 4
For each subchain of 4 matrices, try all 3 split points. Use already-computed smaller subproblems from the table, which is the core dynamic programming idea.

Footnotes

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩
5
Step 5
For $m[1,5]$ , try splits at $k=1,2,3,4$ and choose the smallest total. The corresponding split locations recorded in $s[i,j]$ let us reconstruct the optimal parenthesization.
6
Step 6
Starting from $s[1,5]$ , recursively split the chain into left and right optimal subchains until single matrices remain. This prints the optimal parenthesization.

Footnotes

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩

1. Base cases

Since a single matrix does not need multiplication:

m[1,1]=m[2,2]=m[3,3]=m[4,4]=m[5,5]=0

2. Chains of length $2$

For two matrices there is only one way to multiply.

m[1,2] = 4\cdot10\cdot3 = 120

m[2,3] = 10\cdot3\cdot12 = 360

m[3,4] = 3\cdot12\cdot20 = 720

m[4,5] = 12\cdot20\cdot7 = 1680

3. Chains of length $3$

For $m[1,3]$ :

Split at $k=1$ : $0 + 360 + 4\cdot10\cdot12 = 840$
Split at $k=2$ : $120 + 0 + 4\cdot3\cdot12 = 264$

So,

m[1,3]=264,\quad s[1,3]=2

For $m[2,4]$ :

Split at $k=2$ : $0 + 720 + 10\cdot3\cdot20 = 1320$
Split at $k=3$ : $360 + 0 + 10\cdot12\cdot20 = 2760$

So,

m[2,4]=1320,\quad s[2,4]=2

For $m[3,5]$ :

Split at $k=3$ : $0 + 1680 + 3\cdot12\cdot7 = 1932$
Split at $k=4$ : $720 + 0 + 3\cdot20\cdot7 = 1140$

So,

m[3,5]=1140,\quad s[3,5]=4

All of these computations directly apply the standard recurrence for matrix-chain dynamic programming.2

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩
Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

How to Read the Recurrence

The term $m[i,k] + m[k+1,j]$ is the best cost of solving the two subchains, and $p_{i-1}p_kp_j$ is the cost of multiplying the two resulting matrices together.

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩

4. Chains of length $4$

For $m[1,4]$ , try $k=1,2,3$ :

$k=1$ : $0 + 1320 + 4\cdot10\cdot20 = 2120$
$k=2$ : $120 + 720 + 4\cdot3\cdot20 = 1080$
$k=3$ : $264 + 0 + 4\cdot12\cdot20 = 1224$

Therefore,

m[1,4]=1080,\quad s[1,4]=2

For $m[2,5]$ , try $k=2,3,4$ :

$k=2$ : $0 + 1140 + 10\cdot3\cdot7 = 1350$
$k=3$ : $360 + 1680 + 10\cdot12\cdot7 = 2880$
$k=4$ : $1320 + 0 + 10\cdot20\cdot7 = 2720$

Therefore,

m[2,5]=1350,\quad s[2,5]=2

5. Full chain of length $5$

Now compute $m[1,5]$ by trying all splits $k=1,2,3,4$ :

$k=1$ : $0 + 1350 + 4\cdot10\cdot7 = 1630$
$k=2$ : $120 + 1140 + 4\cdot3\cdot7 = 1344$
$k=3$ : $264 + 1680 + 4\cdot12\cdot7 = 2280$
$k=4$ : $1080 + 0 + 4\cdot20\cdot7 = 1640$

Hence the optimal cost is:

m[1,5]=1344

and the best top-level split is:

s[1,5]=2

This means the chain is optimally split as:

(A_1A_2)(A_3A_4A_5)

Then from $s[3,5]=4$ , the right part is split as:

(A_3A_4)A_5

So the full optimal parenthesization is:

\boxed{((A_1A_2)((A_3A_4)A_5))}

or equivalently

\boxed{(A_1A_2)\big((A_3A_4)A_5\big)}

with minimum scalar multiplications:

\boxed{1344}

Minimum Cost by Subchain Length

Optimal dynamic programming costs obtained for representative subchains

Dynamic Programming Tables

Cost table $m[i,j]$

$i \backslash j$	1	2	3	4	5
1	0	120	264	1080	1344
2	-	0	360	1320	1350
3	-	-	0	720	1140
4	-	-	-	0	1680
5	-	-	-	-	0

Split table $s[i,j]$

$i \backslash j$	1	2	3	4	5
1	-	1	2	2	2
2	-	-	2	2	2
3	-	-	-	3	4
4	-	-	-	-	4
5	-	-	-	-	-

The entries in the split table show where each optimal subproblem divides. This is the basis for backtracking the final parenthesization after the cost table is complete.2

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩
Matrix-Chain Multiplication PDF, Columbia University - Lecture notes showing worked matrix-chain examples and parenthesization logic. ↩

1(A1A2)((A3A4)A5)

Detailed Reasoning and Complexity

Common Mistake

Do not multiply dimensions directly from the original matrices after each step without updating the intermediate result sizes. Each parenthesization creates new matrix dimensions that affect later costs.

Matrix-Chain Multiplication PDF, Columbia University - Lecture notes showing worked matrix-chain examples and parenthesization logic. ↩

Final Answer

The most efficient parenthesization of the matrix chain

A_1A_2A_3A_4A_5

for dimensions

\{4,10,3,12,20,7\}

is:

\boxed{(A_1A_2)\big((A_3A_4)A_5\big)}

or fully parenthesized:

\boxed{((A_1A_2)((A_3A_4)A_5))}

Total scalar multiplications

$A_1A_2$ :
$4\cdot10\cdot3=120$
$A_3A_4$ :
$3\cdot12\cdot20=720$
$(A_3A_4)A_5$ :
intermediate size is $3\times20$ , so
$3\cdot20\cdot7=420$
$(A_1A_2)\big((A_3A_4)A_5\big)$ :
intermediate sizes are $4\times3$ and $3\times7$ , so
$4\cdot3\cdot7=84$

Therefore,

\boxed{120+720+420+84=1344}

Complexity of the dynamic programming method

For a chain of $n$ matrices:

Time complexity: $\boxed{O(n^3)}$
Space complexity: $\boxed{O(n^2)}$

These are the standard complexity bounds for bottom-up matrix-chain multiplication dynamic programming.2

Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩
Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

Knowledge Check

Question 1 of 4

Q1Single choice

What is the optimal parenthesization for the matrix chain with dimensions $\{4,10,3,12,20,7\}$ ?

(A1A2)((A3A4)A5)

((A1(A2A3))A4)A5

(A1((A2A3)A4))A5

A1(A2(A3(A4A5)))

Explore Related Topics

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size  $n$ , explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

Best case: $T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I)$ , the minimum time over all inputs of size  $n$ .
Worst case: $T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I)$ , giving a guaranteed upper bound.
Average case: $T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I)$ , requiring an explicit input probability model.
Linear search illustrates the three cases: $\Theta(1)$ best, $\Theta(n)$ worst, and $\Theta(n)$ average (expected $\frac{n+1}{2}$ comparisons).
Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.

Banker's Algorithm Safe-State Analysis for Processes $P_0$ Through $P_4$

The course walks through a full Banker's‑algorithm safety analysis for processes  $P_0$ – $P_4$ , computing the Need matrix and using the work‑vector test to verify a safe state and a valid completion order.

Need matrix: $P_0\;(0,0,0,0)$ , $P_1\;(0,7,5,0)$ , $P_2\;(1,0,0,2)$ , $P_3\;(0,0,2,0)$ , $P_4\;(0,6,4,2)$ .
Starting work $Work = Available = (1,5,2,0)$ ; each step selects a process with $Need \le Work$ , releases its allocation, and updates $Work$ .
All processes finish, yielding a safe sequence $\langle P_0, P_2, P_1, P_3, P_4\rangle$ .
A safe state requires only one such sequence; it does not mean every immediate allocation is safe.
Exam tip: test processes with minimal or zero Need first to unlock the rest.

Syntax-Directed Translation: Infix to Prefix Notation

The module shows how a syntax‑directed translation scheme using only synthesized attributes can convert infix arithmetic expressions into prefix (Polish) notation while preserving operator precedence and left‑associativity.

Grammar: E → E + T | E - T | T; T → T * F | F; F → digit, enforcing precedence ( *  > + / - ).
Semantic actions compute a val string for each non‑terminal, concatenating the operator before its operand strings.
Example results: 9 - 5 + 2 → + - 9 5 2; 9 - 5 * 2 → - 9 * 5 2.
Synthesized (S‑attributed) attributes allow immediate bottom‑up evaluation during LR‑style parsing.
Left‑recursive rules enable left‑associativity; to use LL parsers the grammar must be transformed and inherited attributes introduced.

Browse all research articles

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for {4,10,3,12,20,7}\{4,10,3,12,20,7\}{4,10,3,12,20,7}

AI Summary

Footnotes

Matrix Chain Multiplication - Dynamic Programming

Key Observation

Footnotes

Footnotes

Dynamic Programming Solution: Fill the Cost Table

Footnotes

Footnotes

Footnotes

1. Base cases

2. Chains of length 222

3. Chains of length 333

Footnotes

How to Read the Recurrence

Footnotes

4. Chains of length 444

5. Full chain of length 555

Minimum Cost by Subchain Length

Dynamic Programming Tables

Cost table m[i,j]m[i,j]m[i,j]

Split table s[i,j]s[i,j]s[i,j]

Footnotes

Detailed Reasoning and Complexity

Common Mistake

Footnotes

Final Answer

Total scalar multiplications

Complexity of the dynamic programming method

Footnotes

Knowledge Check

Explore Related Topics

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

2. Chains of length $2$

3. Chains of length $3$

4. Chains of length $4$

5. Full chain of length $5$

Cost table $m[i,j]$

Split table $s[i,j]$