Matrix-Chain Multiplication Using Dynamic Programming

The Matrix-Chain Multiplication problem is one of the classic examples used in CLRS to explain dynamic programming. The important point is that we are not changing the order of the matrices. We are only deciding where to put parentheses so that the total number of scalar multiplications is as small as possible.

---

1. The Basic Problem

Suppose we have three matrices:

A1​, A2​, A3​

and we want to calculate:

A1​A2​A3​

Matrix multiplication is associative, so we can calculate it in two ways:

(A1​A2​)A3​

or

A1​(A2​A3​)

Both produce the same final matrix.

However, they may require very different numbers of scalar multiplications.

That is the central idea of matrix-chain multiplication:

Find the best way to parenthesize the matrix chain so that the number of scalar multiplications is minimum.

We are not actually multiplying the matrices. We are finding the most efficient order of multiplication.

---

2. Why Does the Order Matter?

Consider the three matrices:

A1​=10×100     A2​=100×5     A3​=5×50

We want:

A1​A2​A3​

There are two possible parenthesizations.

---

Case 1: (A1 A2) A3

First calculate:

A1​A2​

The dimensions are:

$$(10\times 100)(100\times 5)$$

The resulting matrix is:

$$10\times 5$$

The number of scalar multiplications is:

$$10\times 100\times 5=5000$$

Now multiply the result by A3:

$$(10\times 5)(5\times 50)$$

Cost:

$$10\times 5\times 50=2500$$

Therefore, total cost:

5000+2500=7500​

---

3. Case 2: A1 (A2 A3)

First calculate:

A2​A3​

Dimensions:

$$(100\times 5)(5\times 50)$$

Cost:

$$100\times 5\times 50=25000$$

The result has dimensions:

$$100\times 50$$

Now calculate:

A1​(A2​A3​)

Cost:

$$10\times 100\times 50=50000$$

Total:

25000+50000=75000​

---

4. The Interesting Result

We are calculating exactly the same mathematical product:

A1​A2​A3​

But:

Parenthesization	Cost
(A1 A2) A3	7,500
A1 (A2 A3)	75,000

So:

7500 vs. 75000​

The first method requires 10 times fewer scalar multiplications. This is  why the parenthesization matters.

---

5. What Exactly Are We Trying to Find?

Suppose we have:

A1​A2​A3​⋯An​

We want to find:

Which parentheses should be inserted so that the total number of scalar multiplications is minimum?

For example:

A1​A2​A3​A4​

has five different fully parenthesized forms.

As the number of matrices increases, the number of possible parenthesizations increases extremely rapidly.

Therefore, trying every possible parenthesization is not practical.

---

6. Why Not Try Every Possibility?

The number of possible parenthesizations grows exponentially with the number of matrices.

The number of parenthesizations by P(n), with the recurrence:

The number grows exponentially, so exhaustive search is inefficient.

Therefore, we need a better approach.

That is where dynamic programming comes in.

---

7. Why Dynamic Programming Works Here

Matrix-chain multiplication has the two important properties required for dynamic programming:

1. Optimal substructure

An optimal solution to a large matrix chain contains optimal solutions to smaller matrix chains.

For example, if the optimal solution for

A1​A2​A3​A4​

splits as:

(A1​A2​)(A3​A4​)

then:

• A1 A2 must itself be optimally parenthesized.
• A3 A4 must itself be optimally parenthesized.

Otherwise, we could replace one of them with a cheaper solution and obtain a cheaper solution for the entire problem.

---

2. Overlapping subproblems

The same smaller matrix-chain problems can occur repeatedly when considering different parenthesizations.

Instead of solving the same subproblem again and again, dynamic programming stores its answer and reuses it.

---

8. How Do We Define a Subproblem?

This is the most important idea for students.

Let:

Ai​Ai+1​⋯Aj​

be a subchain.

Define:

m[i,j]

as:

The minimum number of scalar multiplications required to compute Ai​Ai+1​⋯Aj​.

For example:

m[2,4]

means:

Minimum cost of multiplying A2​A3​A4​.

we use  this definition for its dynamic-programming table.

---

9. The Base Case

What happens if there is only one matrix?

For example:

A2​

There is nothing to multiply.

Therefore:

m[i,i]=0​

This is our base case.

---

10. How Do We Split a Chain?

Consider:

Ai​Ai+1​⋯Aj​

Suppose we split it between Ak​ and Ak+1​.

Then we have:

(Ai​⋯Ak​)(Ak+1​⋯Aj​)

There are three costs:

Cost 1

Optimally multiply:

Ai​⋯Ak​

which costs:

m[i,k]

Cost 2

Optimally multiply:

Ak+1​⋯Aj​

which costs:

$$m[k+1,j]$$

Cost 3

Multiply the two resulting matrices together.

If:

Ai​⋯Ak​

has dimensions:

pi−1​×pk​

and

Ak+1​⋯Aj​

has dimensions:

pk​×pj​

then their multiplication costs:

pi−1​pk​pj​

scalar multiplications.

---

11. The Recurrence

Therefore:

​with:
        m[i,i]=0​

This recurrence is the heart of the matrix-chain dynamic-programming algorithm.

---

12. Let's Apply It to the Simple Example

Consider:

A1​=10×100     A2​=100×5     A3​=5×50

Therefore the dimension sequence is:

p0​=10,    p1​=100,    p2​=5,    p3​=50

---

Subproblems of Length 1

Each individual matrix requires no multiplication:

$$m[1,1]=0$$         $$m[2,2]=0$$         $$m[3,3]=0$$

---

13. Subproblems of Length 2

Calculate m[1,2]

Only one possible split:

A1​∣A2​

Cost:

$$0+0+(10)(100)(5)$$ 

$$m[1,2]=5000$$

---

Calculate m[2,3]

Again, only one possible split:

A2​∣A3​

Cost:

$$0+0+(100)(5)(50)$$ 

$$m[2,3]=25000$$

So our table is:

Subproblem	Minimum cost
m[1,1]	0
m[2,2]	0
m[3,3]	0
m[1,2]	5,000
m[2,3]	25,000

---

14. Finally Calculate m[1,3]

Now we want:

A1​A2​A3​

There are two possible split positions.

---

Split 1: Between A1 and A2

A1​(A2​A3​)

Cost:

m[1,1]+m[2,3]+p0​p1​p3​ $$=0+25000+(10)(100)(50)$$ $$=75000$$

---

Split 2: Between A2 and A3

(A1​A2​)A3​

Cost:

m[1,2]+m[3,3]+p0​p2​p3​ $$=5000+0+(10)(5)(50)$$ $$=7500$$

Therefore:

$$m[1,3]=\min (75000,7500)$$ m[1,3]=7500​

So the optimal parenthesization is:

(A1​A2​)A3​​

---

15. What Does the DP Table Do?

The dynamic-programming table m stores the best cost for every subchain.

For our example:

	A1	A2	A3
A1	0	5,000	7,500
A2	—	0	25,000
A3	—	—	0

The answer is at:

m[1,3]​

---

16. Why Do We Fill the Table from Shorter Chains to Longer Chains?

Suppose we want:

m[1,4]

To calculate it, we need values such as:

m[1,1],    m[2,4]

or:

m[1,2],    m[3,4]

or:

m[1,3],    m[4,4]

Therefore, the smaller chains must already have been calculated.

So we fill the table in this order:

Length 1
   ↓
Length 2
   ↓
Length 3
   ↓
Length 4
   ↓
...
Length n

This is the bottom-up dynamic-programming approach .

Example

---

17. Remembering the Actual Parenthesization

The table m tells us the minimum cost, but not directly the parentheses.

Therefore, CLRS maintains another table:

s[i,j]

This stores the value of k at which the optimal split occurs.

For our example:

$$s[1,3]=2$$

because the optimal split is:

(A1​A2​)A3​

The s table therefore helps reconstruct the actual optimal parenthesization.

---

18. The Algorithm in Simple Pseudocode

---

19. Complexity Analysis

This is a very good example for explaining how dynamic programming reduces exponential time.

Brute Force

If we try every possible parenthesization, the number of possibilities grows exponentially.

The number of parenthesizations is exponential in n.

Therefore:

Brute force: exponential time​

---

20. Dynamic Programming Complexity

How many subproblems are there?

A subproblem is identified by:

(i,j)

where:

$$1\le i\le j\le n$$

There are:

Θ(n^2)

such subproblems.

For each subproblem m[i,j], we try all possible split positions:

$$k=i,i+1,\dots ,j-1$$

There can be up to:

O(n)

choices of k.

Therefore:

O(n^2)×O(n)

gives:

O(n^3)​

The three nested loops give an O(n^3) running time, and in fact the running time is Θ(n^3).

---

21. Space Complexity

We maintain two tables:

m[i,j]

and

s[i,j]

Each table requires:

Θ(n^2)

space.

Therefore:

Θ(n^2)​

space is required.

---

22. Final Comparison

Method	Time Complexity	Space
Try every parenthesization	Exponential	—
Dynamic Programming	Θ(n³)	Θ(n²)

So the major advantage of dynamic programming is:

Instead of repeatedly solving the same subproblems, we solve each distinct subproblem once and store its result.

---

⭐ Summary

Matrix-chain multiplication does not ask us to change the order of matrices. The order A1, A2, ..., An remains fixed. We only decide where to place parentheses. Different parenthesizations can require very different numbers of scalar multiplications. Dynamic programming finds the parenthesization with minimum cost by solving smaller matrix-chain problems, storing their optimal costs, and using those costs to solve larger chains.

The four ideas to remember are:

1. Different parentheses → different costs
                ↓
2. Find the best split
                ↓
3. Store the best cost for every subchain
                ↓
4. Build the final answer from smaller answers

Thus:

Matrix Chain Multiplication: Θ(n^3) time and Θ(n^2) space​

while exhaustive enumeration takes exponential time.