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. Using Jordan canonical form to evaluate $P$ is a computationally difficult task.