Understanding the matrix chain multiplication problem

When we chain together a sequence of operations, the order in which we group them can drastically change the total work involved, even if the final result stays the same. Matrix multiplication is a classic example of this: the product of a chain of matrices is uniquely defined, but the cost of computing that product depends entirely on how we parenthesize the expression.

This is known as the matrix chain multiplication problem, where the objective is to determine the most efficient way to parenthesize a sequence of matrices so that the total number of scalar multiplications is minimized.

The matrix chain multiplication problem is a foundational optimization problem with direct applications in query optimization for relational databases, computational graph scheduling in deep learning frameworks, and minimizing floating-point operations in scientific computing pipelines.

In this lesson, we will first understand how matrices are multiplied and what makes the order of multiplication matter, and then learn how the matrix chain multiplication problem can be solved efficiently using a dynamic programming solution.

How are matrices multiplied?

A matrix is a rectangular grid of numbers arranged in rows and columns. A matrix with p rows and q columns is said to have dimensions p × q.