# Variation on Matrix Chain problem -- compute diagonal only?

How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square)

First computing the matrix product and then extracting the diagonal can be suboptimal. Consider diagonal of outer product of two vectors uv'. We could get the diagonal by multiplying two vectors pointwise.

$$\text{diag}(uv')=u\odot v$$

More generally, we can compute diagonal of a square matrix product by viewing it as sum of outer products of rows/columns and applying the trick above $$AB=\sum_i u_i v_i' = \sum_i u_i \odot v_i$$

Use the standard dynamic programming algorithm to find the optimal cost of multiplying every subsequence of your matrices $$A_1,\ldots,A_m$$, which are of dimensions $$d_1 \times d_2, d_2 \times d_3, \ldots, d_m \times d_{m+1}$$. Assuming that the product matrix is $$n \times n$$ and that the optimal cost is $$c(A_i \cdots A_j)$$, the optimal cost for computing the diagonal of the product is $$\min_{1 \leq i \leq n-1} c(A_1 \cdots A_i) + c(A_{i+1} \cdots A_m) + nd_{i+1}.$$ (The original problem has $$n^2 d_{i+1}$$ instead.)