# Computing tr(ABCD...)

Suppose we have $$k$$ $$n\times n$$ matrices $$A,B,C,\ldots$$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, computing

$$\text{tr}(ABC\ldots)$$

A related problem of computing vector matrix product $$v'ABC$$ can be done in $$O(n^2)$$ time by skipping most of the computation needed for the full matrix product, so I'm wondering if there's a trick to speed up the trace as well

• By any chance, is the resulting matrix symmetric? Then could compute $v^\top ABC \ldots v$ for $v \sim \mathcal N(0^n, I_n))$, and your expectation should be the trace, unless I made a mistake. Nov 15, 2021 at 11:32
• Yes, that works (even for nonsymmetric), but it's not clear this is better than approximating full matrix product in a similar way, just put v's in the middle: AB...Cvv'DE.. is equal to the matrix product in expectation Nov 16, 2021 at 22:29
• Should be the same, by the cyclic property of trace: $tr(AB...Cvv'DE..F)=tr(v'DE..FAB...Cv)$. But it already gives you the solution, no? (product of Gaussians should have decent concentration) Nov 17, 2021 at 7:30
• So here it seems that approximating trace has same cost as approximating the matrix product, since you can view this trick as taking trace of the matrix product approximation. I was curious if trace is fundamentally easier than full matrix product (like is the case with vector/matrix product), which seems like it isn't Nov 17, 2021 at 20:08

For the worst-case time complexity, no algorithm faster than $$\Theta(n^{\omega})$$ time is known, even for the approximation version.
Indeed, there is a simple reduction from the triangle counting problem to the trace computation of a product matrix. Let $$A$$ be an adjacent matrix of an undirected graph, then $$\mathrm{tr}(A^3)/2$$ is the number of triangles of the graph. Note that this reduction preserves approximation factors.