On $XX'=I$ such that $AX=XB$ is true

Question

Given list of symmetric matrices $\{A_i,B_i\}_{i=1}^r\in\Bbb R^{n\times n}$ where $r\in\Bbb N$ is arbitrary what is a good description of collection of $X\in\Bbb R^{n\times n}$ such that $$XX'=I$$ $$A_iX=XB_i$$ holds?

Note: $X'$ means the transpose of $X$.

(1) Is there a test to see if there is no such $X$?

(2) Is it easy to see if we find one such $X$ we can find ALL such $X$ from finding $U\in\Bbb R^{n\times n} $ such that $UU'=I$ and $UA_i=A_iU$ or $B_iU=UB_i$ at every $i\in\{1,\dots,r\}$?

(3) What if we have $\Bbb F_{p^r}$ instead of $\Bbb R$?

Answer 1

(1) Robert Israel's reduction to testing if $det(X(\vec{t}))$ is identically zero is valid, however, doing this test deterministically is a long-standing open problem in computational complexity, that would imply fairly strong computational lower bounds that currently seem out of reach.

Nonetheless, there is an efficient algorithm that solves your problem by a different route: Tatiana G. Gerasimova, Roger A. Horn, Vladimir V. Sergeichuk, "Simultaneous unitary equivalences."

(2) follows from the usual proof that the set of isomorphisms between two objects in any category is a coset of the automorphism group of either object.

(3) Well, (2) is certainly valid regardless of the field. I'm not sure about (1), but my guess would be that there exist efficient algorithms for that as well, given that efficient algorithms for k-tuple conjugacy and many related problems exist that work over arbitrary fields (e.g. Brooksbank-Luks)

Answer 2

Considering $A_i X = X A_i$ as a set of homogeneous linear equations in the entries of $X$, we can solve them, obtaining the parametric solution $X(t) = \sum_{i=1}^p t_i X_i$ where $t_i$ are arbitrary parameters. We need $X$ to be invertible: since $\det(X(t))$ is a polynomial in the $t_i$, either it will always be $0$ or it will be nonzero for almost all $t$. Now there is a theorem (see e.g. Theorem 12.36 in Rudin, "Functional Analysis") that if $A$ and $B$ are normal, $X$ invertible, with $X^{-1} A X = B$ and $X = UR$ is the polar decomposition of $X$, then $U^{-1} A U = B$. So this will find a solution if there is one.

Answer 3

A necessary condition is that, for every word $w(x,y)$ in two letters, we have $${\rm Tr}w(A_i',A_i)={\rm Tr}(B_i',B_i).$$ If $r=1$ (one pair only), this condition is also sufficient; this is Specht's Theorem. Notice that the symmetry assumption is not important here.

In the present case, a necessary condition is that for every word $w$ in $2r$ letters, one has $$w(A_1,A_1',\ldots,A_r,A_r')=w(B_1,B_1',\ldots,B_r,B_r').$$ Whether it is also a sufficient condition is unclear to me.