6.3. Inductive Structure in Matrix Multiplication

Try these first

1. 1.

   What are the necessary conditions for multiplying two matrices?

   Hint

   Think about the dimensions of the matrices.

2. 2.

   Is matrix multiplication commutative? Why or why not?

   Hint

   Consider how matrix multiplication groups numbers.

3. 3.

   What is the time complexity of multiplying two matrices of dimensions m×n and n×p?

   • O(m × n × p)
   • O(m + n + p)
   • O(m² + n² + p²)

   Hint

   Think about how many entries you need to compute.

4. 4.

   Is the order of matrix multiplication important for computational efficiency?

   • True
   • False

   Hint

   Recall the example with matrices A, B, and C.

5. 5.

   You're given five matrices of dimensions (10x20), (20x30), (30x10), (10x40), (40x30). Calculate the minimum order needed for multiplication and the corresponding total cost.

   Hint

   Consider constructing a cost table for comparing all multiplication paths.

6. 6.

   How would you modify your strategy if one matrix's size dramatically increases, affecting the computational cost? Evaluate the new strategy.

   Hint

   Look at how early multiplications affect downstream costs.