In this question, the matrices are square and real and the polynomials have real coefficients, but feel free to mention other fields if that is interesting.


Let $\chi(M)$ denote the characteristic polynomial of a matrix $M$.


For two pairs of matrices, let us write $(A\_1,B\_1)\stackrel\chi\sim (A\_2,B\_2)$ if
$$ \chi(p(A\_1,B\_1)) = \chi(p(A\_2,B\_2)) $$
for every polynomial $p$ in two non-commuting variables.


A sufficient but not necessary condition for $(A\_1,B\_1)\stackrel\chi\sim (A\_2,B\_2)$ is that $A\_2=X^{-1}A\_1X$ and $B\_2=X^{-1}B\_1X$ for some non-singular $X$.


***Q0.*** I'm sure this is not my invention. Where is it studied?


***Q1.*** Can this relation be characterised in a finite way (without calling on *every* polynomial)?


***Q2.*** How can this relation be tested for? Assume exact real arithmetric or, if you prefer, assume the matrices are rational.



Eigenvalues of polynomials of two matrices
The problem of simultaneous conjugation has been studied for more than 50 years. First off, it has been proved that the ring of $GL(n)$-invariants on $M(n)\times M(n)$ or, more generally, on $M(n)^m$ is generated by the coefficients of the characteristic polynomials $\chi(p(A\_1,\ldots,A\_m))$ where $p$ runs through all non-commutative monomials. In characteristic zero, this is due to to K. S. Sibirskiı̆ (Algebraic invariants of a system of matrices, Sibirsk. Mat. Ž. 9 (1968), 152–164) and, independently, by C. Procesi (The invariant theory of n × n matrices, Advances in Math. 19 (1976), 306–381). In positive characteristic and even over $\mathbb Z$ this is due to S. Donkin (Invariants of several matrices, Invent. Math. 110 (1992), 389–401).


Thus the equivalence relation $\overset\chi\sim$ is simply that given by the GIT-quotient $M(n)^m\to M(n)^m/\!/GL(n)$. In particular, the usual theorems of GIT apply: Two $m$-tuples of matrices are equivalent if and only if the closures of their simultaneous conjugacy classes intersect. In particular, if these conjugacy classes are closed then $\overset\chi\sim$ coincides with simultaneous conjugacy.


The question of when a simultanoues conjugacy class is closed has been studied by R. W. Richardson (Conjugacy classes of n-tuples in Lie algebras and algebraic groups. Duke Math. J.57(1988), 1–35). He shows this to be the case if and only if the subalgebra of $M(n)$ generated by $A\_1,\ldots,A\_m$ is semisimple. This holds for example if $M(n)$ is generated by $A\_1,\ldots,A\_m$ which, for $m\ge2$, is the generic case.


As for the computational aspects of your questions it has been shown by Procesi (loc. cit.) in characteristic zero that it suffices to check the traces of $p(A\_1,\ldots,A\_m)$ where $p$ is a monomial of degree at most $2^n-1$. As far as I remember this is far from optimal and the true bound should be polynomial in $n$.


Finally, for testing equivalence of two $m$-tuples it suffices to test a so-called separating set of invariants, i.e., invariants which separate everything which can be separated by invariants. For this, a paper by H. Derksen and V. Makam (Algorithms for orbit closure separation for invariants and semi-invariants of matrices Algebra Number Theory 14 (2020), 2791–2813) might be useful. In Thm.~1.14 they derive the bound $O(n\log n)$ on the degree of sparating invariants.


