Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.


It is clear if there is a solution $X$ of permutation matrix form then $XX'=I$ solution exists. Is there any truth in converse statement?



On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$
The answer is no for $n\ge4$. The matrices
\begin{equation}
A=\left(\begin{array}{rrrr}
1 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{array}\right)\text{ and }
B=\left(\begin{array}{rrrr}
1 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{array}\right)
\end{equation}
have the same characteristic polynomial $\chi(x)=x^4 - 2x^3 - x^2 + 2x$, so they are orthogonally equivalent (by the spectral theorem). However, they are not conjugate by a permutation matrix, because $A$ has a row with three $1$'s, while $B$ does not.


