9
$\begingroup$

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.

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

1 Answer 1

Reset to default
7
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Denis, what is a better proof that you allude to in the last paragraph? $\endgroup$
    – Igor Khavkine
    Commented Nov 15, 2016 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
    Commented Nov 15, 2016 at 11:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .