# 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? Dec 10, 2019 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, 2019 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. Dec 10, 2019 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.