complexity of matrix multiplication

Question

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate $\operatorname{tr}\{ABCD\}$? Note that $\operatorname{tr}$ means the trace of a matrix.

Answer 1

As you say, evaluating a trace is order $n^2$-you have $n$ diagonal terms, each of which takes $n$ multiplies and $n$ adds to evaluate. The final $n$ additions are dominated. To do trace $ABCD$ I don't see anything better than first finding $AB$ and $CD$, each of which are $n^3$ operations, or, if you are more clever $n^{2.373}$. Then use your $n^2$ trace calculation, giving order $n^3$ or $n^{2.373}$. This will work for any number of matrices. There might be something more clever out there.