Solve matrix equations of the form: $X^T A X = B_1$ and $X A X^T = B_2$ I have trouble solving the following two matrix equations for unknown $X \in \mathbb{R}^{n \times n}$:
$$X^T A X = B_1$$
$$X A X^T = B_2$$
where, $A$, $B_1$ and $B_2$ are all $n \times n$ symmetric matrices such that $A^n = I_n$, and $B_1 \neq B_2$
There is a solution for $X$ if $A$ and the $B$'s are positive-definite, but is there an analytical solution for any matrices?
Edit:
Is there a way to solve this when $A^n \neq I_n$? I'm interested in the case where $A$, $B_1$, $B_2$ and $X$ are matrices of one-to-one mappings, i.e., $A_{ij}=A_{ji}=1$ if $i$ maps to $j$, and $0$ otherwise.
For example: $$A = \begin{bmatrix}
    0 & 1 & 0 & 0 & 0 \\
    1 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 1  & 0\\
    0 & 0 & 1 & 0  & 0\\
    0 & 0 & 0 & 0  & 1
\end{bmatrix}$$
 A: Here are some observations.

*

*Since $A$ is real symmetric and $A^n=I_n$, it is necessarily equal to $I_n$ when $n$ is odd and it is orthogonally similar to some $I _r\oplus -I_{n-r}$ when $n$ is even. At any rate, when $A=I_n$, the system of equations is solvable if and only if $B_1$ and $B_2$ are positive semidefinite matrices with the same spectrum, and the general solution is given by $X=Q\sqrt{B_1}$ where $Q$ is any orthogonal matrix such that $QB_1Q^T=B_2$.

*In general, the system of equations implies that $B_1A=X^TAXA$ and $B_2A=XAX^TA$. Therefore it is solvable only if $B_1A$ and $B_2A$ have the same spectrum.

*If we left-multiply the first equation by $XA$ and right-multiply the second one by $AX$, we obtain $XAB_1=XAX^TAX=B_2AX$. Hence $\operatorname{vec}(X)\in\ker\big((B_1A)\otimes I_n-I_n\otimes(B_2A)\big)$.

*In relation to points 2 and 3, consider the case where $AB_1$ and $B_2A$ are diagonalisable matrices with a common spectrum $\{\lambda_1,\ldots,\lambda_n\}$ consisting of distinct real eigenvalues. For each $\lambda_i$, let $v_i$ be a corresponding left eigenvector of $AB_1$ and $u_i$ be a corresponding right eigenvector of $B_2A$. Since the $\lambda_i$s are distinct, $\ker\big((B_1A)\otimes I_n-I_n\otimes(B_2A)\big)$ has dimension $n$. Thus the general solution to $XAB_1=B_2AX$ is given by $X=\sum_ic_iu_iv_i^T=U\operatorname{diag}(c)V^T$. Our system of equations can then be rewritten as
$$
\begin{aligned}
\operatorname{diag}(c)A_1\operatorname{diag}(c)&=S_1,\\
\operatorname{diag}(c)A_2\operatorname{diag}(c)&=S_2,\\
\end{aligned}
$$
where
$$
A_1=U^TAU,\quad A_2=V^TAV,\quad S_1=V^{-1}B_1(V^T)^{-1},\quad S_2=U^{-1}B_2(U^T)^{-1}.
$$
That is,
$$
(cc^T)\circ A_1=S_1,\quad (cc^T)\circ A_2=S_2.
$$
Thus a necessary condition for solvability is that $(S_1)_{ij}=0$ whenever $(A_1)_{ij}=0$ and $(S_2)_{ij}=0$ whenever $(A_2)_{ij}=0$. If $A_1$ and $A_2$ happen to be entrywise nonzero, the system of equations is solvable if and only if the entrywise division of $S_1$ by $A_1$ and the entrywise division of $S_2$ by $A_2$ are both equal to some rank-one positive semidefinite matrix $cc^T$.

