6.2. Dynamic Programming and Matrix Multiplication

Try these first

1. 1.

   What is the basic requirement to multiply two matrices?

   Hint

   Think about the dimensions of both matrices.

2. 2.

   Is matrix multiplication commutative?

   Hint

   Consider if you switch the order of two matrices.

3. 3.

   What is the main goal of dynamic programming in matrix multiplication?

   • To simplify the matrix dimensions
   • To find the optimal order that minimizes the cost
   • To make multiplication associative

   Hint

   Consider why we care about the order when multiplying multiple matrices.

4. 4.

   True or False: Matrix multiplication is associative but not commutative.

   • True
   • False

   Hint

   Think about how changing the order affects the product.

5. 5.

   Given five matrices M1 (10x20), M2 (20x30), M3 (30x10), M4 (10x5), and M5 (5x40), determine the optimal order for multiplication to minimize computation, detailing your approach.

   Hint

   Build a cost table using dimensions to track minimal multiplication costs.

6. 6.

   Explain how different orders (left-to-right vs right-to-left) in matrix multiplication impact computational cost, using Fibonacci or large matrices as examples.

   Hint

   Consider the size of intermediate products when choosing multiply orders.