6.2. Dynamic Programming and Matrix Multiplication

For our last example of dynamic programming to this week, now we look at the problem of efficiently multiplying the sequence of matrices.

To multiply two matrices A and B, we need compatible dimensions. If we have an m × n matrix A and an n × p matrix B, the final matrix will be m × p. The process requires that the number of columns in A must match the number of rows in B. To compute the product A B, if I want the (i, j)-th entry in A B, I take the i-th row in A and multiply it with the j-th column in B. Hence, the computation for each entry takes O(n) steps, and the total cost of multiplying two matrices is O(m * n * p).

Matrix multiplication requires two matrices to have compatible dimensions. For instance, if matrix A has m rows and n columns, and matrix B has n rows and p columns, they can be multiplied, resulting in a new matrix with m rows and p columns. Each entry is computed by multiplying corresponding entries from the row of A and the column of B, which involves n multiplications per entry. Since there are m * p entries in the resulting matrix, the total computational cost becomes O(m * n * p). This basic understanding is essential when exploring more complex scenarios like multiplying multiple matrices.

Think of matrix multiplication like assembling a toy from multiple parts. If part A has 3 pieces and part B has 4, they can be combined if the connection points match. Each combination of points has to be checked (like computing a matrix entry), and the total time taken depends on the number of points being checked.

The concern is not just computing the product of two matrices, but of three or more. For example, multiplying matrices A, B, and C can be done by either multiplying A and B first or B and C first. Matrix multiplication is associative but not commutative, meaning the order of matrix multiplications matters for efficiency. The complexity can change drastically depending on the order chosen for multiplication.

When multiplying multiple matrices, like A, B, and C, the order in which you perform the multiplications can lead to very different computational costs. Matrix multiplication is associative (meaning that irrespective of how we group the matrices, the result will be the same), but it is not commutative (the order in which matrices are multiplied generally affects the result). Thus, calculating A(B C) could have a different computational cost compared to (A B)C. Understanding this is crucial for optimizing the overall process.

Imagine you're assembling a large LEGO castle from smaller subsections. You can either merge the first two subsections together or merge the last two. Depending on which two you choose to merge first, the amount of effort and time may vary significantly, illustrating how order affects the total building duration.

Suppose we have three matrices: A (1 × 100), B (100 × 1), and C (100 × 100). If we compute B times C first, we get a 100 × 100 matrix, requiring 10,000 steps. Next, multiplying A with that would require another 10,000 steps, totaling 20,000 steps. Conversely, if we compute A times B first, we get a 1 × 1 matrix, which only takes 100 steps, and then multiplying that result by C would also take 100 steps. Hence, the total is only 200 steps.

In this example, when we compute the product of matrices in different orders, we observe a dramatic difference in computational cost. By multiplying B and C first, we end up performing significantly more operations (20,000 steps total), while choosing to multiply A and B first results in just 200 steps. This exemplifies how crucial the order of operations can be in matrix multiplication.

Consider baking a cake where you need to mix ingredients sequentially. If you mix flour and sugar together first (A * B), then add eggs (C), it would take minimal effort. However, mixing the flour, sugar, and eggs all at once in a tricky process leads to a much more complex and time-consuming task, similar to the multiplication order affecting performance.

In general, for a sequence of M matrices M1, M2,..., Mn, each with dimensions r1, c1, r2, c2, ..., we need to ensure that the number of columns in each matrix matches the number of rows in the subsequent matrix. The goal is to find the optimal way to compute their product while minimizing the total cost. This involves deciding where to place the brackets during multiplication.

When dealing with multiple matrices, the goal is to find the optimal order of multiplication to minimize the total computational cost. This requires understanding the dimensions of each matrix to ensure they can be multiplied accordingly. We seek to determine how to group or bracket these multiplications efficiently, which is a key aspect of dynamic programming in solving matrix multiplication problems.

Think of planning a road trip with multiple stops. The order of your route can determine fuel usage and time spent on the road. By mapping out the most efficient route with the least stops, you’re essentially determining the most cost-effective way to complete your journey, paralleling the matrix multiplication optimization process.

--