# Are unitarily equivalent permutation matrices permutation similar?

Two matrices $$A, B \in \mathbb R^{n \times n}$$ are called unitarily equivalent if there exists an unitary matrix $$U \in \mathbb C^{n \times n}$$ such that $$A = U B U^{\ast}$$. If in addition $$U$$ is a permutation matrix, then we call $$A$$ and $$B$$ permutation similar.

Suppose that $$A$$ and $$B$$ are unitarily equivalent permutation matrices. Are they permutation similar too?

Here's a direct proof that if permutation matrices $$A,B$$ (of size $$n\ge 0$$) have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable) then they are conjugate as permutations, i.e., have the same cycle decomposition.

If $$A,B$$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor while reducing the matrix size). So we can suppose there are no cycles of common length in $$A$$ and $$B$$. In this case, we have to prove that $$n=0$$.

Consider a cycle of maximal length $$m$$ occurring in either $$A$$ or $$B$$, say in $$A$$. Then $$\xi=\exp(2i\pi/m)$$ is a root of the characteristic polynomial of $$A$$, and hence of $$B$$. But since $$B$$ has only cycles of length $$, its characteristic polynomial does not vanish at $$\xi$$, and we get a contradiction.

• I agree with the proof. But this only partially answer the question, does it? – shuhalo Dec 10 '19 at 17:36
• @shuhalo Why? I assume that they're linearly conjugate, which is even weaker than unitarily conjugate, and obtain that they're conjugate as permutations, which is exactly what you're asking. – YCor Dec 10 '19 at 19:06
• Alternatively the trace of $A^m$ counts the number of elements whose orbit has size dividing $m$ and so if they are linearly conjugate they have the same number of cycles of each size. – Benjamin Steinberg Dec 10 '19 at 21:24

The answer is yes by an old theorem of Brauer. In fact, permutation matrices are conjugate over any field if and only if they are conjugate by permutation matrices. See this beautiful proof by Kovacs https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/14.2.127.

Edit. Let me add that this was originally proved in the paper Brauer, Richard, On the connection between the ordinary and the modular characters of groups of finite order. Ann. of Math. (2) 42 (1941), 926–935. Laci Kovacs gave a very short elegant proof that works in all characteristics in the link. I believe the easiest characteristic $$0$$ proof is the one I sketched in the comments to @Ycor's answer, namely that if $$A$$ and $$B$$ are conjugate matrices, then $$A^m$$ and $$B^m$$ have the same trace for all $$m>0$$. This means that the corresponding permutation matrices have the same number of elements with an orbit of size dividing $$m$$ for all $$m$$. An easy inductive argument (or Mobius inversion argument on the divisor poset) then shows they have the the same number of orbits of each size and hence are conjugate in the symmetric group.

• Hello, Benjamin. Your answer is only a link. meta.stackexchange.com/a/8259/271150 – Mindwin Dec 11 '19 at 13:17
• @Mindwin I also pointed out this is an old, but well known result of Brauer (which was published in Annals in the the 40s if I remember correctly). The proof of Kovacs is very short and elegant and covers all fields and that is why I provided the link. I indicated a short proof in characteristic 0 at the bottom of Yves' proof. The characteristic p proof is more complicated so I leave the link. – Benjamin Steinberg Dec 11 '19 at 14:26
• BTW, James Propp asked on MO a number of years ago if an analogue holds for arbitrary mappings (mathoverflow.net/questions/198144/…) which lead me to write the paper cambridge.org/core/journals/canadian-mathematical-bulletin/…. – Benjamin Steinberg Dec 11 '19 at 14:51