Consider the following problem:
Given a matrix $M$ we want to optimize the number of additions in the multiplication algorithm for computing $v \mapsto Mv$.
I find this problem interesting because of its ties with the complexity of matrix multiplication (this problem is a restricted version of matrix multiplication).
What is know about this problem?
Is there any interesting results relating this problem to the complexity of matrix multiplication problem?
The answer to the problem seems to involve finding circuits with only addition gates. What if we allow subtraction gates?
I am looking for reductions between this problem and other problems.