SECTION 9 Orbits, Cycles, and the Alternating Groups Given a set A, a relation in A is defined by : For a, bA, let ab if and only if b = n(a) for some nZ. (1) We can check that the relation is indeed an equivalent relation. (Reflexive, Symmetric, Transitive) Since an equivalence relation on a set yields a natural partition of the set, then we have the following Definition Let be a permutation of a set A. The equivalence classes in A determined by the equivalence relation (1) are the orbits of . Example Example: Let A={a, b, c, d}, and be the identity permutation of A. Find the orbits of in A. Solution: The orbits of are: {a}, {b}, {c}, {d} Find the orbits of the permutation
1 2 3 4 5 6 7 8 in S8. 3 8 6 7 4 1 5 2 Solution: The orbits containing 1 is {1, 3, 6} The orbits containing 2 is {2, 8} The orbits containing 4 is {4, 7, 5} Since these three orbits include all integers from 1 to 8, the complete list
of orbits of is {1, 3 ,6}, {2, 8}, {4, 7, 5} Cycles For the remainder of this section, we suppose that A= {1, 2, 3, , n} and that we are dealing with the elements of the symmetric group Sn. 12345678 has orbits : {1, 3 ,6}, {2, 8}, {4, 7, 5}, which 3 8 6 7 4 1 5 2 Recall can be indicated graphically by using circles. Such a permutation, described graphically be a single circle, is called a cycle. Note: we also consider the identity permutation to be a cycle. Here is the term cycle in a mathematically precise way: Cycle Definition
A permutation Sn is a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit. We also introduce a cyclic notation for a cycle. For example Given 1 2 3 4 5 6 7 8 . It has orbits {1, 3, 6}, {2}, {4}, {5}, {7}, {8}. 3 2 6 4 5 1 7 8
We can denote =(1, 3, 6). Note: an integer not appearing in this notation for is left fixed by . Example Example In S5, we see that Example 1 2 3 4 5 (1,3,5, 4) 3 2 5 1 4
(3,5, 4,1) (5, 4,1,3) (4,1,3,5) 1 2 3 4 5 6 7 8 3 8 6 7 4 1 5 2 (1,3,6)(2,8)(4,7,5)
Note: these cycles are disjoint, meaning that any integer is moved by at most one of these cycles; thus no one number appears in the notations of Two cycles. Theorem Theorem Every permutation of a finite set is a product of disjoint cycles. Note: Permutation multiplication is in general not commutative, but the multiplication of disjoint cycles is commutative. Example: 1 2 3 4 5 6 Given the permutation 6 5 2 4 3 1 , write it as a product of disjoint cycles. Solution: 1 2 3 4 5 6 (1,6)(2,5,3)
6 5 2 4 3 1 Example Consider the cycles (1, 4, 5, 6) and (2, 1, 5) in S6. Find (1, 4, 5, 6)(2, 1, 5) and (2, 1, 5)(1, 4, 5, 6). 1 2 3 4 5 6 Solution: (1, 4, 5, 6)(2, 1, 5)= 6 4 3 5 2 1 1 2 3 4 5 6
(2, 1, 5)(1, 4, 5, 6)= 4 1 3 2 6 5 Even and Odd Permutations Definition A cycle of length 2 is a transposition. A computation shows that (a1,a2,, an)=(a1,an)(a1,an-1)(a1,a3)(a1,a2), therefore any cycle is a product of transpositions. Corollary Any permutation of a finite set of at least two elements is a product of transpositions.
Examples Example: (1, 6)(2, 5, 3)=(1, 6)(2, 3)(2, 5) In Sn for n2, the identity permutation is the product (1, 2)(2, 1). Note: a representation of the permutation in this way is not unique, but the number of transposition must either always be even or always be odd. Theorem: No permutation is Sn can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions. Odd/Even permutation Definition A permutation of a finite set is even if it can be expressed as a product of an even number of transpositions. A permutation of a finite set is odd if it can be expressed as a product of an odd number of transpositions.
Example: The identity permutation in Sn is an even permutation since =(1, 2)(2, 1). The permutation (1, 4, 5, 6)(2,1, 5) in S6 is odd since (1, 4, 5, 6)(2,1, 5)=(1, 6)(1, 5)(1, 4)(2, 5)(2, 1) The Alternating Groups Theorem If n2, then the collection of all even permutations of {1, 2, 3,, n} forms a subgroup of order n! / 2 of the symmetric group Sn. Definition The subgroup of Sn consisting of all even permutations of n letters is the alternating groups An on n letters.