Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.3: Symmetric Groups

( \newcommand{\kernel}{\mathrm{null}\,}\)

Recall the groups S2 and S3 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 σ:AA 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., σ(a)=a for all aA. 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:

clipboard_e93837a8e9acedf9d90c2bb574ea5ca4b.png
Figure 4.3.1

Each of these diagrams represents a permutation on five objects. I’ve given the permutations the names α, β, σ, and γ. 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, β 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 β doesn’t do anything to the objects in positions 1 and 5.

Problem 4.3.1

Describe in words what the permutations σ and γ do.

Problem 4.3.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 Sn.

Problem 4.3.3

Draw all the permutation diagrams for the permutations in S3.

Problem 4.3.4

How many distinct permutations are there in S4? How about Sn for any nN?

If Sn 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 α and β from earlier. We can represent the composition αβ via

clipboard_e66a0c8bd5eef918d625e2021b10e0992.png
Figure 4.3.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., β 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 α and β in the opposite order. We see that

clipboard_e019b0f07fcd81531bccd26fc5a2cebdd.png
Figure 4.3.3

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

Problem 4.3.5

Consider α, β, σ, and γ 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 4.3.6

Fix nN. Convince yourself that any ρSn composed with the identity permutation (in either order) equals ρ.

If Sn is going to be a group, we need to know what the inverse of a permutation is.

Problem 4.3.7

Given a permutation ρSn, describe a method for constructing ρ1. Briefly justify that ρρ1 will yield the identity permutation.

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

Theorem 4.3.1

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

Note that it is standard convention to omit the composition symbol when writing down compositions in Sn. For example, we will simply write αβ to denote αβ.

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 α,β,σ, and γ in S5 from the previous examples. Below I have indicated what each permutation is equal to using cycle notation.

clipboard_ee003b5818e393530a92482f85bb4d233.png
Figure 4.3.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, α consists of a single 5-cycle, whereas σ consists of one 2-cycle and one 3-cycle. In the case of σ, we say that σ 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 β=(1)(2,4,3)(5). In particular, we could denote the identity permutation in S5 using (1)(2)(3)(4)(5). Yet, it is common to simply use (1) to denote the identity in Sn 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 4.3.8: S3

Write down all 6 elements in S3 using cycle notation.

Problem 4.3.9: S4

Write down all 24 elements in S4 using cycle notation.

Suppose σSn. Since σ is one-to-one and onto, it is clear that it is possible to write σ as a product of disjoint cycles such that each i{1,2,,n} appears exactly once.

Let’s see if we can figure out how to multiply elements of Sn using cycle notation. Consider the permutations α=(1,3,2) and β=(3,4) in S4. To compute the composition αβ=(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 β, we know that β(1)=1 (i.e., β maps 1 to 1). Now, we see what α(1)=3. Thus, the composition αβ maps 1 to 3 (since αβ(1)=α(β(1))=α(1)=3). Next, we should return to β and see what happens to 3—which is where we ended a moment ago. We see that β maps 3 to 4 and then α maps 4 to 4 (since 4 does not appear in the cycle notation for α). So, αβ(3)=4. Continuing this way, we see that β maps 4 to 3 and α maps 3 to 2, and so αβ maps 4 to 2. Lastly, since β(2)=2 and α(2)=1, we have αβ(2)=1. Putting this altogether, we see that αβ=(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 4.3.10

Consider α, β, σ, and γ for which we drew the permutation diagrams. Using cycle notation, compute each of the following.

  1. αγ
  2. α2
  3. α3
  4. α4
  5. α5
  6. σα
  7. α1σ1
  8. β2
  9. β3
  10. βγα
  11. σ3
  12. σ6

Problem 4.3.11

Write down the group table for S3 using cycle notation.

In Problem 4.3.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 4.3.2

Suppose α and β are two disjoint cycles. Then αβ=βα. That is, products of disjoint cycles commute.

Problem 4.3.12

Compute the orders of all the elements in S3. See Problem 4.3.8.

Problem 4.3.13

Compute the orders of any twelve of the elements in S4. See Problem 4.3.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 4.3.3

If αSn such that α consists of a single k-cycle, then |α|=k.

Theorem 4.3.4

Suppose αSn such that α consists of m disjoint cycles of lengths k1,,km. Then |α|=lcm(k1,,km).*

*

Recall that lcm(k1,,km) is the least common multiple of {k1,,km}.

Problem 4.3.14

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

Problem 4.3.15

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

Problem 4.3.16

Draw the subgroup lattice for S3.

Problem 4.3.17

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

Problem 4.3.18

Consider S3.

  1. Using (1,2), (1,3), and (2,3) as generators, draw the Cayley diagram for S3.
  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 4.3.19

Recall that there are 4!=24 permutations in S4.

  1. Pick any 12 permutations from S4 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 Sn is a generating set for Sn. In fact, the adjacent transpositions form an even smaller generating set for Sn. To get some intuition, let’s play with a few examples.

Problem 4.3.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 4.3.21

Consider the arbitrary k-cycle (a1,a2,,ak) from Sn (with kn). Find a way to write this permutation as a product of 2-cycles.

Problem 4.3.22

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

The previous two problems imply the following theorem.

Theorem 4.3.5

Consider Sn.

  1. Every permutation in Sn can be written as a product of transpositions.
  2. Every permutation in Sn can be written as a product of adjacent transpositions.

Corollary 4.3.1

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

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 4.3.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 S4. To convince yourself of this fact, first prove that this group has 24 actions and then ponder the action of S4 on the four long diagonals of a cube.
  2. It turns out that you can generate S4 with (1,2) and (1,2,3,4). Moreover, you can arrange the Cayley diagram for S4 with these generators on a truncated cube, which is depicted in Figure 4.3.5. Try it.
clipboard_ec45c9f965caa16d4c951fdc80b42f250.png
Figure 4.3.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 4.3.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 Sn.

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 V4={e,v,h,vh}. Recall that V4 has the following group table.

evhvheevhvhvvevhhhhvhevvhvhhve

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

123411234221433341244321

Comparing each of the four columns to the leftmost column, we can obtain the corresponding permutations. In particular, we obtain e(1)v(1,2)(3,4)h(1,3)(2,4)vh(1,4)(2,3). 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 V4. 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 V4 again. Recall that V4 is a subset of D4, which is the symmetry group for a square. Alternatively, V4 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 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 4.3.23

Consider D4.

  1. Using the method outlined above, find a subgroup of S8 that is isomorphic to D4.
  2. Label the corners of a square 1–4. Find a subgroup of S4 that is isomorphic to D4 by considering the natural action of D4 on the labels on the corners of the square.

Problem 4.3.24

Consider Z6.

  1. Using the method outlined earlier, find a subgroup of S6 that is isomorphic to Z6.
  2. Label the corners of a regular hexagon 1–6. Find a subgroup of S6 that is isomorphic to Z6 by considering the natural action of Z6 on the labels on the corners of the hexagon.

This page titled 4.3: Symmetric Groups is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Dana Ernst via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?