Cycle type determines conjugacy class

From Groupprops
Jump to: navigation, search
This article describes a basic fact about permutations, or about the symmetric group or alternating group.
View a complete list of basic facts about permutations

Definition

For a finite set

For two permutations on a finite set, the following are equivalent:

  1. The two permutations have the same cycle type.
  2. The two permutations are conjugate in the symmetric group; in other words, they are in the same conjugacy class.

A cycle type on a set of size n is described by an unordered integer partition of n, where the parts are the sizes of the individual cycles. Thus, the set of conjugacy classes in the symmetric group on n letters is in bijection with the set of unordered integer partitions of n.

For an arbitrary set

Consider two finitary permutations on a set. By finitary permutation, we mean that the permutation fixes all but finitely many elements. Then the following are equivalent:

  1. The two permutations have the same cycle type
  2. The two permutations are conjugate in the finitary symmetric group; in other words, they are in the same conjugacy class in this group

Definitions used

Cycle type

Further information: Cycle type of a permutation

The cycle type of a permutation gives numerical information coded in its cycle decomposition. More precisely, it specifies how many cycles there are of each size. The cycle type is typically described as a sequence i_1,i_2, \ldots, where i_j denotes the number of cycles of size j in the cycle decomposition. Note that for a permutation on an infinite set, this also includes i_\infty, the number of cycles of infinite length.

When we're working with finitary permutations on an infinite set, then i_1 is infinite, but all the other i_js are finite, and there are only finitely many of them that are nonzero.

Conjugacy class

Further information: Conjugacy class, Conjugate elements

Related facts

Comprehensive treatment of small degrees

In the right column links in the table below, you can see tabulated information on the conjugacy classes. The cases n = 3,4,5 are embedded below.

Degree Symmetric group List of conjugacy class sizes Element structure page Section on conjugacy class structure interpreted as symmetric group
3 symmetric group:S3 1,2,3 element structure of symmetric group:S3 element structure of symmetric group:S3#Interpretation as symmetric group
4 symmetric group:S4 1,3,6,6,8 element structure of symmetric group:S4 element structure of symmetric group:S4#Interpretation as symmetric group
5 symmetric group:S5 1,10,15,20,20,24,30 element structure of symmetric group:S5 element structure of symmetric group:S5#Interpretation as symmetric group
6 symmetric group:S6 1,15,15,40,40,45,90,90,120,120,144 element structure of symmetric group:S6 element structure of symmetric group:S6#Interpretation as symmetric group
7 symmetric group:S7 1,21,70,105,105,210,210,280, 420,420,504,504,630,720,840 element structure of symmetric group:S7 element structure of symmetric group:S7#Interpretation as symmetric group
8 symmetric group:S8 1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 element structure of symmetric group:S8 element structure of symmetric group:S8#Interpretation as symmetric group


n = 3

Further information: element structure of symmetric group:S3#Interpretation as symmetric group


Partition Partition in grouped form Verbal description of cycle type Elements with the cycle type in cycle decomposition notation Elements with the cycle type in one-line notation Size of conjugacy class Formula for size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calculating element order
1 + 1 + 1 1 (3 times) three fixed points () -- the identity element 123 1 \! \frac{3!}{(1)^3(3!)} even; no 1 \operatorname{lcm} \{ 1, 1, 1 \}
2 + 1 2 (1 time), 1 (1 time) transposition in symmetric group:S3: one 2-cycle, one fixed point (1,2), (1,3), (2,3) 213, 321, 132 3 \! \frac{3!}{(2)(1)} odd 2 \operatorname{lcm} \{ 2,1 \}
3 3 (1 time) 3-cycle in symmetric group:S3: one 3-cycle (1,2,3), (1,3,2) 231, 312 2 \! \frac{3!}{3} even; yes; no 3 \operatorname{lcm} \{ 3 \}
Total (3 rows -- 3 being the number of unordered integer partitions of 3) -- -- -- -- 6 (equals 3!, the size of the symmetric group) -- odd: 3
even;no: 1
even; yes; no: 2
order 1: 1, order 2: 3, order 3: 2 --


n = 4

Further information: element structure of symmetric group:S4#Interpretation as symmetric group


Partition Partition in grouped form Verbal description of cycle type Elements with the cycle type Size of conjugacy class Formula for size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calculating element order
1 + 1 + 1 + 1 1 (4 times) four cycles of size one each, i.e., four fixed points () -- the identity element 1 \! \frac{4!}{(1)^4(4!)} even; no 1 \operatorname{lcm}\{ 1,1,1,1 \}
2 + 1 + 1 2 (1 time), 1 (2 times) one transposition (cycle of size two), two fixed points (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 6 \! \frac{4!}{[(2)^1(1!)][(1)^2(2!)]}, also \binom{4}{2} odd 2 \operatorname{lcm}\{2,1,1 \}
2 + 2 2 (2 times) double transposition: two cycles of size two (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) 3 \! \frac{4!}{(2)^2(2!)} even; no 2 \operatorname{lcm}\{2,2 \}
3 + 1 3 (1 time), 1 (1 time) one 3-cycle, one fixed point (1,2,3), (1,3,2), (2,3,4), (2,4,3), (3,4,1), (3,1,4), (4,1,2), (4,2,1) 8 \! \frac{4!}{[(3)^1(1!)][(1)^1(1!)]} or \! \frac{4!}{(3)(1)} even; yes; no 3 \operatorname{lcm}\{3,1 \}
4 4 (1 time) one 4-cycle, no fixed points (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2) 6 \! \frac{4!}{(4)^1(1!)} or \frac{4!}{4} odd 4 \operatorname{lcm} \{ 4 \}
Total (5 rows, 5 being the number of unordered integer partitions of 4) -- -- -- 24 (equals 4!, the order of the whole group) -- odd: 12 (2 classes)
even; no: 4 (2 classes)
even; yes; no: 8 (1 class)
order 1: 1 (1 class)
order 2: 9 (2 classes)
order 3: 8 (1 class)
order 4: 6 (1 class)
--


n = 5

Further information: element structure of symmetric group:S5#Interpretation as symmetric group


Partition Partition in grouped form Verbal description of cycle type Representative element with the cycle type Size of conjugacy class Formula calculating size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calcuating element order
1 + 1 + 1 + 1 + 1 1 (5 times) five fixed points () -- the identity element 1 \! \frac{5!}{(1)^5(5!)} even; no 1 \operatorname{lcm}\{1 \}
2 + 1 + 1 + 1 2 (1 time), 1 (3 times) transposition: one 2-cycle, three fixed point (1,2) 10 \! \frac{5!}{[(2)^1(1!)][(1)^3(3!)]} or \! \frac{5!}{(2)(1)^3(3!)}, also \binom{5}{2} in this case odd 2 \operatorname{lcm}\{2,1 \}
3 + 1 + 1 3 (1 time), 1 (2 times) one 3-cycle, two fixed points (1,2,3) 20 \! \frac{5!}{[(3)^1(1!)][(1)^2(2!)]} or \! \frac{5!}{(3)(1)^2(2!)} even; no 3 \operatorname{lcm}\{3,1\}
2 + 2 + 1 2 (2 times), 1 (1 time) double transposition: two 2-cycles, one fixed point (1,2)(3,4) 15 \frac{5!}{[2^2(2!)][1^1(1!)]} or \! \frac{5!}{2^2(2!)(1)} even; no 2 \operatorname{lcm}\{2,1 \}
4 + 1 4 (1 time), 1 (1 time) one 4-cycle, one fixed point (1,2,3,4) 30 \! \frac{5!}{[4^1(1!)][1^1(1!)]} or\! \frac{5!}{(4)(1)} odd 4 \operatorname{lcm}\{4,1\}
3 + 2 3 (1 time), 2 (1 time) one 3-cycle, one 2-cycle (1,2,3)(4,5) 20 \! \frac{5!}{[3^1(1!)][2^1(1!)]} or \! \frac{5!}{(3)(2)} odd 6 \operatorname{lcm}\{3,2 \}
5 5 (1 time) one 5-cycle (1,2,3,4,5) 24 \frac{5!}{5^1(1!)} or \! \frac{5!}{5} even; yes; yes 5 \operatorname{lcm} \{ 5 \}
Total (7 rows, 7 being the number of unordered integer partitions of 5) -- -- -- 120 (equals order of the group) -- odd: 60 (3 classes)
even;no: 36 (3 classes)
even;yes;yes: 24 (1 class)
[SHOW MORE]


Proof

The key idea here is that conjugation by an element of the symmetric group is tantamount to a relabeling of the elements that are being permuted. Thus, if a permutation \alpha sends x to y, then conjugating \alpha by \sigma gives a permutation that sends \sigma(x) to \sigma(y). That's because:

(\sigma \alpha \sigma^{-1})(\sigma(x)) = \sigma(\alpha(x)) = \sigma(y)

Conjugate implies same cycle type

Conjugation by \sigma sends each constituent cycle of the permutation to an equivalent cycle, where all the elements of the cycle are replaced by their images under \sigma. In other words:

\sigma(a_1,  a_2,  \ldots,  a_n) \sigma^{-1} = (\sigma(a_1),  \sigma(a_2), \ldots, \sigma(a_n))

Thus, the lengths of the cycles in the cycle decomposition remain unaffected, so the number of cycles of each length remains unaffected.

Same cycle type implies conjugate

The outline for the case of a finite set:

  1. Construct a bijection between cycles in the first permutation and cycles in the second, such that the bijection matches cycles of the same size. Note that such a bijection is not necessarily unique.
  2. For a pair of cycles (a_1, a_2, \ldots, a_n) and (b_1,b_2,\ldots,b_n), define \sigma(a_i) = b_i. Note that since we can write a cycle to begin with any element, the choice of \sigma is not necessarily unique.

Then, a \sigma chosen in this way conjugates the first permutation to the second permutation.

For the case of an infinite set, we can restrict our attention to the union of the finite subsets of elements moved by the two permutations, and construct \sigma as above, on those two subsets. Such a \sigma is clearly finitary, and conjugates the first permutation to the second.