By shuhalo

2019-12-10 14:33:01 8 Comments

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?


@Benjamin Steinberg 2019-12-10 14:55:17

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

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.

@Mindwin 2019-12-11 13:17:11

Hello, Benjamin. Your answer is only a link.

@Benjamin Steinberg 2019-12-11 14:26:57

@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 2019-12-11 14:51:21

BTW, James Propp asked on MO a number of years ago if an analogue holds for arbitrary mappings (…) which lead me to write the paper…‌​.

@YCor 2019-12-10 15:50:27

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 $<m$, its characteristic polynomial does not vanish at $\xi$, and we get a contradiction.

@shuhalo 2019-12-10 17:36:50

I agree with the proof. But this only partially answer the question, does it?

@YCor 2019-12-10 19:06:33

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

@Benjamin Steinberg 2019-12-10 21:24:23

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.

Related Questions

Sponsored Content

2 Answered Questions

1 Answered Questions

2 Answered Questions

1 Answered Questions

[SOLVED] Generators for the semigroup $\mathrm{SL}(n,\mathbb{N})$

1 Answered Questions

2 Answered Questions

2 Answered Questions

3 Answered Questions

Sponsored Content