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$?



On $XX'=I$ such that $AX=XB$ is true
(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."](http://arxiv.org/abs/1112.4446v1)


(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](http://dx.doi.org/10.1016/j.jalgebra.2008.07.014))


