16
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Oct 7, 2014 at 5:00
  • $\begingroup$ Actually, characteristic $0$ is what I meant. I'm not sure about positive characteristic. $\endgroup$ Oct 7, 2014 at 5:12
  • $\begingroup$ 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). $\endgroup$ Oct 8, 2014 at 0:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – user180040
    Oct 8, 2014 at 1:00
  • $\begingroup$ The third proof there uses the lemma that $\{\operatorname{gcd}(i,j)\}$ is an invertible matrix - something called "Smith's determinant." $\endgroup$
    – user180040
    Oct 8, 2014 at 1:20

4 Answers 4

7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ By the fixed point subspace of $A$, you mean the kernel of $A - I$? $\endgroup$
    – James
    Oct 7, 2014 at 9:05
  • $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Oct 7, 2014 at 9:16
  • $\begingroup$ 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 ... $\endgroup$
    – James
    Oct 7, 2014 at 10:20
  • $\begingroup$ If it's not too involved, could you add some details about the inductive argument? $\endgroup$
    – user180040
    Oct 7, 2014 at 18:09
  • $\begingroup$ Thank you @DerekHolt. This is quite a subtle argument. It amazes me that you were able to come up with this so quickly. $\endgroup$
    – James
    Oct 8, 2014 at 17:19
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks @user180040. This is a pretty proof, though, like Derek Holt's, it took awhile for me to digest :-) $\endgroup$
    – James
    Oct 8, 2014 at 17:20
  • $\begingroup$ @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. $\endgroup$
    – user180040
    Oct 9, 2014 at 10:05
  • $\begingroup$ 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. $\endgroup$
    – James
    Oct 9, 2014 at 10:55
5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – James
    Oct 7, 2014 at 9:02
-1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Oct 7, 2014 at 6:20
  • $\begingroup$ @DerekHolt: Can you provide an example? On another note, the decomposition w.r.t the standard basis is certainly unique. $\endgroup$ Oct 7, 2014 at 6:46
  • $\begingroup$ I see what you meant. It needs some further explanation. $\endgroup$ Oct 7, 2014 at 6:57

You must log in to answer this question.

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