I am looking for references to anything interesting thats know about matrix product chains that take the vector $\{1\}$ to another vector $\{n\}$ (the end result of an addition chain). Each matrix operation adds two entries together to form a new entry and chooses to keep or discard each entry used in the sum. The maximal dimension of the vector at an arbitrary step is tightly bound by the small step count of the addition chain. It's the number of temporary variables the addition chain needs to be computed. So we have: $\{n\} = M_{l(n)}..M_1M_2\{1\}$.

Splitting the matrix product into two:

$P = M_1M_2...M_p$.

$Q = M_{p+1}M_{p+2}...M_{l(n)}$.

Gives a pair of problems. One an addition sequence problem and the other a vector addition chain problem. This is used for the fastest known algorithm for computing optimal addition chains. This is my area of interest.

When I try searching for matrix product chains I am swamped by the standard dynamic programming exercise to compute a matrix product efficiently. So can't find anything interesting on matrix product chains at all.


closed as unclear what you're asking by Anthony Quas, David Handelman, Chris Godsil, John Klein, Mark Wildon Dec 29 '18 at 17:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.