The minimum number of scalar multiplications required to compute the…

Concept

For a chain of matrices, the cost of one multiplication of a p×q matrix by a q×r matrix is p·q·r scalar multiplications. The TOTAL cost depends on the order (parenthesization) in which the products are taken, not on the final result. The Matrix-Chain-Order problem finds the parenthesization of minimum total cost using dynamic programming: m[i,j] = min over every split point k of ( m[i,k] + m[k+1,j] + pᵢ₋₁·pₖ·pⱼ ), where the dimension sequence is ⟨p₀, p₁, …, pₙ⟩.

Setup

The sequence ⟨5, 10, 3, 12, 5⟩ defines four matrices:

• A₁ is 5×10

• A₂ is 10×3

• A₃ is 3×12

• A₄ is 12×5

Application

With four matrices there are three ways to make the outermost split. Evaluate each, reusing the cheapest cost of every sub-chain:

1. Cost of each adjacent pair: A₁A₂ = 5·10·3 = 150; A₂A₃ = 10·3·12 = 360; A₃A₄ = 3·12·5 = 180.

2. Outermost split after A₁ → A₁·(A₂A₃A₄). Cheapest cost of A₂A₃A₄ is 330, then A₁ (5×10) times the (10×5) result: 5·10·5 = 250. Total = 330 + 250 = 580.

3. Outermost split after A₂ → (A₁A₂)·(A₃A₄). Pair costs 150 and 180; the (5×3) result times the (3×5) result: 5·3·5 = 75. Total = 150 + 180 + 75 = 405.

4. Outermost split after A₃ → (A₁A₂A₃)·A₄. Cheapest cost of A₁A₂A₃ is 330, then the (5×12) result times A₄ (12×5): 5·12·5 = 300. Total = 330 + 300 = 630.

5. Take the smallest of the three totals: min(580, 405, 630) = 405.

Cross-check

The winning order (A₁A₂)·(A₃A₄) is balanced: it first collapses both ends to small 5×3 and 3×5 matrices, so the final product is only 5·3·5 = 75 — far cheaper than letting the large inner dimension 12 drive the last multiplication (which costs 250 or 300 in the other orders). Re-adding 150 + 180 + 75 confirms 405.

Minimum number of scalar multiplications = 405.