Which of the following does not represent the total number of multiplications…
2017
Which of the following does not represent the total number of multiplications for multiplying four matrices of orders 20 x 2, 2 x 30, 30 x 12 and 12 x 8?
- A.
1232
- B.
3680
- C.
10320
- D.
8850
Attempted by 127 students.
Show answer & explanation
Correct answer: D
Let the matrices be A1(20 x 2), A2(2 x 30), A3(30 x 12), and A4(12 x 8). Multiplying matrices of dimensions p x q and q x r costs p x q x r scalar multiplications.
Check all five parenthesizations:
(((A1A2)A3)A4): 20 x 2 x 30 + 20 x 30 x 12 + 20 x 12 x 8 = 1200 + 7200 + 1920 = 10320.
((A1(A2A3))A4): 2 x 30 x 12 + 20 x 2 x 12 + 20 x 12 x 8 = 720 + 480 + 1920 = 3120.
(A1((A2A3)A4)): 2 x 30 x 12 + 2 x 12 x 8 + 20 x 2 x 8 = 720 + 192 + 320 = 1232.
(A1(A2(A3A4))): 30 x 12 x 8 + 2 x 30 x 8 + 20 x 2 x 8 = 2880 + 480 + 320 = 3680.
((A1A2)(A3A4)): 20 x 2 x 30 + 30 x 12 x 8 + 20 x 30 x 8 = 1200 + 2880 + 4800 = 8880.
The valid totals are 1232, 3120, 3680, 8880, and 10320. Therefore, 8850 is not produced by any valid parenthesization.
Correct answer: 8850.