Let \(A_1,A_2,A_3\), and A4 be four matrices of dimensions 10 × 5,5 × 20,20 ×…
2016
Let \(A_1,A_2,A_3\), and A4 be four matrices of dimensions 10 × 5,5 × 20,20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product \(A_1A_2A_3A_4\) using the basic matrix multiplication method is .
Attempted by 58 students.
Show answer & explanation
Correct answer: 1500
Key idea: cost of multiplying an r×s matrix by an s×t matrix is r·s·t. Use this to evaluate the possible parenthesizations.
((A1A2)A3)A4: A1A2 = 10·5·20 = 1000 → 10×20; (A1A2)A3 = 10·20·10 = 2000 → 10×10; ((A1A2)A3)A4 = 10·10·5 = 500. Total = 1000 + 2000 + 500 = 3500.
(A1(A2A3))A4: A2A3 = 5·20·10 = 1000 → 5×10; A1(A2A3) = 10·5·10 = 500 → 10×10; (...)A4 = 10·10·5 = 500. Total = 1000 + 500 + 500 = 2000.
A1((A2A3)A4): A2A3 = 5·20·10 = 1000 → 5×10; (A2A3)A4 = 5·10·5 = 250 → 5×5; A1·(...) = 10·5·5 = 250. Total = 1000 + 250 + 250 = 1500.
A1(A2(A3A4)): A3A4 = 20·10·5 = 1000 → 20×5; A2·(...) = 5·20·5 = 500 → 5×5; A1·(...) = 10·5·5 = 250. Total = 1000 + 500 + 250 = 1750.
(A1A2)(A3A4): A1A2 = 10·5·20 = 1000 → 10×20; A3A4 = 20·10·5 = 1000 → 20×5; multiply results = 10·20·5 = 1000. Total = 1000 + 1000 + 1000 = 3000.
Minimum cost: 1500 scalar multiplications, achieved by computing A2A3 first, then multiplying that result by A4, and finally multiplying by A1 (parenthesization A1((A2A3)A4)).
A video solution is available for this question — log in and enroll to watch it.