In the last few posts, we have discussed algebraic structures whose sets contain objects (e.g., numbers). Now, let’s consider structures over a set of functions, whose binary operation is function composition.
Definition 1. Consider two functions and . We will denote function composition of as . We will use this notation instead of the more common . Both represent the idea “apply , then “.
Is this a group? Let’s check closure:
Closure is violated. isn’t even a magma! Adding to the underlying set exacerbates the problem: then both and .
So it is hard to establish closure under function composition. Can it be done?
Yes. Composition exhibits closure on sets of permutation functions. Recall that a permutation is simply a bijection: it re-arrange a collection of things. For example, here are the six possible bijections over a set of three elements.
Definition 2. The symmetric group denotes composition over a set of all bijections (permutations) over some set of objects. The symmetric group is then of order .
The underlying set of is the set of all permutations over a 3-element set. It is of order .
This graphical representation of permutations is rather unwieldy. Let’s switch to a different notation system!
Notation 3: Two Line Notation. We can use two lines to denote each permutation mapping . The top row represents the original elements , the bottom represents where each element has been relocated .
Two line notation is sometimes represented as an array, with the top row as matrix row, and bottom denoting matrix column. Then the identity matrix represents the identity permutation.
Definition 4. A cycle is a sequence of morphisms that forms a closed loop. An n-cycle is a cycle of length n. A 1-cycle does nothing. A 2-cycle is given the special name transposition. has two permutations with 3-cycles: can you find them?
Theorem 5. Cycle Decomposition Theorem. Every permutation can be decomposed into disjoint cycles. Put differently, a node cannot participate in more than one cycle. If it did, its parent cycles would merge.
Notation 6: Cycle Notation. Since permutations always decompose into cycles, we can represent them as , pronounced “ goes to goes to …”.
Cycle starting element does not matter: .
The Cycle Algorithm
It is difficult to tell visually the outcome of permutation composition. Let’s design an algorithm to do it for us!
Algorithm 7: Cycle Algorithm. To compose two permutation functions and , take each element and follow its arrows until you find the set of disjoint cycles. More formally, compose these functions times until you get .
Here’s a simple example from .
Make sense? Good! Let’s try a more complicated example from .
A couple observations are in order.
- 1-cycles (e.g., ) can be omitted: their inclusion does not affect algorithm results.
- Disjoint cycles commute: . Contrast this with composition, which does not commute .
Now, let’s return to for a moment, with its set of six permutation functions. Is this group closed? We can just check every possible composition:
From the Cayley table on the right, we see immediately that is closed (no new colors) and non-Abelian (not diagonal-symmetric).
But there is something much more interesting in this table. You have seen it before. Remember the dihedral group ? It is isomorphic to !
If you go back to the original permutation pictures, this begins to make sense. Permutations and resemble rotations/cycles; , , and perform reflections/flips.
Generators & Presentations
In Theorem 7, we learned that permutations decompose into cycles. Let’s dig deeper into this idea.
Theorem 8. Every n-cycle can be decomposed into some combination of 2-cycles. In other words, cycles are built from transpositions.
The group has three transpositions , , and .
Transpositions are important because they are generators: every permutation can be generated by them. For example, . In fact, we can lay claim to an even stronger fact:
Theorem 9. Every permutation can be generated by adjacent transpositions. Every permutation .
By the isomorphism , we can generate our “dihedral-looking” Cayley graph by selecting generators and .
But we can use Theorem 9 to produce another, equally valid Cayley diagram. There are two adjacent transpositions in : and . All other permutations can be written in terms of these two generators:
This allows us to generate a transposition-based Cayley diagram. Here are the dihedral and transposition Cayley diagrams, side by side:
We can confirm the validity of the transposition diagram by returning to our multiplication table: means a green arrow .
Note that the transposition diagram is not equivalent cyclic group , because arrows in the latter are monochrome and unidirectional.
We’re not quite done! We can also rename our set elements to employ generator-dependent names, by “moving clockwise”:
We could just as easily have “moved counterclockwise”, with names like , . And we can confirm by inspection that, in fact, etc.
Using the original clockwise notation, one presentation of becomes:
Towards Alternating Groups
Any given permutation can be written as a product of permutation. Consider, for example, the above equalities
- . These have 2, 4, and 8 permutations, respectively.
- . These have 3, 5, and 9 permutations, respectively.
Did you notice any patterns in the above lists? All expressions for require an even number of transpositions, and all expressions of require an odd number. In other words, the parity (evenness or oddness) of a given permutation doesn’t seem to be changing. In fact, this observation generalizes:
Theorem 10. For any given permutation, the parity of its transpositions is unique.
Thus, we can classify permutations by their parity. Let’s do this for :
- are even permutations.
- of odd permutations.
Theorem 11. Exactly half of are even permutations, and they form a group called the alternating group . Just as , has elements.
Why don’t odd permutations form a group? For one thing, it doesn’t contain the identity permutation, which is always even.
Let’s examine in more detail. Does it remind you of anything?
It is isomorphic to the cyclic group ..!
We have so far identified the following isomorphisms: and . Is it also true that e.g., and ?
No! Recall that the and . Only , these sets are not even potentially isomorphic. For example:
For these larger values of , the symmetric group is much larger than dihedral and cyclic groups.
Why do symmetric & alternating groups matter? Let me give two answers.
Perhaps you have seen the quadratic equation, the generic solution to quadratic polynomials .
Analogous formulae exist for cubic (degree-3) and quartic (degree-4) polynomials. 18th century mathematics was consumed by the theory of equations: mathematicians attempting to solve quintic polynomials (degree-5). Ultimately, this quest proved to be misguided: there is no general solution to quintic polynomials.
Why should degree-5 polynomials admit no solution? As we will see when we get to Galois Theory, it has to do with the properties of symmetric group .
A second reason to pay attention to symmetric groups comes from the classification theorem of finite groups. Mathematicians have spent decades exploring the entire universe of finite groups, finding arcane creatures such as the monster group, which may or may not explain features of quantum gravity.
One way to think about group space is by the following periodic table:
Crucially, in this diverse landscape, the symmetric group plays a unique role:
Theorem 12: Cayley’s Theorem. Every finite group is a subgroup of the subgroup , for some sufficiently large .
For historical reasons, subgroups of the symmetric group are usually called permutation groups.
Until next time.
- The symmetric group is set of all bijections (permutations) over some set of objects, closed under function composition.
- Permutations can be decomposed into disjoint cycles: cycle notation uses this fact to provide an algorithm to solve for arbitrary compositions.
- All permutations (and hence, the symmetric group) can be generated by adjacent transpositions. This allows us to construct a presentation of the symmetric group.
- Permutations have unique parity: thus we can classify permutations as even or odd. The group of even presentations is called the alternating group .
- It can be shown that and . However, for larger , the symmetric and alternating group are much larger than cyclic and dihedral groups.
The best way to learn math is through practice! If you want to internalize this material, I encourage you to work out for yourself the Cayley table & Cayley diagram for . 🙂
- This post is based on Professor Macaulay’s Visual Group Theory lectures, which in turn is based on Nathan Carter’s eponymous textbook.
- Related to this style of teaching group theory are Dana Ernst’s lecture notes.
- If you want to see explore finite groups with software, Group Explorer is excellent.
For a more traditional approach to the subject, these Harvard lectures are a good resource.