Skip to main content
Logo image

Section 2.5 The Symmetric Group

For a set X, denote by SX the set of bijective maps f:XX. We make SX into a group with composition of functions as the binary operation: (f,g)fg, so fg(x)=f(g(x)).
The identity element is the identity map idX:XX defined by idX(x)=x for all xX. Every element fSX has an inverse since each f is one-to-one and onto. The operation is associative since composition of maps is.
When X is finite, say |X|=n, we assume X={1,2,,n} and write Sn for SX. It is easy to check that |Sn|=n!. The group Sn is called the symmetric group on n letters. Any subgroup of Sn is called a permutation group.
Note that S1={id} and S2={id,σ} (where σ interchanges 1 and 2) are cyclic groups. For n3, it is easy to check that Sn is nonabelian.
Consider σS11 described somewhat cumbersomely by
σ=(12345678910115132764981110)
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 that a cycle of length k (or a k-cycle) is a permutation, τSX, for which there exist a1,,akX satisfying
τ(ai)=ai+1 for 1ik, τ(ak)=a1, and τ(x)=x for all other xX.
The cycle τ is written as τ=(a1 a2  ak).

Example 2.5.1.

For example, we can write
σ=(12345678910115132764981110)
as as a product of disjoint cycles:
σ=(1 5 7 4 2)5cycle(3)(6)1cycles(8 9)(10 11)2cycles.
Recall the the following properties:
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 Sn and want to find its representation as a product of disjoint cycles. Let G=σ be the cyclic group generated by σ. Then G acts on X={1,,n} by (τ,k)τ(k). Given a group action, we know that the set X is partitioned into orbits. Each orbit corresponds to one of the disjoint cycles in the decomposition:
Gk=Orbit of (k)={τ(k)τσ}.
The only difference between the orbit and the cycle, is that the elements in the cycle are ordered to convey a bit more information:
(k σ(k) σ2(k)  σ1(k))
where is the smallest positive integer such that σ(k)=k. 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 X 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)

Show that the order (as a group element in Sn) of an r-cycle σ=(a1 a2  ar) is r.
Solution.
σ takes ai to ai+1 for 1ir and ar to a1, it is straightforward to check by induction that σj takes ai to ai+j with i+j read with least positive residues modulo r. It follows that the order of σ is r.

(b)

Write a permutation σSn as a product of disjoint cycles: σ=σ1σs. Show that the order of σ is the least common multiple of the lengths of the cycles σi.
Solution.
Let mj be the length (order) of the cycle σj, and let M=lcm{m1,,ms}. Then, since disjoint cycles commute,
σM=(σ1σs)M=σ1MσsM=1
since each mj is a multiple of M. It follows from Lagrange that the order of σ divides M. Suppose that N=|σ|, then since disjoint cycles commute,
σN=(σ1σs)N=σ1NσsN=1,
hence
σ1N=σ2nσtN.
Recall that the σj are disjoint cycles so as permutations only move sets which are disjoint from one another. That is, σ1 cannot move any integer in the sets moved by σ2,,σs, yet their Nth powers are equal. The only resolution is that σ1N=1=σ1N. This implies m1N. Since the cycles commute, we may do the same trick for all the σj to conclude mjN for all j, and hence MN. Thus |σ|=M.

Exercise 2.5.2.

Write a permutation σSn as the product of disjoint cycles —including the 1-cycles:
σ=σ1σr,
and let ai denote the length of σi. 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 n.
If σ=σ1σr has lengths a1ar1, then we call the r-tuple (a1,,ar) the cycle type of σ.

(a)

Let τ=(a1 a2  ak) be any k-cycle. Show that for any permutation σ,
στσ1=(σ(a1) σ(a2)  σ(ak)),
so in particular, conjugation takes a k-cycle to another k-cycle.
Solution.
Let’s first see where we send an integer of the form =σ(ai) for some i. We see that \[\sigma\tau\sigma^{-1}(\sigma(a_i)) = \sigma\tau(a_i) = \sigma(a_{i+1}),\] where we read the subscripts modulo k, so we might conjecture that στσ1=(σ(a1)σ(a2)σ(ak)), however to be sure, we must show that στσ1 fixes all other integers. So now let be an integer, with σ(ai) for any i. Then σ1()ai for any i, so τ leaves it unchanged, so that σ takes it back to . So no integer other than the σ(ai) is moved by στσ1, and our decomposition is complete.

(b)

Let τ,τSn be any two cycles of length k. Show that there is an element σSn so that
τ=στσ1.
This means that for each k-cycles in Sn form their own and complete conjugacy class.
Solution.
Let τ=(a1a2ak) and μ=(b1b2bk). Then for any permutation σ which takes aibi we have the desired equality.
Use the exercises above to deduce the following proposition.

Proof.

Let σSn and consider its conjugacy class. Write σ as the product of disjoint cycles (including the 1-cycles):
σ=σ1σr with mi=|σi|.
We have observed that (arranged in descending order since disjoint cycles commute), m1,,mr is a partition of n. Since conjugation is an (inner) automorphism,
τστ1=τστ1τσrτ1,
and by the exercises above τσjτ1 is again a cycle of length mj, so the resulting cycles in τστ1 again produce the same partition of n.
Given a partition of n, there is certainly a permutation with that cycle type, just by listing the integers from 1 to n, 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 sgn:Sn{±1} as follows: for a permutation σSn, write σ as the product of disjoint cycles (including the 1-cycles), say σ=σ1σt. Then we define
sgn(σ)=(1)nt.
It follows that sgn(1)=1=(1)nn, and sgn((a b))=(1)n(n1)=1. For a permutation σ, the value sgn(σ) is called the sign of the permutation.
For the second definition, note that any cycle can be written as the product of transpositions:
(a1 a2  ar)=(a1 ar)(a1 a3)(a1 a2),
hence so can any permutation (though not in a unique way). If
σ=τ1τr,
where all the τi are transpositions, then it is also true that
sgn(σ)=(1)r.

Remark 2.5.5.

For n2, it follows from the first isomorphism theorem that An is a normal subgroup of index 2 in Sn. For n3, it is generated by the 3-cycles, and for n5, it is simple group.