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

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.

Footnotes

1. Introduction to Algorithms, Dynamic Programming PDF - CLRS treatment of matrix-chain multiplication recurrence and complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Matrix chain multiplication - Wikipedia - Overview of the problem, associativity, and Catalan-number growth of parenthesizations. ↩ ↩² ↩³

3. 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\}$:

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$.

Footnotes

1. Matrix chain multiplication - Wikipedia - Overview of the problem, associativity, and Catalan-number growth of parenthesizations. ↩

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

3. Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

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

Footnotes

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

2. Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩

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}$$

Dynamic Programming Tables

Cost table $m[i,j]$

Split table $s[i,j]$

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

Footnotes

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

2. 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

1. $A_1A_2$:

   $$4\cdot10\cdot3=120$$

2. $A_3A_4$:

   $$3\cdot12\cdot20=720$$

3. $(A_3A_4)A_5$:
   intermediate size is $3\times20$, so

   $$3\cdot20\cdot7=420$$

4. $(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

Footnotes

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

2. Matrix Chain Multiplication - GeeksforGeeks - Practical explanation of the recurrence and complexity bounds. ↩