The Symmetric Group S_n

My blog only scratches the surface of the topic of group theory, as you can well imagine. For example, the topic of today's post, The Symmetric Group, can fill a graduate level text, like this one by Bruce Sagan. Sagan got his doctorate at MIT, but his undergraduate career was at Cal State Hayward, my alma mater. Go Pioneers!

 

The symmetric group Sn is the group of permutations on n distinct elements. If n > 2, Sn is non-abelian.

 

An n-cycle is a permutation that rearranges n elements. (xyz), (123), (cat) are all 3-cycles on different sets of 3 symbols.

 

A 2-cycle is often called a transposition. 

 

Let me list the elements of S1, S2, S3, and S4 using cyclic notation The order of Sn is n!, which means S5 has 120 elements. I am not spending all morning listing those.

 

S1: (1) 

There is only one way to have a one element group, it's just the identity.

 

S2: (1), (12)

There is also a unique up to isomorphism two element group. It's the same structure as (Z2, +) and ({1, -1}, ✕). There's the identity element e and the non-identity element x where x*x=e.

 

S3: (1), (12), (13), (23), (123), (132)

S3 is the smallest non-abelian group, because a transposition doesn't commute with anything except the identity (1) and itself, because every transposition is its own inverse. Some examples.

(12)(123) = (13), while (123)(12) = (23)

(12)(13) = (123), while (13)(12) = (132)

 

Stated without proof: Every permutation can be represented as a combination of transpositions. 

 

Even permutations are the combination of an even number of transpositions, while odd permutations are the combination of an odd number of transpositions. The combinations that create a permutation are not unique, but these combinations must share the same parity, either even or odd.

 

A slightly annoying convention to get used to. If n is odd, the n-cycle is an even permutation, and if n is even, the n-cycle is odd.

 

Stated without proof: If n>1, Sn can be split into two equal sized partitions, the even permutations and the odd permutations.

 

Lemma: The set of all even permutations is a normal subgroup of Sn known as An, the alternating group on n elements. 

Proof: If we combine an even permutation with an even permutation, the result must also be an even permutation, so the subset is closed under the combination operator. The identity (1) is even, and every even permutation's inverse must also be even, since combining them makes the even permutation (1). This is the same as saying if even + x = even, x must itself be even.

And now S4, split into cycle structures. The even permutations will be written in red, the odd in black.

The identity: (1)

The 2-cycles: (12), (13), (14), (23), (24), (34)

The 3-cycles: (123), (124), (132), (134), (142), (143), (234), (243)

 

The 4-cycles: (1234), (1243), (1324), (1342), (1423), (1432)

 

The pairs of transpositions: (12)(34), (13)(24), (14)(23)

 

Stated without proof: In Sn, the conjugacy classes are defined as all permutations with the same cycle structure.

 

When we look at subgroups of Sn, just having the same cycle structure does not promise conjugacy in the subgroup. Remember that a conjugate of a must be of the form xax⁻¹, and x might not be in the subgroup. So in subgroups of Sn, it is still necessary that conjugates must be of the same cycle structure, but it is not sufficient. In the post introducing permutation groups, D4 was presented. The elements are

 

Rotations: (1), (1234), (13)(24), (1432)

Reflections: (12)(34), (14)(23), (13), (24)

 

Note that all the pairs of transpositions in S4 are also in
D4, but the 180° rotation commutes with everything in D4, so it stands alone in its conjugacy class, while (12)(34) and (14)(23) are still conjugates, because (13)(12)(34)(13)=(14)(23).

  

Let's consider A4. This is a non-abelian group of order 12. All the pairs of transpositions are still conjugate to one another, but the 3-cycles are split into two conjugacy classes. The inverse of a 3-cycle (abc) is (acb), and the elements needed to make such permutations conjugate to their inverses are transpositions such as (ab), (ac) and (bc), which aren't even permutations. So the conjugacy classes here are: 

The identity: (1)

3-cycle conjugacy class #1: (123), (124), (134), (234)

3-cycle conjugacy class #1: (132), (142), (143), (243)

The pairs of transpositions: (12)(34), (13)(24), (14)(23)

 

Remember that a normal subgroup must be a union of conjugacy classes and its order must divide the order of the group. In A4, the only way to meet both those criteria to get a proper normal subgroup is to add the pairs of transpositions to the the identity, {(1), (12)(34), (13)(24), (14)(23)}.

 

One last fun fact: A4 is isomorphic to the symmetries of a regular tetrahedron. The 3-cycles are the same as spinning one of the four faces, and the pairs of transpositions correspond to swapping one edge {a, b} with the edge connecting the other two vertices {c, d}.

The next post will be about permutation matrices.