# When are two binary matrices simultaneously equivalent to their transpose?

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.

• Is the first phrase true? (The word `permutation' confuses me...) – Ilya Bogdanov Nov 15 '16 at 9:11
• @IlyaBogdanov, Thank you for pointing it out. Hope, it is correct now. – Supriyo Nov 15 '16 at 9:16

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 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$.
• @Igor. The best proof that $A^t$ is conjugated to $A$ is via the the invariant theory for matrices over a PID $R$. The first theorem says that $M,N\in M_{p\times q}(R)$ are equivalent iff they have the same invariant factors. The $k$th invariant factor of $M$ is the gcd of all of its minors of size $k$. The second theorem is that $A_1,A_2\in M_n(K)$ ($K$ a field) are similar (conjugate to each other) iff $A_1-XI_n$ and $A_2-XI_n$ are equivalent in $M_n(K[X])$. Obviously, $A^t-XI_n$ and $A-XI_n$ have the same minors, hence $A$ and $A^t$ are similar. See my Springer-Verlag book Matrices. – Denis Serre Nov 15 '16 at 11:35