6.1. 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. So, as you probably know, to multiply two matrices A and B, we need compatible dimensions.

Matrix multiplication is a technique used in linear algebra where two matrices are combined to produce another matrix. The critical requirement for multiplying two matrices is that the number of columns in the first matrix (A) must equal the number of rows in the second matrix (B). This compatibility ensures that the matrices can be multiplied together.

Think of matrix multiplication like combining ingredients for a recipe. If a recipe says you need 2 cups of flour (from matrix A) and 1 cup of sugar (from matrix B), you can only mix them if you have the right amounts. Similarly, matrices can only be multiplied if their dimensions match appropriately.

If we have A and B, then we need that the number of columns in A must match the number of rows in B. So, we have an m x n matrix A and an n x p matrix B, and the final matrix is going to be an m x p matrix.

In this chunk, the dimensions of the matrices are clearly defined. A matrix A of size m x n means it has m rows and n columns. Matrix B is specified as n x p, which means it has n rows and p columns. The result of multiplying A and B will yield a new matrix that has m rows (from A) and p columns (from B). This illustrates how dimensions play a vital role in determining if multiplication can occur and the size of the resultant matrix.

Imagine a classroom scenario. If each student (matrix A with m rows) needs to sit across from a set of books (matrix B with p columns), but each student only has a specific number of arms (n columns) to hold them, the arrangement can only happen if the number of arms matches the number of books per student. The final result displays how many students can effectively 'hold' the books, analogous to the dimensions of the resulting product matrix.

The way you compute that product A B, so if I want the i j th entry in A B, then I will take the i th row in A and sum it multiplied with the j th column B.

To find an individual entry in the product of two matrices, you locate the i-th row of matrix A and the j-th column of matrix B. Each corresponding entry in these two selections is multiplied together, and the results are summed up. This requires O(n) operations, where n is the number of columns in A (or rows in B). This method is how you derive each entry in the resulting product matrix.

Consider a factory producing different products in batches. If you want to know how many items you produced in total for a specific product type, you'd multiply the number of products by the number of batches. Each batch (row from A) contributes to the total for the specific product type (column from B), and you add these contributions to get the final total.

Therefore, I have to compute finally m times p entries, each entry requires a linear order n amount to there. So, the total cost of multiplying two matrices in terms of basic arithmetic operations is of the order of m times n times p.

The computational cost of multiplying two matrices involves determining the cost for each of the m x p entries. Since each entry computation requires O(n) operations (multiplying and summing n pairs), the total is therefore O(mnp). This final expression captures how the size of the matrices and the number of operations required grow with the dimensions involved.

Imagine organizing data in an event. If you have m events, and for each event, you want to send p invitations after processing the guest list (n entries), you could think of the time taken as your total cost. It increases with more events m, more guests n, and more invitations p, reflecting how the multiplication of matrices works.

Matrix multiplication is not commutative. So, it is important that the order is the same, but within that in which sequence I do this computation does not matter.

Matrix multiplication follows the associative property, meaning that while the order of multiplication matters (A × B is not the same as B × A), the grouping does not. This means (A × B) × C will yield the same result as A × (B × C). This property allows us to regroup matrices to optimize our multiplication sequence.

Think of it like stacking books on shelves. If you have groups of books A, B, and C to arrange, it doesn't matter whether you stack A on B first and then on C, or vice versa — the total number of books in the end is the same. However, horizontally stacking book groups in the right order matters for fitting them on the shelf – similar to the way you must follow the specific order in matrix multiplication.

The complexity of computing the answer can change depending on which order I do it, whether I do it as A times B followed by C or first B times C and then multiply by A.

The strategy you choose for multiplying multiple matrices can significantly affect the total computational cost. As demonstrated, different orders may yield very different numbers of operations required due to the dimensions of the matrices involved. This writing emphasizes the importance of finding the most efficient order to minimize overall computational effort.

Consider packing boxes for a move. Depending on whether you first pack the small boxes and then the large ones or vice versa can reflect how easy or hard the process will be—one way might allow you to use space more efficiently and cut down on trips, similar to optimizing matrix multiplication order for efficiency.

Our goal is to find an optimum way to compute this product...the choice of whether to put the bracket like this...how to put the bracket like this.

This section discusses the need to determine the optimal way to parenthesize the products of multiple matrices to minimize the total computational cost. By exploring various ways to group the matrices, we can find the arrangement that yields the least computational expense, reflecting a systematic approach seen in dynamic programming.

Think of scheduling classes in a school. If one class needs to come before another, and that can change how many classes can be taken in a semester, organizing the order in which classes are taught can maximize the learning potential of students — similar to how optimizing matrix multiplication can save resources and time.

--