# If permutation matrices are conjugate in $\operatorname{GL}(n,\mathbb{F})$ are the corresponding permutations conjugate in the symmetric group?

There is a standard embedding of the symmetric group $S_n$ into $\operatorname{GL}(n,\mathbb{F})$ (for any field $\mathbb{F}$) that sends each permutation in $S_n$ to the corresponding permutation matrix. As this is a group homomorphism, certainly, conjugate permutations map to conjugate matrices. What about the converse? Suppose that $A$ and $B$ are similar permutation matrices in $\operatorname{GL}(n,\mathbb{F})$ coming from permutations $\alpha$ and $\beta$ in $S_n$. Does it follow that $\alpha$ and $\beta$ are already conjugate in $S_n$? (I thought that I had a proof, but I noticed that the argument seems to fail in positive characteristic.)

• I believe this is true in positive characteristic. You should be able to recover the cycle type of a permutation from the characteristic polynomial of the matrix. – Jair Taylor Oct 7 '14 at 5:00
• Actually, characteristic $0$ is what I meant. I'm not sure about positive characteristic. – Jair Taylor Oct 7 '14 at 5:12
• Proven in: L. G. Kovács, The permutation lemma of Richard Brauer, Bull. London Math. Soc, 14 (1982), 127-128. Sadly not in the open domain (you can mail me for a copy). – darij grinberg Oct 8 '14 at 0:03
• After seeing Darij's comment, I found this: agreg-maths.univ-rennes1.fr/documentation/docs/Agreg.Brauer.pdf It has three proofs of this lemma. The first is in characteristic zero and uses the characteristic polynomial. The second seems the same as my second proof, valid in characteristic zero only. The third follows Derek Holt's method, but avoids the induction part at the end. – user180040 Oct 8 '14 at 1:00
• The third proof there uses the lemma that $\{\operatorname{gcd}(i,j)\}$ is an invertible matrix - something called "Smith's determinant." – user180040 Oct 8 '14 at 1:20

I think the following argument works independently of the field. The dimension of the fixed point subspaces of $A$ and $B$ are equal to the total number of cycles (including cycles of length $1$) of $\alpha$ and $\beta$ so, if $A$ and $B$ are similar matrices, then $\alpha$ and $\beta$ must have the same total numbers of cycles.

The same applies to $\alpha^p$ and $\beta^p$ for any prime $p$, and the number of their cycles are equal to $a_1+a_2p$ and $b_1 + b_2p$, where $a_1$ and $a_2$ are the numbers of cycles of $\alpha$ of length not divisible by $p$ and divisible by $p$ respectively, and similarly for $b_1,b_2$ with $\beta$. So $a_1+a_2p=b_1+b_2p$, and since we already know that $a_1+a_2=b_1+b_2$, we get $a_1=b_1$, $a_2=b_2$. In other words, for any prime $p$, $\alpha$ and $\beta$ have the same numbers of cycles of lengths divisible by $p$.

Now, by an inductive argument on the number of prime factors of $k$, we can show that for any integer $k>0$, $\alpha$ and $\beta$ have the same numbers of cycles of lengths divisible by $k$, and that implies that $\alpha$ and $\beta$ have the same cycle types, so are conjugate in $S_n$.

For example for $k=12$ let $a_i$ be the number of cycles of $\alpha$ of length $j$, where $\gcd(j,12)=i$, for $i=1,2,3,4,6,12$. By induction, we know $a_1+a_2+a_3+a_4+a_6+a_{12}$, $a_2+a_4+a_6+a_{12}$, $a_3+a_6+a_{12}$, $a_4+a_{12}$ and $a_6+a_{12}$. The total number of cycles of $\alpha^{12}$ is $a_1+2a_2+3a_3+4a_4+6a_6+12a_{12}$ so that number, together with the already known sums, is enough to determine $a_{12}$ and hence to prove that $a_{12}=b_{12}$.

• By the fixed point subspace of $A$, you mean the kernel of $A - I$? – James Oct 7 '14 at 9:05
• That's right - dimension of eigenspace for eigenvalue $1$. You seem to be getting lots of different proofs, but they all seem to depend somehow on some kind of M\"obius Inversion argument to do an induction. – Derek Holt Oct 7 '14 at 9:16
• Okay, thank you. It took me a while just to realise that $1$ was actually an eigenvalue. Obvious, once you see it! :-) And yes, I noticed, after @BrunoJoyal mentioned it, that my own argument (though it breaks in positive characteristic) could have been made nicer by using Mobius inversion as well. I'll continue studying your proof ... – James Oct 7 '14 at 10:20
• If it's not too involved, could you add some details about the inductive argument? – user180040 Oct 7 '14 at 18:09
• Thank you @DerekHolt. This is quite a subtle argument. It amazes me that you were able to come up with this so quickly. – James Oct 8 '14 at 17:19

Note: I've edited this proof to replace the induction step with an appeal to the Möbius inversion formula.

Note: I've added a shorter proof in the case of characteristic zero.

This is true in any characteristic. $A$ and $B$ are similar if and only if they define isomorphic $F[X]$-module structures on $F^n$ via $Xv = Av$ and $Xv = Bv$, respectively.

If the cycles of $\alpha$ have lengths $n_1, \dots, n_s$, then the canonical $F[X]$-module structure is isomorphic to $M = \oplus_i F[X]/(X^{n_i} - 1)$.

I will assume first that the characteristic is $p > 0$. Write $n_i = r_i p^{k_i}$ with $r_i$ prime to $p$. Then $M = \oplus_i F[X]/(X^{r_i} - 1)^{p^{k_i}}$. We want to check that the numbers $r_i$ and $k_i$ are well-determined by $M$ up to permutation. Let $h_k(r)$ denote the number of times the factor $(X^r - 1)^{p^k}$ appears in the sum for $M$.

For any number $r$ prime to $p$, write $\phi_r$ for the $r$th cyclotomic polynomial. The polynomials $\phi_r$ are pairwise relatively prime, and $X^r - 1 = \prod_{d|r} \phi_d$. We have $M = \oplus_r M_r$ where $M_r$ is the submodule of $M$ annihilated by some power of $\phi_r$, and $M_r = \bigoplus_{i \text{ such that } r|r_i} F[X]/(\phi_r^{p^{k_i}})$. For a fixed $r$, the powers appearing in this decomposition are well determined by $M_r$ (and hence $M$), by the uniqueness part of the structure theorem for finitely generated modules over a PID.

If we let $f_k(r)$ be the number of times that $\phi_r^{p^k}$ appears in the decomposition of $M_r$, then $f_k(r)$ is well determined by $M$ and we have $f_k(r) = \sum_{q \text{ such that } r|q} h_k(q)$. To finish the proof, it will be enough to show that the function $f_k = f$ uniquely determines the function $h_k= h$.

If we let $N$ be a common multiple of all numbers $q$ for which $h(q) \ne 0$ (or equivalently, for which $f(q) \ne 0$), and we write $f'(t) = f(N/t)$ and $h'(t) = h(N/t)$, then we have $f'(u) = \sum_{t, \, t|u} h'(t)$. It follows from the Möbius inversion formula that $h'$ is determined by $f'$, hence $h$ by $f$.

If the characteristic is zero, argue the same way, but replacing all powers $p^{k_i}$ with $1$.

Note that the argument using the characteristic polynomial fails in positive characteristic $p$, since for example $X^2 - 1 = (X-1)^2$ when $p = 2$.

ALTERNATIVE PROOF IN CHARACTERISTIC ZERO:

Let $h(c)$ denote the number of cycles of length $c$ in a decomposition of $\alpha$. Note that $\operatorname{tr} A$ is the number of fixed points of the permutation $\alpha$. Thus if we let $f(n) = \operatorname{tr} A^n$, then $f(n)$ is also the number of fixed points of the permutation $\alpha^n$, namely $$f(n) = \sum_{c|n} ch(c).$$ It follows from the Möbius inversion formula that the function $h(c)$ is entirely determined by $f(n)$, hence by $A$.

• Thanks @user180040. This is a pretty proof, though, like Derek Holt's, it took awhile for me to digest :-) – James Oct 8 '14 at 17:20
• @James The first one isn't really that nice. It's a direct translation of the problem into the language of $F[X]$-modules, and then uses the Chinese remainder theorem and the structure theorem to reduce the problem. The module problem was equivalent. Derek Holt's is nicer in that it identifies an easily described invariant that relates the permutation and the endomorphism, and is enough to do the job. Seeing his solution is how I got the idea for the second proof, which I do like better than the first, but which unfortunately doesn't work in positive characteristic. – user180040 Oct 9 '14 at 10:05
• Your second proof is essentially the one I had in mind originally, but I used an explicit induction rather than Mobius inversion. (And it took me a couple of pages of scribbling to convince myself it worked. :-) Eventually noticing that it broke in prime characteristic is, as I said, what prompted the question in the first place. Thanks again for your nice answer. – James Oct 9 '14 at 10:55

This is true in characteristic $0$. If $A$ is a permutation matrix corresponding to the permutation $\sigma \in S_n$, then the characteristic polynomial of $A$ is $f(T) = \prod_{k=1}^\infty(1-T^k)^{a_k}$, where $a_k$ is the number of cycles of length $k$ in $\sigma$. (Remark that this is actually a finite product.) I claim that you can recover the cycle type of $\sigma$ from $f(T)$, i.e. that you can recover the sequence $\{a_k\}$. Remark that

$$\log f(T) = -\sum_{k=1}^\infty \sum_{m=1}^\infty\frac{T^{km}}{m}a_k = - \sum_{l=1}^\infty\frac{T^{l}}{l}b_l$$

where $b_l = \sum_{d \mid l} d a_d$. By induction (or by Möbius inversion), we can recover the sequence $\{a_k\}$ from the sequence $\{b_l\}$, and hence from $f(T)$. Therefore the cycle type of $\sigma$ is completely determined by its characteristic polynomial, and two elements of $S_n$ are conjugate iff they have the same cycle type.

• I think my own argument is probably okay in characteristic zero. But this is interesting, as it shows quite a different and more elegant approach. Thanks for that. – James Oct 7 '14 at 9:02

Yes, they both permute the standard basis and have the same cycle structure.

It's easier to see if you view them as linear transformations: Each cycle corresponds to a stable subspace of the total space and the cycle decomposition corresponds to the stable decomposition.

• I don't see how this shows that the permutations have the same cycle structure. The stable subspaces defined by the cycles are not necessarily indecomposable. – Derek Holt Oct 7 '14 at 6:20
• @DerekHolt: Can you provide an example? On another note, the decomposition w.r.t the standard basis is certainly unique. – Quang Hoang Oct 7 '14 at 6:46
• I see what you meant. It needs some further explanation. – Quang Hoang Oct 7 '14 at 6:57