Matrix-chain multiplication

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• LCS recurrence on a mismatch? from Lesson 5.1.3
• Knapsack DP time? from Lesson 5.1.2
• Strassen exponent? from Lesson 4.1.2

1 · The Hook

🎣

Multiplying A₁A₂A₃ with sizes 10 × 100, 100 × 5, 5 × 50 costs 7,500 scalar multiplications as (A₁A₂)A₃ but 75,000 as A₁(A₂A₃). Matrix multiplication is associative, so the answer is the same; only the cost differs. Choosing the best parenthesisation is a classic interval DP, and a GATE regular.

2 · Predict First

🤔

Multiplying a p × q matrix by a q × r matrix costs p·q·r scalar multiplications. For A₁ (10 × 100), A₂ (100 × 5), A₃ (5 × 50), compute the cost of both orders.

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

(A₁A₂)A₃: 10·100·5 + 10·5·50 = 5,000 + 2,500 = 7,500. A₁(A₂A₃): 100·5·50 + 10·100·50 = 25,000 + 50,000 = 75,000.

Setting

Matrices A₁ … Aₙ, with Aᵢ of size p_{i−1} × pᵢ (dimension list p₀, p₁, …, pₙ). Find the parenthesisation with the fewest scalar multiplications.

Recurrence

m[i][j] = minimum cost of computing Aᵢ … Aⱼ.

• m[i][i] = 0.
• m[i][j] = min over i ≤ k < j of ( m[i][k] + m[k + 1][j] + p_{i−1}·p_k·p_j ) (split after A_k).

Fill by increasing chain length; record the best k in s[i][j] to rebuild the parenthesisation.

Cost

Θ(n²) subproblems × Θ(n) choices each = Θ(n³) time, Θ(n²) space.

How many parenthesisations?

The number of ways to fully parenthesise n matrices is the Catalan number C_{n−1}: 1, 1, 2, 5, 14, 42 for n = 1 … 6: exponential, so brute force is hopeless.

Worked example: p = (10, 20, 30, 40, 30), four matrices

• Length 2: m[1][2] = 10·20·30 = 6,000; m[2][3] = 20·30·40 = 24,000; m[3][4] = 30·40·30 = 36,000.
• m[1][3] = min(0 + 24,000 + 10·20·40, 6,000 + 0 + 10·30·40) = min(32,000, 18,000) = 18,000.
• m[2][4] = min(0 + 36,000 + 20·30·30, 24,000 + 0 + 20·40·30) = min(54,000, 48,000) = 48,000.
• m[1][4] = min(k=1: 0 + 48,000 + 10·20·30 = 54,000; k=2: 6,000 + 36,000 + 10·30·30 = 51,000; k=3: 18,000 + 0 + 10·40·30 = 30,000) = 30,000, order ((A₁A₂)A₃)A₄.

4 · Visual

fill order: diagonal by diagonal (chain length 1, 2, 3, ...)
m[i][j] looks left along its row and down along its column

5 · Worked Examples

Example 1 Easy

Cost of multiplying a 4 × 6 matrix by a 6 × 3 matrix?

Solution

4 · 6 · 3 = 72.

Example 2 Medium

Dimensions p = (2, 3, 4, 5) (three matrices). Minimum cost?

Solution

(A₁A₂)A₃: 2·3·4 + 2·4·5 = 24 + 40 = 64; A₁(A₂A₃): 3·4·5 + 2·3·5 = 90. Minimum 64.

Example 3 GATE

Number of ways to fully parenthesise a product of 5 matrices?

Solution

Catalan C₄ = 14.

6 · GATE Traps

⚠️

• The split cost is p_{i−1}·p_k·p_j, using the outer dimensions and the split dimension.
• Fill by chain length, not row by row.
• Θ(n³) time, Θ(n²) space.
• Parenthesisations: C_{n−1} for n matrices (not Cₙ).

7 · Memory Hook

🧠

"Split at k: left cost + right cost + outer × split × outer."

8 · Connect the Dots

Matrix chain is DP over intervals. Next: DP over amounts, subset sum, coin change and rod cutting, where the table index is a number to be reached.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksMatrix chain

Dimensions p = (10, 20, 30, 40, 30). Minimum scalar multiplications?

Numerical answer: ________

Q2NAT2 marksMatrix chain

Dimensions p = (10, 30, 5, 60). Minimum scalar multiplications?

Numerical answer: ________

Q3NAT2 marksMatrix chain

Dimensions p = (40, 20, 30, 10, 30). Minimum scalar multiplications?

Numerical answer: ________

Q4NAT1 markCatalan

Number of full parenthesisations of a product of 6 matrices?

Numerical answer: ________

Q5MCQ1 markComplexity

The matrix-chain DP for n matrices runs in:

• (A) Θ(n log n)
• (B) Θ(n³)
• (C) Θ(n²)
• (D) Θ(2ⁿ)

10 · Rule Card

• m[i][i] = 0; m[i][j] = min_k (m[i][k] + m[k+1][j] + p_{i−1}p_k p_j).
• Fill by chain length; s[i][j] stores the best k.
• Θ(n³) time, Θ(n²) space; parenthesisations C_{n−1}.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

matrix-chain multiplicationdimension list p₀ … pₙsplit cost p_{i−1}p_k p_jinterval DPfill by chain lengthCatalan number of parenthesisations

12 · Answer Vault