What is matrix chain multiplication?

Matrix chain multiplication is the process of multiplying multiple matrices with only a few arithmetic operations.

Remember, matrix multiplication is an associative property.

The trick is to place parenthesis in such an order that the result is computed with only a few arithmetic operations.

Example

Consider three matrices, where A is 2x3, B is 3x5, and C is 5x10.

Since the first case involves fewer arithmetic operations, it is a better approach.

Approach

A simple approach to this is to place parenthesis at all the possible positions and calculate the operational cost. Finding the minimum operational cost for one possible position is the optimal way of solving a chain of matrices. If there are four (n) matrices, then there are three (n-1) ways to place the parenthesis.

• A(BCD)
• (AB)(CD)
• (ABC)D