4.3: Symmetric Groups

Recall the groups \(S_2\) and \(S_3\) from Problems 2.5.3 and 2.2.7. These groups act on two and three coins, respectively, that are in a row by rearranging their positions (but not flipping them over). These groups are examples of symmetric groups. In general, the symmetric group on \(n\) objects is the set of permutations that rearranges the \(n\) objects. The group operation is composition of permutations. Let’s be a little more formal.

Definition: Permutation of a set

A permutation of a set \(A\) is a function \(\sigma:A\to A\) that is both one-to-one and onto.

You should take a moment to convince yourself that the formal definition of a permutation agrees with the notion of rearranging the set of objects. The do-nothing action is the identity permutation, i.e., \(\sigma(a)=a\) for all \(a\in A\). There are many ways to represent a permutation. One visual way is using permutation diagrams, which we will introduce via examples.

Consider the following diagrams:

Figure \(\PageIndex{1}\)

Each of these diagrams represents a permutation on five objects. I’ve given the permutations the names \(\alpha\), \(\beta\), \(\sigma\), and \(\gamma\). The intention is to read the diagrams from the top down. The numbers labeling the nodes along the top are identifying position. Following an edge from the top row of nodes to the bottom row of nodes tells us what position an object moves to. It is important to remember that the numbers are referring to the position of an object, not the object itself. For example, \(\beta\) is the permutation that sends the object in the second position to the fourth position, the object in the third position to the second position, and the object in the fourth position to the third position. Moreover, the permutation \(\beta\) doesn’t do anything to the objects in positions 1 and 5.

Problem \(\PageIndex{1}\)

Describe in words what the permutations \(\sigma\) and \(\gamma\) do.

Problem \(\PageIndex{2}\)

Draw the permutation diagram for the do-nothing permutation on 5 objects. This is called the identity permutation. What does the identity permutation diagram look like in general for arbitrary \(n\)?

Definition: Set of all Permutation

The set of all permutations on \(n\) objects is denoted by \(S_n\).

Problem \(\PageIndex{3}\)

Draw all the permutation diagrams for the permutations in \(S_3\).

Problem \(\PageIndex{4}\)

How many distinct permutations are there in \(S_4\)? How about \(S_n\) for any \(n\in \mathbb{N}\)?

If \(S_n\) is going to be a group, we need to know how to compose permutations. This is easy to do using the permutation diagrams. Consider the permutations \(\alpha\) and \(\beta\) from earlier. We can represent the composition \(\alpha \circ \beta\) via

Figure \(\PageIndex{2}\)

As you can see by looking at the figure, to compose two permutations, you stack the one that goes first in the composition (e.g., \(\beta\) in the example above) on top of the other and just follow the edges from the top through the middle to the bottom. If you think about how function composition works, this is very natural. The resulting permutation is determined by where we begin and where we end in the composition.

We already know that the order of composition matters for functions, and so it should matter for the composition of permutations. To make this crystal clear, let’s compose \(\alpha\) and \(\beta\) in the opposite order. We see that

Figure \(\PageIndex{3}\)

The moral of the story is that composition of permutations does not necessarily commute.

Problem \(\PageIndex{5}\)

Consider \(\alpha\), \(\beta\), \(\sigma\), and \(\gamma\) from earlier. Can you find a pair of permutations that do commute? Can you identify any features about your diagrams that indicate why they commuted?

Problem \(\PageIndex{6}\)

Fix \(n\in\mathbb{N}\). Convince yourself that any \(\rho\in S_n\) composed with the identity permutation (in either order) equals \(\rho\).

If \(S_n\) is going to be a group, we need to know what the inverse of a permutation is.

Problem \(\PageIndex{7}\)

Given a permutation \(\rho\in S_n\), describe a method for constructing \(\rho^{-1}\). Briefly justify that \(\rho \circ \rho^{-1}\) will yield the identity permutation.

At this point, we have all the ingredients we need to prove that \(S_n\) forms a group under composition of permutations.

Theorem \(\PageIndex{1}\)

The set of permutations on \(n\) objects forms a group under the operation of composition. That is, \((S_n,\circ)\) is a group. Moreover, \(|S_n|=n!\).

Note that it is standard convention to omit the composition symbol when writing down compositions in \(S_n\). For example, we will simply write \(\alpha\beta\) to denote \(\alpha \circ \beta\).

Permutation diagrams are fun to play with, but we need a more efficient way of encoding information. One way to do this is using cycle notation. Consider \(\alpha, \beta, \sigma\), and \(\gamma\) in \(S_{5}\) from the previous examples. Below I have indicated what each permutation is equal to using cycle notation.

Figure \(\PageIndex{4}\)

Each string of numbers enclosed by parentheses is called a cycle and if the string of numbers has length \(k\), then we call it a \(k\)-cycle. For example, \(\alpha\) consists of a single 5-cycle, whereas \(\sigma\) consists of one 2-cycle and one 3-cycle. In the case of \(\sigma\), we say that \(\sigma\) is the product of two disjoint cycles.

One observation that you hopefully made is that if an object in position \(i\) remains unchanged, then we don’t bother listing that number in the cycle notation. However, if we wanted to, we could use the 1-cycle \((i)\) to denote this. For example, we could write \(\beta=(1)(2,4,3)(5)\). In particular, we could denote the identity permutation in \(S_5\) using \((1)(2)(3)(4)(5)\). Yet, it is common to simply use \((1)\) to denote the identity in \(S_n\) for all \(n\).

Notice that the first number we choose to write down for a given cycle is arbitrary. However, the numbers that follow are not negotiable. Typically, we would use the smallest possible number first, but this is not necessary. For example, the cycle \((2,4,7)\) could also be written as \((4,7,2)\) or \((7,2,4)\).

Problem \(\PageIndex{8}\): \(S_3\)

Write down all 6 elements in \(S_3\) using cycle notation.

Problem \(\PageIndex{9}\): \(S_4\)

Write down all 24 elements in \(S_4\) using cycle notation.

Suppose \(\sigma\in S_n\). Since \(\sigma\) is one-to-one and onto, it is clear that it is possible to write \(\sigma\) as a product of disjoint cycles such that each \(i\in\{1,2,\ldots, n\}\) appears exactly once.

Let’s see if we can figure out how to multiply elements of \(S_n\) using cycle notation. Consider the permutations \(\alpha=(1,3,2)\) and \(\beta=(3,4)\) in \(S_4\). To compute the composition \(\alpha\beta=(1,3,2)(3,4)\), let’s explore what happens in each position. Since we are doing function composition, we should work our way from right to left. Since 1 does not appear in the cycle notation for \(\beta\), we know that \(\beta(1)=1\) (i.e., \(\beta\) maps 1 to 1). Now, we see what \(\alpha(1)=3\). Thus, the composition \(\alpha\beta\) maps 1 to 3 (since \(\alpha\beta(1)=\alpha(\beta(1))=\alpha(1)=3\)). Next, we should return to \(\beta\) and see what happens to 3—which is where we ended a moment ago. We see that \(\beta\) maps 3 to 4 and then \(\alpha\) maps 4 to 4 (since 4 does not appear in the cycle notation for \(\alpha\)). So, \(\alpha\beta(3)=4\). Continuing this way, we see that \(\beta\) maps 4 to 3 and \(\alpha\) maps 3 to 2, and so \(\alpha\beta\) maps 4 to 2. Lastly, since \(\beta(2)=2\) and \(\alpha(2)=1\), we have \(\alpha\beta(2)=1\). Putting this altogether, we see that \(\alpha\beta=(1,3,4,2)\). Now, you should try a few. Things get a little trickier if the composition of two permutations results in a permutation consisting of more than a single cycle.

Problem \(\PageIndex{10}\)

Consider \(\alpha\), \(\beta\), \(\sigma\), and \(\gamma\) for which we drew the permutation diagrams. Using cycle notation, compute each of the following.

1. \(\alpha\gamma\)
2. \(\alpha^2\)
3. \(\alpha^3\)
4. \(\alpha^4\)
5. \(\alpha^5\)
6. \(\sigma\alpha\)
7. \(\alpha^{-1}\sigma^{-1}\)
8. \(\beta^2\)
9. \(\beta^3\)
10. \(\beta\gamma\alpha\)
11. \(\sigma^3\)
12. \(\sigma^6\)

Problem \(\PageIndex{11}\)

Write down the group table for \(S_3\) using cycle notation.

In Problem \(\PageIndex{9}\), one of the permutations you should have written down is \((1,2)(3,4)\). This is a product of two disjoint 2-cycles. It is worth pointing out that each cycle is a permutation in its own right. That is, \((1,2)\) and \((3,4)\) are each permutations. It just so happens that their composition does not “simplify" any further. Moreover, these two disjoint 2-cycles commute since \((1,2)(3,4)=(3,4)(1,2)\). In fact, this phenomenon is always true.

Theorem \(\PageIndex{2}\)

Suppose \(\alpha\) and \(\beta\) are two disjoint cycles. Then \(\alpha\beta=\beta\alpha\). That is, products of disjoint cycles commute.

Problem \(\PageIndex{12}\)

Compute the orders of all the elements in \(S_3\). See Problem \(\PageIndex{8}\).

Problem \(\PageIndex{13}\)

Compute the orders of any twelve of the elements in \(S_4\). See Problem \(\PageIndex{9}\).

Computing the order of a permutation is fairly easy using cycle notation once we figure out how to do it for a single cycle. In fact, you’ve probably already guessed at the following theorem.

Theorem \(\PageIndex{3}\)

If \(\alpha\in S_n\) such that \(\alpha\) consists of a single \(k\)-cycle, then \(|\alpha|=k\).

Theorem \(\PageIndex{4}\)

Suppose \(\alpha\in S_n\) such that \(\alpha\) consists of \(m\) disjoint cycles of lengths \(k_1,\ldots, k_m\). Then \(|\alpha|=\text{lcm}(k_1,\ldots, k_m)\).*

*

Recall that \(\text{lcm}(k_1,\ldots, k_m)\) is the least common multiple of \(\{k_1,\ldots, k_m\}\).

Problem \(\PageIndex{14}\)

Is the previous theorem true if we do not require the cycles to be disjoint? Justify your answer.

Problem \(\PageIndex{15}\)

What is the order of \((1,4,7)(2,5)(3,6,8,9)\)?

Problem \(\PageIndex{16}\)

Draw the subgroup lattice for \(S_3\).

Problem \(\PageIndex{17}\)

Now, using \((1,2)\) and \((1,2,3)\) as generators, draw the Cayley diagram for \(S_3\). Look familiar?

Problem \(\PageIndex{18}\)

Consider \(S_3\).

1. Using \((1,2)\), \((1,3)\), and \((2,3)\) as generators, draw the Cayley diagram for \(S_3\).
2. In the previous part, we used a generating set with three elements. Is there a smaller generating set? If so, what is it?

Problem \(\PageIndex{19}\)

Recall that there are \(4!=24\) permutations in \(S_4\).

1. Pick any 12 permutations from \(S_4\) and verify that you can write them as words in the 2-cycles \((1,2), (1,3), (1,4), (2,3), (2,4),(3,4)\). In most circumstances, your words will not consist of products of disjoint 2-cycles. For example, the permutation \((1,2,3)\) can be decomposed into \((1,2)(2,3)\), which is a word consisting of two 2-cycles that happen to not be disjoint.
2. Using your same 12 permutations, verify that you can write them as words only in the 2-cycles \((1,2),(2,3),(3,4)\).

By the way, it might take some trial and error to come up with a way to do this. Moreover, there is more than one way to do it.

As the previous exercises hinted at, the 2-cycles play a special role in the symmetric groups. In fact, they have a special name. A transposition is a single cycle of length 2. In the special case that the transposition is of the form \((i,i+1)\), we call it an adjacent transposition. For example, \((3,7)\) is a (non-adjacent) transposition while \((6,7)\) is an adjacent transposition.

It turns out that the set of transpositions in \(S_n\) is a generating set for \(S_n\). In fact, the adjacent transpositions form an even smaller generating set for \(S_n\). To get some intuition, let’s play with a few examples.

Problem \(\PageIndex{20}\)

Try to write each of the following permutations as a product of transpositions. You do not necessarily need to use adjacent transpositions.

1. \((3,1,5)\)
2. \((2,4,6,8)\)
3. \((3,1,5)(2,4,6,8)\)
4. \((1,6)(2,5,3)\)

The products you found in the previous exercise are called transposition representations of the given permutation.

Problem \(\PageIndex{21}\)

Consider the arbitrary \(k\)-cycle \((a_1,a_2,\ldots, a_k)\) from \(S_n\) (with \(k\leq n\)). Find a way to write this permutation as a product of 2-cycles.

Problem \(\PageIndex{22}\)

Consider the arbitrary 2-cycle \((a,b)\) from \(S_n\). Find a way to write this permutation as a product of adjacent 2-cycles.

The previous two problems imply the following theorem.

Theorem \(\PageIndex{5}\)

Consider \(S_n\).

1. Every permutation in \(S_n\) can be written as a product of transpositions.
2. Every permutation in \(S_n\) can be written as a product of adjacent transpositions.

Corollary \(\PageIndex{1}\)

The set of transpositions (respectively, the set of adjacent transpositions) from \(S_n\) forms a generating set for \(S_n\).

It is important to point out that the transposition representation of a permutation is not unique. That is, there are many words in the transpositions that will equal the same permutation. However, as we shall see in the next section, given two transposition representations for the same permutation, the number of transpositions will have the same parity (i.e., even versus odd).

Remark \(\PageIndex{1}\)

Here are two interesting facts that I will let you ponder on your own time.

1. The group of rigid motion symmetries for a cube is isomorphic to \(S_4\). To convince yourself of this fact, first prove that this group has 24 actions and then ponder the action of \(S_4\) on the four long diagonals of a cube.
2. It turns out that you can generate \(S_4\) with \((1,2)\) and \((1,2,3,4)\). Moreover, you can arrange the Cayley diagram for \(S_4\) with these generators on a truncated cube, which is depicted in Figure \(\PageIndex{5}\). Try it.

Figure \(\PageIndex{6}\): Truncated cube. [Image source: Wikipedia]

It turns out that the subgroups of symmetric groups play an important role in group theory.

Definition: Permutation Group

Every subgroup of a symmetric group is called a permutation group.

The proof of the following theorem isn’t too bad, but we’ll take it for granted. After tinkering with a few examples, you should have enough intuition to see why the theorem is true and how a possible proof might go.

Theorem \(\PageIndex{6}\): Cayley's Theorem

Every finite group is isomorphic to some permutation group. In particular, if \(G\) is a group of order \(n\), then \(G\) is isomorphic to a subgroup of \(S_n\).

Cayley’s Theorem guarantees that every finite group is isomorphic to a permutation group and it turns out that there is a rather simple algorithm for constructing the corresponding permutation group. I’ll briefly explain an example and then let you try a couple.

Consider the Klein four-group \(V_4=\{e,v,h,vh\}\). Recall that \(V_4\) has the following group table.

\(\begin{array}{c|c|c|c|c}
* & e & v & h & v h \\
\hline e & e & v & h & v h \\
\hline v & v & e & v h & h \\
\hline h & h & v h & e & v \\
\hline v h & v h & h & v & e
\end{array}\)

If we number the elements \(e,v,h,\) and \(vh\) as \(1,2,3,\) and \(4\), respectively, then we obtain the following table.

\(\begin{array}{c|c|c|c|c}
& 1 & 2 & 3 & 4 \\
\hline 1 & 1 & 2 & 3 & 4 \\
\hline 2 & 2 & 1 & 4 & 3 \\
\hline 3 & 3 & 4 & 1 & 2 \\
\hline 4 & 4 & 3 & 2 & 1
\end{array}\)

Comparing each of the four columns to the leftmost column, we can obtain the corresponding permutations. In particular, we obtain \[\begin{aligned} e&\leftrightarrow (1)\\ v&\leftrightarrow (1,2)(3,4)\\ h&\leftrightarrow (1,3)(2,4)\\ vh&\leftrightarrow(1,4)(2,3). \end{aligned}\] Do you see where these permutations came from? The claim is that the set of permutations \(\{(1),(1,2)(3,4),(1,3)(2,4),(1,4)(2,3)\}\) is isomorphic to \(V_4\). In this particular case, it’s fairly clear that this is true. However, it takes some work to prove that this process will always result in an isomorphic permutation group. In fact, verifying the algorithm is essentially the proof of Cayley’s Theorem.

Since there are potentially many ways to rearrange the rows and columns of a given table, it should be clear that there are potentially many isomorphisms that could result from the algorithm described above.

Here’s another way to obtain a permutation group that is isomorphic to a given group. Let’s consider \(V_4\) again. Recall that \(V_4\) is a subset of \(D_4\), which is the symmetry group for a square. Alternatively, \(V_4\) is the symmetry group for a non-square rectangle. Label the corners of the rectangle 1, 2, 3, and 4 by starting in the upper left corner and continuing clockwise. Recall that \(v\) is the action that reflects the rectangle over the vertical midline. The result of this action is that the corners labeled by 1 and 2 switch places and the corners labeled by 3 and 4 switch places. Thus, \(v\) corresponds to the permutation \((1,2)(3,4)\). Similarly, \(h\) swaps the corners labeled by 1 and 4 and the corners labeled by 2 and 3, and so \(h\) corresponds to the permutation \((1,4)(2,3)\). Notice that this is not the same answer we got earlier and that’s okay as there may be many permutation representations for a given group. Lastly, \(vh\) rotates the rectangle \(180^{\circ}\) which sends ends up swapping corners labeled 1 and 3 and swapping corners labeled by 2 and 4. Therefore, \(vh\) corresponds to the permutation \((1,3)(2,4)\).

Problem \(\PageIndex{23}\)

Consider \(D_4\).

1. Using the method outlined above, find a subgroup of \(S_8\) that is isomorphic to \(D_4\).
2. Label the corners of a square 1–4. Find a subgroup of \(S_4\) that is isomorphic to \(D_4\) by considering the natural action of \(D_4\) on the labels on the corners of the square.

Problem \(\PageIndex{24}\)

Consider \(\mathbb{Z}_6\).

1. Using the method outlined earlier, find a subgroup of \(S_6\) that is isomorphic to \(\mathbb{Z}_6\).
2. Label the corners of a regular hexagon 1–6. Find a subgroup of \(S_6\) that is isomorphic to \(\mathbb{Z}_6\) by considering the natural action of \(\mathbb{Z}_6\) on the labels on the corners of the hexagon.