For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $B^t = P^{-1}BP$ hold simultaneously? I am particularly looking for some easy conditions on these matrices $A$ and $B$.


A matrix is conjugate to its transpose, see [Matrix is conjugate to its own transpose](https://math.stackexchange.com/questions/62497/matrix-is-conjugate-to-its-own-transpose). Using Jordan canonical form to evaluate $P$ is a computationally difficult task.



When are two binary matrices simultaneously equivalent to their transpose?
Clearly, a necessary condition is that for every word $w$ in two letters, one has
$${\rm Tr}\,w(A^t,B^t)={\rm Tr}\,w(A,B).$$
Equivalently,
$${\rm Tr}\,\hat w(A,B)={\rm Tr}\,w(A,B),$$
where $\hat w$ is the reverse word. Namely, if $w=x^\ell y^mx^n\cdots$, then $\hat w=\cdots x^ny^mx^\ell$.
Unless the word $\hat w$ be conjugated (in the free group ${\mathbb F}\_2$) to $w$, which means $w=w\_1w\_2$ and $\hat w=w\_2w\_1$, this is a non-trivial condition.


I suspect that this necessary condition is also sufficient.


I doubt that the assumption that the entries are $0,1$ simplifies anything.


By the way, the Jordan form is not a good way to prove that $A^t$ is conjugated to $A$, because it does not show that the change-of-basis matrix $P$ has entries in the smallest field containing the entries of $A$.


