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.

  • $\begingroup$ Is the first phrase true? (The word `permutation' confuses me...) $\endgroup$ – Ilya Bogdanov Nov 15 '16 at 9:11
  • $\begingroup$ @IlyaBogdanov, Thank you for pointing it out. Hope, it is correct now. $\endgroup$ – 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 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$.

  • 1
    $\begingroup$ Denis, what is a better proof that you allude to in the last paragraph? $\endgroup$ – Igor Khavkine Nov 15 '16 at 11:24
  • 3
    $\begingroup$ @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. $\endgroup$ – Denis Serre Nov 15 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.