Matrix chain multiplication recurrence and its solution

Question

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.

In the classical matrix chain multiplication problem, we wish to minimize the total number of scalar multiplications. In this problem, we consider the all intermediate matrices arising in the computation (including the final result but excluding the original matrices), and the cost of a specific order is the maximal number of entries of such an intermediate matrix. As usual, we want to minimize the cost.

As an example, if $n = 2$ the answer is simply $d_0d_2$, and if $n = 3$, then there are two orders:

• $(A_1A_2)A_3$, in which the intermediate matrices are $A_1A_2,A_1A_2A_3$. The cost is therefore $\max(d_0d_2,d_0d_3)$.
• $A_1(A_2A_3)$, in which the intermediate matrices are $A_2A_3,A_1A_2A_3$. The cost is therefore $\max(d_1d_3,d_0d_3)$.

Denote by $C_{ij}$ the optimal cost of multiplying $A_i,\ldots,A_j$. We can write the following recurrence for $C_{ij}$:

$$C_{ij}=\min_{i \leq k <j} \max \{C_{i,k},C_{k+1,j},d_{i-1}d_j\},$$

with base case $C_{ii} = 0$.

How do we get this recurrence?

Answer 1

We get the recurrence by considering all possible ways of breaking up $A_i \times \cdots \times A_j$.

Specifically, we consider $(A_i \times \cdots \times A_k) \times (A_{k+1} \times \cdots \times A_j)$ for all relevant values of $k$, which are $i,\ldots,j-1$.