If you would prefer reading the post as a contiguous block rather than a slide show,

## Motivation

The purpose of this post is to show a fully worked out example of Chain Matrix Multiplication using dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve. (Note: Not the technical definition)

There are multiple sources online with great proofs, source code, and explanation of the proofs, but I did not find an example problem that I felt was easy to understand and follow. I hope that the proofs become much easier to understand after seeing this problem worked out.

You may be wondering “What is my motivation for doing this problem using *Dynamic Programming*
when I could just as easily multiply the matrices in order and be done with it?”. Well, suppose that
the matrices are really big; as in, each matrix was a couple of hundred columns and rows.
Ordinary matrix multiplication is an Θ(n^{3}) operation, so it will take many operations.
It just so happens that the order in which you multiply matrices makes a huge difference in the number of
calculations you have to do. That’s why we look for the optimal order (technical term is factorization) of multiplication.

## Preliminaries

#### Notation

- The symbol ‘×’ will be used to signify multiplying two matrices together.
- The symbol ’
⋅ ’ will be used to signify multiplying two integers together. - Z
_{a,b}will be used to signify the cost of multiplying all the matrices from Matrix a to Matrix b together in the optimal order.

## Preliminaries 2

#### Prerequisite Math Facts

- A
_{p x q}× B_{q x r}will take p⋅ q⋅ r operations, where A is a matrix with p rows and q columns and B is a matrix with q rows and r columns. - Matrix multiplication is associative, so A × (B × C) == (A × B) × C.
- Multiplying A
_{p x q}× B_{q x r}will yield the matrix C_{ p x r}. - For matrices A and B, A × B
≠ B × A

## Preliminaries 3

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | ? | ? | ? | ? |

2 | - | 0 | ? | ? | ? |

3 | - | - | 0 | ? | ? |

4 | - | - | - | 0 | ? |

5 | - | - | - | - | 0 |

We will use this table to keep track of the cost of multiplying matrices.
Notice that the diagonals are all 0; it’s because we won’t be multiplying a matrix
by itself. The boxes with hyphens will be ignored because matrix multiplication works
from left to right, not the other way around. Element Z_{a,b} in the table
will be the cost of multiplying all the matrices between a and b. Getting the
top right corner box will give us our final answer.

## Preliminaries 4

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | ? | ? | ? | ? |

2 | - | 4 x 2 | ? | ? | ? |

3 | - | - | 2 x 3 | ? | ? |

4 | - | - | - | 3 x 6 | ? |

5 | - | - | - | - | 6 x 5 |

The aptly named dimension table will be used to keep track of the dimensions of the resultant matrix.

## Game Time!

Matrix | Dimensions |
---|---|

M_{1} |
3 x 4 |

M_{2} |
4 x 2 |

M_{3} |
2 x 3 |

M_{4} |
3 x 6 |

M_{5} |
6 x 5 |

Looks like everything is set. Looks like we’re ready for the problem.
Suppose we want to multiply the matrices M_{1} × M_{2} × M_{3} × M_{4} × M_{5}.
What is the optimal factorization (technical term for order of multiplying matrices) for this problem?
Let’s do this!

## Round 1

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | ? | ? | ? | ? |

2 | - | 0 | ? | ? | ? |

3 | - | - | 0 | ? | ? |

4 | - | - | - | 0 | ? |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | ? | ? | ? | ? |

2 | - | 4 x 2 | ? | ? | ? |

3 | - | - | 2 x 3 | ? | ? |

4 | - | - | - | 3 x 6 | ? |

5 | - | - | - | - | 6 x 5 |

First, we start by keeping track of all the possible combinations of multiplying 2 matrices. Remember, we are not allowed to switch the order of the matrices, so there are only 4 combinations.

Cell | Combination | Calculation | Resulting Dimension |
---|---|---|---|

Z_{1,2} |
M_{1} × M_{2} |
3 |
3 x 2 |

Z_{2,3} |
M_{2} × M_{3} |
4 |
4 x 3 |

Z_{3,4} |
M_{3} × M_{4} |
2 |
2 x 6 |

Z_{4,5} |
M_{4} × M_{5} |
3 |
3 x 5 |

With that, we’ve completed round one. We update our costs and dimensions tables and we’re ready for round 2.

## Round 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | ? | ? | ? |

2 | - | 0 | 24 | ? | ? |

3 | - | - | 0 | 36 | ? |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | ? | ? | ? |

2 | - | 4 x 2 | 4 x 3 | ? | ? |

3 | - | - | 2 x 3 | 2 x 6 | ? |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

From here on out, we will start heavily using our tables. For round 2, we will
start looking at cost of multiplying 3 matrices together: Z_{1,3},
Z_{2,4}, and Z_{3,5}.

For Z_{1,3}, we want the min{(M_{1} × M_{2}) × M_{3}
, M_{1} × (M_{2} × M_{3})}.

We can rewrite that as min{Z_{1,2} × M_{3},
M_{1} × Z_{2,3})}. Now we recognize the values from the table.

### An important point is that when we do the calculation of cost of Z_{1,2} × M_{3}, we have to find the cost of multiplying
Z_{1,2} × M_{3} and we have to add to that the cost of Z_{1,2}, which is 24.

We have to do this for each of the remaining 2 combinations. We will end up doing 6 subproblems.
## Round 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | ? | ? | ? |

2 | - | 0 | 24 | ? | ? |

3 | - | - | 0 | 36 | ? |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | ? | ? | ? |

2 | - | 4 x 2 | 4 x 3 | ? | ? |

3 | - | - | 2 x 3 | 2 x 6 | ? |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

Cell | Combination | Shorthand | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|---|

Z_{1,3} |
(M_{1} × M_{2}) × M_{3} |
Z_{1,2} × M_{3} |
3 |
18 + 24 = 42 | 3 x 3 | ✓ |

Z_{1,3} |
M_{1} × (M_{2} × M_{3}) |
M_{1} × Z_{2,3} |
3 |
36 + 24 = 50 | 3 x 3 | ✗ |

Z_{2,4} |
(M_{2} × M_{3}) × M_{4} |
Z_{2,3} × M_{4} |
4 |
72 + 24 = 96 | 4 x 6 | ✗ |

Z_{2,4} |
M_{2} × (M_{3} × M_{4}) |
M_{2} × Z_{3,4} |
4 |
36 + 48 = 84 | 4 x 6 | ✓ |

Z_{3,5} |
(M_{3} × M_{4}) × M_{5} |
Z_{3,4} × M_{5} |
2 |
36 + 60 = 96 | 2 x 5 | ✓ |

Z_{3,5} |
M_{3} × (M_{4} × M_{5}) |
M_{3} × Z_{4,5} |
2 |
30 + 90 = 120 | 2 x 5 | ✗ |

With that, we’re finished with round 2. We just update our cost and dimension tables with the values with the check marks, and we’re ready for round 3.

## Round 3

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | ? | ? |

2 | - | 0 | 24 | 84 | ? |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | ? | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | ? |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

For round 3, we’re finding all the possible ways to multiply
4 matrices without changing their order. Our goal is to fill in Z_{1,4}
and Z_{2,5}. Let’s start with Z_{1,4}.

Z_{1,4} = min{ M_{1} × Z_{2,4},
Z_{1,2} × Z_{3,4},
Z_{1,3} × M_{4}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{1,4} |
M_{1} × Z_{2,4} |
3 |
72 + 84 = 156 | 3 x 6 | ✗ |

Z_{1,4} |
Z_{1,2} × Z_{3,4} |
3 |
24 + 36 + 36 = 96 | 3 x 6 | ✓ |

Z_{1,4} |
Z_{1,3} × M_{4} |
3 |
42 + 54 = 96 | 3 x 6 | ✓ |

Notice that two of the solutions have the same cost.
This means that either ordering is equally optimal way to factorize
multiplication for Z_{1,4}.

## Round 3 Part 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | ? |

2 | - | 0 | 24 | 84 | ? |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | ? |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

Now we’re doing Z_{2,5}.

Z_{2,5} = min{ M_{2} × Z_{3,5},
Z_{2,3} × Z_{4,5},
Z_{2,4} × M_{5}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{2,5} |
M_{2} × Z_{3,5} |
4 |
40 + 96 = 136 | 4 x 5 | ✓ |

Z_{2,5} |
Z_{2,3} × Z_{4,5} |
4 |
60 + 24 + 90 = 174 | 4 x 5 | ✗ |

Z_{2,5} |
Z_{2,4} × M_{5} |
4 |
84 + 120 = 204 | 4 x 5 | ✗ |

With that, we’re done with round 3. Time for the last round!

## Final Round!

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | ? |

2 | - | 0 | 24 | 84 | 136 |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | 4 x 5 |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

As with any good final boss battle, this one will have the most parts.

Z_{1,5} = min{ M_{1} × Z_{2,5},
Z_{1,2} × Z_{3,5},
Z_{1,3} × Z_{4,5},
Z_{1,4} × M_{5}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{1,5} |
M_{1} × Z_{2,5} |
2 |
60 + 136 = 196 | 3 x 5 | ✗ |

Z_{1,5} |
Z_{1,2} × Z_{3,5} |
3 |
30 + 24 + 96 = 150 | 3 x 5 | ✓ |

Z_{1,5} |
Z_{1,3} × Z_{4,5} |
3 |
45 + 42 + 90 = 177 | 3 x 5 | ✗ |

Z_{1,5} |
Z_{1,4} × M_{5} |
3 |
96 + 90 = 186 | 3 x 5 | ✗ |

So we found that the best factorization for this problm is Z_{1,2} × Z_{3,5} and the total cost is 150.

## Final Credits

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | 150 |

2 | - | 0 | 24 | 84 | 136 |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | 3 x 5 |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | 4 x 5 |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

So we found that the best factorization for this problm is Z_{1,2} × Z_{3,5} and the total cost is 150.

Recall from round 1 that Z_{1,2} is M_{1} × M_{2}.

Also recall from round 2 that Z_{3,5} is (M_{3} × M_{4}) × M_{5}.

So the best factorization of these matrices is (M_{1} × M_{2}) × ((M_{3} × M_{4}) × M_{5}).
And with that, we’re done! Thanks for reading!

## Motivation

The purpose of this post is to show a fully worked out example of Chain Matrix Multiplication using dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve. (Note: Not the technical definition)

There are multiple sources online with great proofs, source code, and explanation of the proofs, but I did not find an example problem that I felt was easy to understand and follow. I hope that the proofs become much easier to understand after seeing this problem worked out.

You may be wondering “What is my motivation for doing this problem using *Dynamic Programming*
when I could just as easily multiply the matrices in order and be done with it?”. Well, suppose that
the matrices are really big; as in, each matrix was a couple of hundred columns and rows.
Ordinary matrix multiplication is an Θ(n^{3}) operation, so it will take many operations.
It just so happens that the order in which you multiply matrices makes a huge difference in the number of
calculations you have to do. That’s why we look for the optimal order (technical term is factorization) of multiplication.

## Preliminaries

#### Notation

- The symbol ‘×’ will be used to signify multiplying two matrices together.
- The symbol ’
⋅ ’ will be used to signify multiplying two integers together. - Z
_{a,b}will be used to signify the cost of multiplying all the matrices from Matrix a to Matrix b together in the optimal order.

## Preliminaries 2

#### Prerequisite Math Facts

- A
_{p x q}× B_{q x r}will take p⋅ q⋅ r operations, where A is a matrix with p rows and q columns and B is a matrix with q rows and r columns. - Matrix multiplication is associative, so A × (B × C) == (A × B) × C.
- Multiplying A
_{p x q}× B_{q x r}will yield the matrix C_{ p x r}. - For matrices A and B, A × B
≠ B × A

## Preliminaries 3

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | ? | ? | ? | ? |

2 | - | 0 | ? | ? | ? |

3 | - | - | 0 | ? | ? |

4 | - | - | - | 0 | ? |

5 | - | - | - | - | 0 |

We will use this table to keep track of the cost of multiplying matrices.
Notice that the diagonals are all 0; it’s because we won’t be multiplying a matrix
by itself. The boxes with hyphens will be ignored because matrix multiplication works
from left to right, not the other way around. Element Z_{a,b} in the table
will be the cost of multiplying all the matrices between a and b. Getting the
top right corner box will give us our final answer.

## Preliminaries 4

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | ? | ? | ? | ? |

2 | - | 4 x 2 | ? | ? | ? |

3 | - | - | 2 x 3 | ? | ? |

4 | - | - | - | 3 x 6 | ? |

5 | - | - | - | - | 6 x 5 |

The aptly named dimension table will be used to keep track of the dimensions of the resultant matrix.

## Game Time!

Matrix | Dimensions |
---|---|

M_{1} |
3 x 4 |

M_{2} |
4 x 2 |

M_{3} |
2 x 3 |

M_{4} |
3 x 6 |

M_{5} |
6 x 5 |

Looks like everything is set. Looks like we’re ready for the problem.
Suppose we want to multiply the matrices M_{1} × M_{2} × M_{3} × M_{4} × M_{5}.
What is the optimal factorization (technical term for order of multiplying matrices) for this problem?
Let’s do this!

## Round 1

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | ? | ? | ? | ? |

2 | - | 0 | ? | ? | ? |

3 | - | - | 0 | ? | ? |

4 | - | - | - | 0 | ? |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | ? | ? | ? | ? |

2 | - | 4 x 2 | ? | ? | ? |

3 | - | - | 2 x 3 | ? | ? |

4 | - | - | - | 3 x 6 | ? |

5 | - | - | - | - | 6 x 5 |

First, we start by keeping track of all the possible combinations of multiplying 2 matrices. Remember, we are not allowed to switch the order of the matrices, so there are only 4 combinations.

Cell | Combination | Calculation | Resulting Dimension |
---|---|---|---|

Z_{1,2} |
M_{1} × M_{2} |
3 |
3 x 2 |

Z_{2,3} |
M_{2} × M_{3} |
4 |
4 x 3 |

Z_{3,4} |
M_{3} × M_{4} |
2 |
2 x 6 |

Z_{4,5} |
M_{4} × M_{5} |
3 |
3 x 5 |

With that, we’ve completed round one. We update our costs and dimensions tables and we’re ready for round 2.

## Round 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | ? | ? | ? |

2 | - | 0 | 24 | ? | ? |

3 | - | - | 0 | 36 | ? |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | ? | ? | ? |

2 | - | 4 x 2 | 4 x 3 | ? | ? |

3 | - | - | 2 x 3 | 2 x 6 | ? |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

From here on out, we will start heavily using our tables. For round 2, we will
start looking at cost of multiplying 3 matrices together: Z_{1,3},
Z_{2,4}, and Z_{3,5}.

For Z_{1,3}, we want the min{(M_{1} × M_{2}) × M_{3}
, M_{1} × (M_{2} × M_{3})}.

We can rewrite that as min{Z_{1,2} × M_{3},
M_{1} × Z_{2,3})}. Now we recognize the values from the table.

### An important point is that when we do the calculation of cost of Z_{1,2} × M_{3}, we have to find the cost of multiplying
Z_{1,2} × M_{3} and we have to add to that the cost of Z_{1,2}, which is 24.

We have to do this for each of the remaining 2 combinations. We will end up doing 6 subproblems.
## Round 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | ? | ? | ? |

2 | - | 0 | 24 | ? | ? |

3 | - | - | 0 | 36 | ? |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | ? | ? | ? |

2 | - | 4 x 2 | 4 x 3 | ? | ? |

3 | - | - | 2 x 3 | 2 x 6 | ? |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

Cell | Combination | Shorthand | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|---|

Z_{1,3} |
(M_{1} × M_{2}) × M_{3} |
Z_{1,2} × M_{3} |
3 |
18 + 24 = 42 | 3 x 3 | ✓ |

Z_{1,3} |
M_{1} × (M_{2} × M_{3}) |
M_{1} × Z_{2,3} |
3 |
36 + 24 = 50 | 3 x 3 | ✗ |

Z_{2,4} |
(M_{2} × M_{3}) × M_{4} |
Z_{2,3} × M_{4} |
4 |
72 + 24 = 96 | 4 x 6 | ✗ |

Z_{2,4} |
M_{2} × (M_{3} × M_{4}) |
M_{2} × Z_{3,4} |
4 |
36 + 48 = 84 | 4 x 6 | ✓ |

Z_{3,5} |
(M_{3} × M_{4}) × M_{5} |
Z_{3,4} × M_{5} |
2 |
36 + 60 = 96 | 2 x 5 | ✓ |

Z_{3,5} |
M_{3} × (M_{4} × M_{5}) |
M_{3} × Z_{4,5} |
2 |
30 + 90 = 120 | 2 x 5 | ✗ |

With that, we’re finished with round 2. We just update our cost and dimension tables with the values with the check marks, and we’re ready for round 3.

## Round 3

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | ? | ? |

2 | - | 0 | 24 | 84 | ? |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | ? | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | ? |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

For round 3, we’re finding all the possible ways to multiply
4 matrices without changing their order. Our goal is to fill in Z_{1,4}
and Z_{2,5}. Let’s start with Z_{1,4}.

Z_{1,4} = min{ M_{1} × Z_{2,4},
Z_{1,2} × Z_{3,4},
Z_{1,3} × M_{4}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{1,4} |
M_{1} × Z_{2,4} |
3 |
72 + 84 = 156 | 3 x 6 | ✗ |

Z_{1,4} |
Z_{1,2} × Z_{3,4} |
3 |
24 + 36 + 36 = 96 | 3 x 6 | ✓ |

Z_{1,4} |
Z_{1,3} × M_{4} |
3 |
42 + 54 = 96 | 3 x 6 | ✓ |

Notice that two of the solutions have the same cost.
This means that either ordering is equally optimal way to factorize
multiplication for Z_{1,4}.

## Round 3 Part 2

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | ? |

2 | - | 0 | 24 | 84 | ? |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | ? |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

Now we’re doing Z_{2,5}.

Z_{2,5} = min{ M_{2} × Z_{3,5},
Z_{2,3} × Z_{4,5},
Z_{2,4} × M_{5}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{2,5} |
M_{2} × Z_{3,5} |
4 |
40 + 96 = 136 | 4 x 5 | ✓ |

Z_{2,5} |
Z_{2,3} × Z_{4,5} |
4 |
60 + 24 + 90 = 174 | 4 x 5 | ✗ |

Z_{2,5} |
Z_{2,4} × M_{5} |
4 |
84 + 120 = 204 | 4 x 5 | ✗ |

With that, we’re done with round 3. Time for the last round!

## Final Round!

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | ? |

2 | - | 0 | 24 | 84 | 136 |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | ? |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | 4 x 5 |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

As with any good final boss battle, this one will have the most parts.

Z_{1,5} = min{ M_{1} × Z_{2,5},
Z_{1,2} × Z_{3,5},
Z_{1,3} × Z_{4,5},
Z_{1,4} × M_{5}}

Cell | Combination | Calculation | Total Cost | Resulting Dimension | Winner |
---|---|---|---|---|---|

Z_{1,5} |
M_{1} × Z_{2,5} |
2 |
60 + 136 = 196 | 3 x 5 | ✗ |

Z_{1,5} |
Z_{1,2} × Z_{3,5} |
3 |
30 + 24 + 96 = 150 | 3 x 5 | ✓ |

Z_{1,5} |
Z_{1,3} × Z_{4,5} |
3 |
45 + 42 + 90 = 177 | 3 x 5 | ✗ |

Z_{1,5} |
Z_{1,4} × M_{5} |
3 |
96 + 90 = 186 | 3 x 5 | ✗ |

So we found that the best factorization for this problm is Z_{1,2} × Z_{3,5} and the total cost is 150.

## Final Credits

#### Cost Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 0 | 24 | 42 | 96 | 150 |

2 | - | 0 | 24 | 84 | 136 |

3 | - | - | 0 | 36 | 96 |

4 | - | - | - | 0 | 90 |

5 | - | - | - | - | 0 |

#### Dimensions Table

× | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 3 x 4 | 3 x 2 | 3 x 3 | 3 x 6 | 3 x 5 |

2 | - | 4 x 2 | 4 x 3 | 4 x 6 | 4 x 5 |

3 | - | - | 2 x 3 | 2 x 6 | 2 x 5 |

4 | - | - | - | 3 x 6 | 3 x 5 |

5 | - | - | - | - | 6 x 5 |

So we found that the best factorization for this problm is Z_{1,2} × Z_{3,5} and the total cost is 150.

Recall from round 1 that Z_{1,2} is M_{1} × M_{2}.

Also recall from round 2 that Z_{3,5} is (M_{3} × M_{4}) × M_{5}.

So the best factorization of these matrices is (M_{1} × M_{2}) × ((M_{3} × M_{4}) × M_{5}).
And with that, we’re done! Thanks for reading!

Edit 1: Changed the multiplication symbols to more friendly ones. Edit 2: Fixed spelling mistakes….I are really good at English :D