Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) = g_m(A\mathbb{x})$. If yes, then output such an $A$. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the family of iterated matrix multiplication polynomials. Two popular variants of the iterated matrix multiplication polynomial are: IMM$_{w,d}$ (the $(1,1)$ entry of the product of $d$ many $w\times w$ symbolic matrices) and Tr-IMM$_{w,d}$ (the trace of the product of $d$ many $w\times w$ symbolic matrices). The families - Det, IMM and Tr-IMM - are VBP-complete under $p$-projections, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is 'yes' for Det and Tr-IMM (modulo the use of randomness).

The above result may appear a bit surprising as the complexity of equivalence testing for IMM and that for Det are quite different over rationals: a randomized polynomial-time equivalence testing for IMM over rationals is known [Kayal,Nair,Saha,Tavenas 2019], whereas [Garg,Gupta,Kayal,Saha 2019] showed that equivalence testing for Det over rationals is integer factoring hard (under randomized reductions and assuming GRH). To our knowledge, the complexity of equivalence testing for Tr-IMM was not known before this work. We show that, despite the syntactic similarity between IMM and Tr-IMM, equivalence testing for Tr-IMM and that for Det are randomized polynomial-time Turing reducible to each other over any field of characteristic zero or sufficiently large. The result is obtained by connecting the two problems via another well-studied problem in computer algebra, namely the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following:

1.Testing equivalence of polynomials to Tr-IMM$_{w,d}$, for $d\geq 3$ and $w\geq 2$, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Det$_w$, the determinant of the $w \times w$ matrix of formal variables. (Here, $d$ need not be a constant.)

2. FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors $\{$Tr-IMM$_{w,3}\}_{w \in \mathbb{N}}$.

These results, in conjunction with the randomized poly-time reduction (shown in [GGKS19]) from determinant equivalence testing to FMAI, imply that the four problems - FMAI, equivalence testing for Tr-IMM and for Det, and the $3$-tensor isomorphism problem for the family of matrix multiplication tensors - are randomized poly-time equivalent under Turing reductions.