Section 2.5 The Symmetric Group
For a set denote by the set of bijective maps We make into a group with composition of functions as the binary operation: so
The identity element is the identity map defined by for all Every element has an inverse since each is one-to-one and onto. The operation is associative since composition of maps is.
When is finite, say we assume and write for It is easy to check that The group is called the symmetric group on letters. Any subgroup of is called a permutation group.
Note that and (where interchanges 1 and 2) are cyclic groups. For it is easy to check that is nonabelian.
Consider described somewhat cumbersomely by
where takes an element in the top row to the element directly below it. It is more convenient to write as a product of disjoint cycles.
Recall the the following properties:
Proposition 2.5.2.
- Every permutation can be written uniquely as the product of disjoint cycles.
- The cycle can be represented as
- Disjoint cycles commute.
The process by which we write a permutation as a product of disjoint cycles can be presented as algorithmic, but it also has a natural interpretation in terms of group actions.
Suppose we are given a permutation in and want to find its representation as a product of disjoint cycles. Let be the cyclic group generated by Then acts on by Given a group action, we know that the set is partitioned into orbits. Each orbit corresponds to one of the disjoint cycles in the decomposition:
The only difference between the orbit and the cycle, is that the elements in the cycle are ordered to convey a bit more information:
where is the smallest positive integer such that So now the proposition above is clearer: the cycles are uniquely determined because the orbits under the action of are, an orbit can be named by any element it contains since the group acts transitively on each orbit, and being the disjoint union of orbits does not depend on the order in which you write the orbits in the union.
Exercise 2.5.1.
(a)
Solution.
(b)
Write a permutation as a product of disjoint cycles: Show that the order of is the least common multiple of the lengths of the cycles
Solution.
Let be the length (order) of the cycle and let Then, since disjoint cycles commute,
since each is a multiple of It follows from Lagrange that the order of divides Suppose that then since disjoint cycles commute,
hence
Recall that the are disjoint cycles so as permutations only move sets which are disjoint from one another. That is, cannot move any integer in the sets moved by yet their th powers are equal. The only resolution is that This implies Since the cycles commute, we may do the same trick for all the to conclude for all and hence Thus
Exercise 2.5.2.
Write a permutation as the product of disjoint cycles —including the 1-cycles:
and let denote the length of Because disjoint cycles commute, we may assume that the cycles are arranged in so their lengths appear in descending order and since we include the 1-cycles their lengths form a partition of the integer
(a)
Solution.
Let’s first see where we send an integer of the form for some We see that \[\sigma\tau\sigma^{-1}(\sigma(a_i)) = \sigma\tau(a_i) = \sigma(a_{i+1}),\] where we read the subscripts modulo so we might conjecture that however to be sure, we must show that fixes all other integers. So now let be an integer, with for any Then for any so leaves it unchanged, so that takes it back to So no integer other than the is moved by and our decomposition is complete.
(b)
Solution.
Let and Then for any permutation which takes we have the desired equality.
Use the exercises above to deduce the following proposition.
Proposition 2.5.3.
There is a one-to-one correspondence between conjugacy classes of elements in are partitions of the integer
Proof.
Let and consider its conjugacy class. Write as the product of disjoint cycles (including the 1-cycles):
We have observed that (arranged in descending order since disjoint cycles commute), is a partition of Since conjugation is an (inner) automorphism,
and by the exercises above is again a cycle of length so the resulting cycles in again produce the same partition of
Given a partition of there is certainly a permutation with that cycle type, just by listing the integers from 1 to and grouping them into cycles of the desired length.
So we have a surjective map from permutations to partitions which is well-defined on conjugacy classes. We have another exercise which shows that two cycles of a given length are always conjugate and this extends to a product of disjoint cycles.
Permutations are divided into even and odd permutations according to one of the following two equivalent schemes. The virtue of the first definition is that it is clearly well-defined.
Define a function as follows: for a permutation write as the product of disjoint cycles (including the 1-cycles), say Then we define
For the second definition, note that any cycle can be written as the product of transpositions:
hence so can any permutation (though not in a unique way). If
where all the are transpositions, then it is also true that
Proposition 2.5.4.
The definitions are the sign function given above are equivalent. Moreover, is a group homomorphism, and is surjective for It’s kernel is called the alternating group, denoted
Remark 2.5.5.
For it follows from the first isomorphism theorem that is a normal subgroup of index 2 in For it is generated by the 3-cycles, and for it is simple group.