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.

 

 

 

 

 

 

 

More on normal subgroups.

 We have a definition of a normal subgroup H contained in G, where for all x in G, xH = Hx. But why normal subgroups are important has not yet been discussed. Let me explain some things, proving some and stating others without proof.

1. if a is in H, all conjugates of a are also in H.

Proof. All conjugates of a can be written as xax⁻¹ for some x in G. Consider the set xHx⁻¹. We know xH = Hx, so we can rewrite our considered set as Hxx⁻¹, which simplifies to H. Since a is in H, every xax⁻¹ is also in H. 

 

Corollary. Every normal subgroup is a union of conjugacy classes.

 

The inverse truth of this says a non-normal subgroup H must have elements that do not have all their conjugates in H.

2. Every kernel of a homomorphism must be a normal subgroup.

Proof. Let f:G1→G2 be a homomorphism. If h is in the kernel of f, then f(h)f(x) = f(hx) = f(x), since f(h) is mapped to the identity of G2.  This does not mean hx = xh necessarily, but that Hx = xH, a subset of G1 that has as many elements as the order of H. A homomorphism splits the domain of f into a partition of equal sized sets called cosets.

 

Corollary: If G is a finite group and H is a subgroup, the order of H must divide the order of G.

For example, a set with 6 elements can only have subgroups of order 1 (the identity), 2, 3, or 6 (the whole group).

Definition: If H is a normal subgroup of G, the factor group G/H is a group created by an epimorphism f:G→G/H, where the co-domain is a group whose order is the order of G divided by the order of H.

An epimorphism is onto, so every element of G is mapped to a unique element of G/H. If G is abelian, then G/H must also be abelian, but if G is non-abelian, then G/H might be abelian or non-abelian.

 

In the next post, there will be examples of factor groups, some of which we have already seen.

 

Commentary

 

I am introducing topics in a completely different order than how I learned group theory from Ted Tracewell. It was a Monday/Wednesday/Friday class and on the first Friday, Tracewell started showing us examples of finite groups and subgroups. I went up to him after class, noticing a pattern that all the subgroups were of orders that divide the order of the group, and asking if it was a coincidence.

 

"No! It's always true! You have enough information to prove it yourself! Don't look it up!"

 

It was 1977, there was no easy access to all the world's knowledge, so I took the challenge. I finally got the proof to click on Sunday night after a lot of false starts. When I showed the proof to Tracewell on Monday, he asked what I called the equal sized subsets. I didn't have a special name for them, I just called them partitions.

 

If I had used the word "coset", he would have known I looked up the answer. My lack of knowledge of the term convinced him I had done the work myself. And that Monday long ago was when I turned into a math major.

 

Personal commentary

 In the Winter Quarter of 1977, just a few days after my 21st birthday, I started attending a class in Abstract Algebra, taught by Ted Tracewell at Cal State Hayward, now known as Cal State East Bay. Sad to say, I can find no pictures of him, but the celebrities who look most like him are the science fiction author Isaac Asimov without the muttonchops, or the songwriter/playwright/actor Adolph Green with glasses.

 

 

 

I just turned 66, and I now can identify that class as the one that changed my life. I show pictures of Asimov and Green smiling because that is how I remember Ted Tracewell. He had a real excitement about higher mathematics and it always shown through. When I taught, I tried to emulate that enthusiasm when I could, and some students commented on it. Some said they hated math, but because they saw I loved it, it made it easier to get through the class.

 

Many topics in group theory feel like solving puzzles, both the proofs and the exercises, like filling in Cayley tables and finding conjugacy classes, which I have shown on the blog. More puzzle-like topics include representing finite abelian groups, representing groups pictorially in terms of their generators the structure of normal groups and filling in character tables, the last topic part of group representation theory. The inter-connectivity of group theory makes it hard for me to figure out the order in which topics should be introduced.

I will often take side trips to talk about the lives of the mathematicians who made important discoveries, but today it's my personal history, important to me, if no one else.