The Symmetric Group

Part Of: Algebra sequence
Followup To: An Introduction to Geometric Group Theory
Content Summary: 1800 words, 18 min read

On Permutations

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 $f$ and $g$ . We will denote function composition of $g(f(x))$ as $f \bullet g$ . We will use this notation instead of the more common $g \circ f$ . Both represent the idea “apply $f$ , then $g$ “.

Consider $G = (\left\{ f(x) = 2x, g(x) = x+1, h(x) = 2x + 2, i(x) = 2x+1 \right\}, \bullet)$ .

Is this a group? Let’s check closure:

$g \bullet f = 2(x+1) = h \in G$
$f \bullet g = (2x)+1 = i \in G$
$f \bullet h = 2(2x)+2 \not\in G$

Closure is violated. $G$ isn’t even a magma! Adding $j(x) = 4x+2$ to the underlying set exacerbates the problem: then both $f \bullet j \not\in G$ and $g \bullet j \not\in G$ .

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.

Symmetry Group_ Permutation Options

Definition 2. The symmetric group $S_n$ denotes composition over a set of all bijections (permutations) over some set of $n$ objects. The symmetric group is then of order $n!$ .

The underlying set of $S_{3}$ is the set of all permutations over a 3-element set. It is of order $3! = 3 \times 2 \times 1 = 6$ .

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 $\phi$ . The top row represents the original elements $x$ , the bottom represents where each element has been relocated $\phi(x)$ .

Symmetric Group_ Two Line Notation

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. $S_3$ 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 $(A_1\ A_2\ \ldots\ A_n)$ , pronounced “ $A_1$ goes to $A_2$ goes to …”.

Symmetric Group_ Cycle Notation (1)

Cycle starting element does not matter: $(A\ C\ B) = (C\ B\ A) = (B\ A\ C)$ .

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 $a(S)$ and $b(S)$ , take each element $s \in S$ and follow its arrows until you find the set of disjoint cycles. More formally, compose these functions $x$ times until you get $(a \bullet b)^x(s) = s$ .

Here’s a simple example from $S_{3} = ( \left\{ 0, 1, 2, 3, 4, 5 \right\}, \bullet )$ .

Symmetric Group_ Cycle Algorithm S3 Ex (2)

Make sense? Good! Let’s try a more complicated example from $S_4$ .

Symmetric Group_ Cycle Algorithm S4 Ex (1)

A couple observations are in order.

1-cycles (e.g., $(A)$ ) can be omitted: their inclusion does not affect algorithm results.
Disjoint cycles commute: $(B\ D),(A\ C) = (A\ C),(B\ D)$ . Contrast this with composition, which does not commute $(B\ D) \bullet (A\ C) \neq (A\ C) \bullet (B\ D)$ .

Now, let’s return to $S_{3}$ for a moment, with its set of six permutation functions. Is this group closed? We can just check every possible composition:

Symmetric Group_ Permutation Composition

From the Cayley table on the right, we see immediately that $S_{3}$ 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 $D_{3}$ ? It is isomorphic to $S_{3}$ !

Symmetric Group_ D3 S3 Isomorphism (3)

If you go back to the original permutation pictures, this begins to make sense. Permutations $1$ and $2$ resemble rotations/cycles; $3$ , $4$ , and $5$ 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 $S_{3} = \left\{ 0, 1, 2, 3, 4, 5 \right\}, \bullet)$ has three transpositions $3 = (A\ B)$ , $4 = (B\ C)$ , and $5 = (A\ C)$ .

Transpositions are important because they are generators: every permutation can be generated by them. For example, $1 = 3 \bullet 4$ . In fact, we can lay claim to an even stronger fact:

Theorem 9. Every permutation can be generated by adjacent transpositions. Every permutation $S_{n} = \langle (1 2), (2 3), \ldots, (n-1\ n) \rangle$ .

By the isomorphism $S_3 \cong D_3$ , we can generate our “dihedral-looking” Cayley graph by selecting generators $1=(A\ B\ C)$ and $3 = (B\ C)$ .

But we can use Theorem 9 to produce another, equally valid Cayley diagram. There are two adjacent transpositions in $S_{3}$ : $3$ and $4$ . All other permutations can be written in terms of these two generators:

$0 = 3 \bullet 3$ .
$1 = 3 \bullet 4$ .
$2 = 4 \bullet 3$ .
$5 = 3 \bullet 4 \bullet 3$ .

This allows us to generate a transposition-based Cayley diagram. Here are the dihedral and transposition Cayley diagrams, side by side:

Symmetric Group_ Cayley Diagram (4)

We can confirm the validity of the transposition diagram by returning to our multiplication table: $1 \bullet 3 = 5$ means a green arrow $1 \rightarrow 5$ .

Note that the transposition diagram is not equivalent cyclic group $C_6$ , 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”:

Symmetric Group_ Abstract Cayley Diagram

We could just as easily have “moved counterclockwise”, with names like $3 \mapsto r$ , $1 \mapsto rl$ . And we can confirm by inspection that, in fact, $rl = lrlr$ etc.

Using the original clockwise notation, one presentation of $S_3$ becomes:

$S_3 = \langle l, r \mid r^2 = e, l^2 = e, (lr)^3 = e \rangle$

Towards Alternating Groups

Any given permutation can be written as a product of permutation. Consider, for example, the above equalities

$1 = rl = lrlr = (lr)^3rl$ . These have 2, 4, and 8 permutations, respectively.
$5 = lrl = lrl^3 = l^3r^3l^3$ . These have 3, 5, and 9 permutations, respectively.

Did you notice any patterns in the above lists? All expressions for $1$ require an even number of transpositions, and all expressions of $5$ 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 $S_3$ :

$0, 1, 2$ are even permutations.
$3, 4, 5$ of odd permutations.

Theorem 11. Exactly half of $S_n$ are even permutations, and they form a group called the alternating group $A_n$ . Just as $\lvert S_n \rvert = n!$ , $A_n$ has $\dfrac{n!}{2}$ 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 $A^3 = (\left\{ 0, 1, 2 \right\}, \bullet )$ in more detail. Does it remind you of anything?

It is isomorphic to the cyclic group $C_3$ ..!

Symmetric Group_ C3 A3 Isomorphism (1)

We have so far identified the following isomorphisms: $S_3 \cong D_3$ and $A_3 \cong C_3$ . Is it also true that e.g., $S_4 \cong D_4$ and $A_4 \cong C_4$ ?

No! Recall that the $\lvert D_n \rvert=2n$ and $\lvert C_n \rvert = n$ . Only $n \neq 3$ , these sets are not even potentially isomorphic. For example:

$\lvert D_4 \rvert=2 \times 4 = 8 \neq 24 = 4! = \lvert S_4 \rvert$ .
$\lvert C_4 \rvert= 4 \neq 12 = \frac{24}{2} = \lvert A_4 \rvert$ .

For these larger values of $n$ , the symmetric group is much larger than dihedral and cyclic groups.

Applications

Why do symmetric & alternating groups matter? Let me give two answers.

Perhaps you have seen the quadratic equation, the generic solution to quadratic polynomials $ax^2 + bx + c = 0$ .

$x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

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 $S_5$ .

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:

Symmetric Group_ Periodic Table

Image courtesy of Samuel Prime.

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 $S_n$ , for some sufficiently large $n$ .

For historical reasons, subgroups of the symmetric group are usually called permutation groups.

Until next time.

Wrapping Up

Takeaways:

The symmetric group $S_n$ is set of all bijections (permutations) over some set of $n$ 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 $A_n$ .
It can be shown that $S_3 \cong D_3$ and $A_3 cong C_3$ . However, for larger $n$ , 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 $S_4$ . 🙂

Related Resources

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.

Fewer Lacunae

Distilled, Integrative Research

The Symmetric Group

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply