Matrix Chain Order MCQs: 12 Solved GATE and UGC NET Questions with Explanations

Matrix Chain Order looks simple until several dimensions and brackets appear together under exam pressure. The usual traps are confusing associativity with cost, multiplying the wrong three dimensions, or answering a ratio when the question asks for a total. Matrix Chain Order requires careful scalar-cost calculations, optimal parenthesization, and dynamic programming to choose split points.

Related reading: dynamic programming and optimal merge patterns.

The scalar-cost rule and associativity

Multiplying a (p x q) matrix by a (q x r) matrix costs p x q x r scalar multiplications and produces a (p x r) matrix. Everything else in Matrix Chain Order is careful arithmetic built on this rule.

Matrix multiplication is associative. Therefore, (AB)C and A(BC) produce the same final matrix, but their costs can differ. Parenthesization changes the work, not the result.

Concept check. To compute the minimum scalar multiplications in a matrix chain, should we (a) always multiply the smallest matrix first, (b) always multiply the largest first, (c) determine the best order regardless of individual matrix size, or (d) keep the given order? The answer is (c). A local greedy choice can make the remaining chain expensive, so dynamic programming evaluates the complete sequence of splits. (practise this question).

1. ISRO 2023: The complexity of multiplying matrices A and B of orders m x n and n x p is (a) O(m x p), (b) O(m x n^2 x p), (c) O(m x n x p^2), or (d) O(m x n x p). The answer is (d). The result has m x p entries, and each entry needs a dot product across n values, giving m x n x p work. (practise this question).

Warm-up numericals: one grouping and small chains

2. Three matrices: A, B, and C have sizes 4 x 6, 6 x 3, and 3 x 4. The options are (a) 120, (b) 140, (c) 240, and (d) none of these. Compute both choices:

• (AB)C = 4 x 6 x 3 + 4 x 3 x 4 = 72 + 48 = 120

• A(BC) = 6 x 3 x 4 + 4 x 6 x 4 = 72 + 96 = 168

The minimum is 120, option (a). (practise this question).

3. UGC NET 2014: For dimensions 10 x 100, 100 x 5, and 5 x 50, how many times faster is ((A1A2)A3) than (A1(A2A3))? The options are (a) 5, (b) 10, (c) 20, and (d) 100.

• ((A1A2)A3) = 10 x 100 x 5 + 10 x 5 x 50 = 5,000 + 2,500 = 7,500

• (A1(A2A3)) = 100 x 5 x 50 + 10 x 100 x 50 = 25,000 + 50,000 = 75,000

The ratio is 75,000 / 7,500 = 10, so the answer is (b) 10. (practise this question).

The dynamic-programming method worked in full

4. UGC NET 2016: Matrices A1 to A4 have dimensions 30 x 35, 35 x 15, 15 x 5, and 5 x 10. The options are (a) 14,875, (b) 21,000, (c) 9,375, and (d) 11,875.

Use p = [30, 35, 15, 5, 10], m[i,i] = 0, and

m[i,j] = min over k of (m[i,k] + m[k+1,j] + p[i-1] x p[k] x p[j]).

Fill shorter chains first:

For the full chain, the three split costs are:

• k=1: 0 + 4,375 + 30 x 35 x 10 = 14,875

• k=2: 15,750 + 750 + 30 x 15 x 10 = 21,000

• k=3: 7,875 + 0 + 30 x 5 x 10 = 9,375

Thus m[1,4] = 9,375, option (c), with ((A1(A2A3))A4). Notice that options (a) and (b) are the two non-optimal full-chain split costs. (practise this question).

More minimum-multiplication questions

5. UGC NET 2017: For p = [5, 10, 3, 12, 5], the options are 630, 580, 480, and 405. The grouping (A1A2)(A3A4) costs 5 x 10 x 3 + 3 x 12 x 5 + 5 x 3 x 5 = 150 + 180 + 75 = 405. The other valid totals are 580, 630, 1,210, and 1,260, so the answer is 405. (practise this question).

6. Four-matrix classic: With p=10, q=100, r=20, s=5, and t=80, the options are 248,000, 44,000, 19,000, and 25,000. In ((M1(M2M3))M4), the costs are 100 x 20 x 5 = 10,000, 10 x 100 x 5 = 5,000, and 10 x 5 x 80 = 4,000. The total is 19,000. The next-best valid total is 25,000, so 19,000 is the minimum. (practise this question).

7. GATE 2016 NAT: For dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, use A1((A2A3)A4). Its cost is 5 x 20 x 10 + 5 x 10 x 5 + 10 x 5 x 5 = 1,000 + 250 + 250 = 1,500. The answer is 1,500. The next-best grouping costs 1,750, so 1,500 is the minimum. (practise this question).

8. Five matrices, NAT: For p = [30, 35, 15, 5, 10, 20], the DP table gives a minimum of 11,875. The winning grouping is ((A1(A2A3))(A4A5)): A2A3 costs 2,625, A1(A2A3) costs 5,250 more, A4A5 costs 1,000, and the final multiplication costs 3,000. Total: 2,625 + 5,250 + 1,000 + 3,000 = 11,875. The four top-level split costs are 28,125, 27,250, 11,875, and 15,375, so the third split is optimal. (practise this question).

Theory and counting questions

9. DP complexity: If Ai has dimension p[i-1] x p[i], what is the time complexity of the dynamic-programming solution: (a) O(n^3), (b) O(n^2), (c) O(2^n), or (d) O(n)? There are O(n^2) subchain cells and each tries O(n) split points. The answer is (a) O(n^3) time, with O(n^2) space. (practise this question).

10. Number of parenthesizations: Four matrices can be fully parenthesized in how many ways? The answer is 5, the third Catalan number:

(A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4), and (((A1A2)A3)A4).

This rapidly growing choice count is why DP is preferable to brute force. (practise this question).

The tricky ones examiners love

11. GATE 2018: For F1 to F5 with dimensions 2 x 25, 25 x 3, 3 x 16, 16 x 1, and 1 x 1000, which original adjacent pairs are explicitly multiplied in the optimal parenthesization? The options are (a) F1F2 and F3F4, (b) F2F3, (c) F3F4, and (d) F1F2 and F4F5.

The adjacent-pair costs are 150, 1,200, 48, and 16,000 respectively. The optimal grouping is (F1(F2(F3F4)))F5, so only F3F4 is directly multiplied before becoming part of an intermediate. The answer is (c). The 1 x 1000 tail makes multiplying by F5 early very expensive. (practise this question).

12. Coal India 2017: Which value does not represent the total multiplications for matrices of sizes 20 x 2, 2 x 30, 30 x 12, and 12 x 8: (a) 1,232, (b) 3,680, (c) 10,320, or (d) 8,850?

The five valid parenthesizations cost 10,320, 3,120, 1,232, 3,680, and 8,880. Therefore 8,850, option (d), is not achievable. It is deliberately close to 8,880, so list the valid totals before eliminating. (practise this question).

Common mistakes on Matrix Chain MCQs

• Confusing result and cost: associativity preserves the result, not the number of scalar multiplications.

• Shifting the dimension array: n matrices require n+1 values. Write every Ai as p[i-1] x p[i] first.

• Using a greedy shortcut: multiplying the apparently smallest pair first does not guarantee a global minimum.

• Dropping a shared dimension: recompute the winning split once after finding it. One wrong factor changes every later total.

• Answering the wrong quantity: distinguish a minimum total, a times-faster ratio, an impossible total, and an explicitly computed pair.

The Algorithm Basics MCQs set covers general complexity vocabulary and line-by-line tracing. Greedy Algorithms and Huffman Coding MCQs explains when a local choice is justified; Matrix Chain Order instead compares every split in a dynamic-programming table.

The short version and where to practise next

Remember p x q x r, keep the final result separate from the running cost, and fill the DP table from chain length 2 up to n. The answer is m[1,n], found in O(n^3) time and O(n^2) space, while the number of possible groupings follows the Catalan numbers.

Attempt the complete Matrix Chain set through GATE Guidance by Sanchit Sir, strengthen the implementation side with DSA using Java, and browse the wider GATE CS exam catalogue for the full Dynamic Programming track. Solving these 12 first, then attempting additional practice questions without looking at the answers, is more useful than passively reading twenty explanations.