# GATE | Sudo GATE 2020 Mock I (27 December 2019) | Question 55

Assume that multiplying a matrix M_{1} of dimension a×b with another matrix M_{2} of dimension bxc requires abc scalar multiplications. Computing the product of n matrices M_{1}M_{1}M_{3} … M_{n} can be done by parenthesizing in different ways. Define M_{i}M_{i+1} as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain M_{1}M_{2}M_{3}M_{4}M_{5}M_{6} using parenthesization (M_{1}(M_{2}M_{3}))(M_{4}(M_{5}M_{6})), M_{2}M_{3} and M_{5}M_{6} are only explicitly computed pairs.

Consider a matrix multiplication chain A_{1}A_{2}A_{3}A_{4}, where matrices A_{1}, A_{2}, A_{3} and A_{4} are of dimensions 5×40,40×6,6×20 and 20×5 respectively. In the parenthesization of A_{1}A_{2}A_{3}A_{4} that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are**(A)** A_{1}A_{2} and A_{3}A_{4}**(B)** A_{2}A_{3} only**(C)** A_{3}A_{4} only**(D)** A_{1}A_{2} and A_{2}A_{3}**Answer:** **(A)****Explanation:** Given matrix A_{5X40}, A_{40×6}, A_{6×20}, A_{20×5}

According to matrix chain multiplication:

Therefore, selected pairs are:

[A_{3}, A_{4}] = 600 [A_{1}, A_{2}] = 1200

So, option (A) is correct.

Quiz of this Question

Attention reader! Don’t stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in **GATE Test Series Course**.

Learn all **GATE CS concepts with Free Live Classes** on our youtube channel.