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?
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.
You question is easily seen to be equivalent to the following : is it true that two unoriented finite graphs are isomorphic if and only if they are isospectral ? Unfortunately the answer is no and this is well known. Cf. e.g. https://en.wikipedia.org/wiki/Spectral_graph_theory
