# Arithmetic complexity of matrix powering with non-commutative entries

Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative.

What is the complexity class and circuit and formula complexity of computing $\mathsf{Tr}(M^d)$ when $d=O(m)$ and $n=O(m^2)$?

Can this class be algebraic class $\mathsf{VNP}$?

• Did you mean $\mathsf{VNP}_{nc}$ (the non-commutative version of $\mathsf{VNP}$)? Since you are computing noncommutative polynomials... Note that computing noncommutative determinant is hard (#P-hard in characteristic zero, $\mathsf{Mod_p P}$-hard in characteristic $p$), which should be roughly the same as your question. Apr 5 '16 at 15:50
• @JoshuaGrochow I am sorry what if the non-commutative elements have matrix repressentation?
– user34945
Apr 7 '16 at 1:06
• You mean the $x_i$ are themselves matrices? Apr 7 '16 at 10:17
• @JoshuaGrochow hmmm... yes in general many non-commutative structures have matrix representation.
– user34945
Apr 7 '16 at 17:44