# 6.1: Permutation Groups

- Page ID
- 6120

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

We begin by studying the kinds of permutations that arise in situations where we have used the **quotient principle** in the past.

## 6.1.1 The rotations of a square

In Figure 6.1 we show a square with its four vertices labeled a, b, c, and d. We have also labeled the spots in the plane where each of these vertices falls with the label 1, 2, 3, or 4. Then we have shown the effect of rotating the square clockwise through 90, 180, 270, and 360 degrees (which is the same as rotating through 0 degrees).

*Figure 6.1: The four possible results of rotating a square but maintaining its location.*

Underneath each of the rotated squares we have named the function that carries out the rotation. We use ρ, the Greek letter pronounced “row,” to stand for a 90 degree clockwise rotation. We use ρ 2 to stand for two 90 degree rotations, and so on. We can think of the function ρ as a function on the four element set1 {1, 2, 3, 4}. In particular, for any function ϕ (the Greek letter phi, usually pronounced “fee,” but sometimes “fie”) from the plane back to itself that may move the square around but otherwise leaves it in the same location, we let ϕ(i) be the label of the place where vertex previously in position i is now. Thus ρ(1) = 2, ρ(2) = 3, ρ(3) = 4 and ρ(4) = 1. Notice that ρ is a permutation on the set {1, 2, 3, 4}.

◦248. The composition f ◦g of two functions f and g is defined by f ◦g(x) = f(g(x)). Is ρ 3 the composition of ρ and ρ 2 ? Does the answer depend on the order in which we write ρ and ρ 2 ? How is ρ 2 related to ρ?

◦249. Is the composition of two permutations always a permutation? In Problem 248 you see that we can think of ρ 2 ◦ ρ as the result of first rotating by 90 degrees and then by another 180 degrees. In other words, the composition of two rotations is the same thing as first doing one and then doing the other. Of course there is nothing special about 90 degrees and 180 degrees. As long as we first do one rotation through a multiple of 90 degrees and then another rotation through a multiple of 90 degrees, the composition of these rotations is a rotation through a multiple of 90 degrees. If we first rotate by 90 degrees and then by 270 degrees then we have rotated by 360 degrees, which does nothing visible to the square. Thus we say that ρ 4 is the “identity function.” In general the identity function on a set S, denoted by ι (the Greek letter iota, pronounced eye-oh-ta) is the function that takes each element of the set to itself. In symbols, ι(x) = x for every x in S. Of course the identity function on a set is a permutation of that set.

1What we are doing is restricting the rotation ρ to the set {1, 2, 3, 4}.

## 6.1.2 Groups of permutations

◦250. For any function ϕ from a set S to itself, we define ϕ n (for nonnegative integers n) inductively by ϕ 0 = ι and ϕ n = ϕ n−1 ◦ ϕ for every positive integer n. If ϕ is a permutation, is ϕ n a permutation? Based on your experience with previous inductive proofs, what do you expect ϕ n ◦ϕ m to be? What do you expect (ϕ m) n to be? There is no need to prove these last two answers are correct, for you have, in effect, already done so in Chapter 2.

◦251. If we perform the composition ι ◦ ϕ for any function ϕ from S to S, what function do we get? What if we perform the composition ϕ ◦ ι? What you have observed about iota in Problem 251 is called the identity property of iota. In the context of permutations, people usually call the function ι “the identity” rather than calling it “iota.” Since rotating first by 90 degrees and then by 270 degrees has the same effect as doing nothing, we can think of the 270 degree rotation as undoing what the 90 degree rotation does. For this reason we say that in the rotations of the square, ρ 3 is the “inverse” of ρ. In general, a function ϕ : T → S is called an inverse of a function σ : S → T (σ is the lower case Greek letter sigma) if ϕ ◦ σ = σ ◦ ϕ = ι. For a slower introduction to inverses and practice with them, see Section A.1.3 in Appendix A. Since a permutation is a bijection, it has a unique inverse, as in Section A.1.3 of Appendix A. And since the inverse of a bijection is a bijection (again, as in the Appendix), the inverse of a permutation is a permutation. We use ϕ −1 to denote the inverse of the permutation ϕ. We’ve seen that the rotations of the square are functions that return the square to its original location but may move the vertices to different places. In this way we create permutations of the vertices of the square. We’ve observed three important properties of these permutations.

- (Identity Property) These permutations include the identity permutation.
- (Inverse Property) Whenever these permutations include ϕ, they also include ϕ −1 .
- (Closure Property) Whenever these permutations include ϕ and σ, they also include ϕ ◦ σ.

A set of permutations with these three properties is called a permutation group2 or a group of permutations. We call the group of permutations corresponding to rotations of the square the rotation group of the square. There is a similar rotation group with n elements for any regular n-gon.

252. If f : S → T, g : T → X, and h : X → Y , is h ◦ (g ◦ f) = (h ◦ g) ◦ f? What does this say about the status of the associative law ρ ◦ (σ ◦ ϕ) = (ρ ◦ σ) ◦ ϕ in a group of permutations?

253.

- •How should we define ϕ −n for an element ϕ of a permutation group? Online hint.
- •Will the two standard rules for exponents a ma n = a m+n and (a m) n = a mn still hold in a group if one or more of the exponents may be negative? (No proof required yet.)
- (c) Proving that (ϕ −m) n = ϕ −mn when m and n are nonnegative is different from proving that (ϕ m) −n = ϕ −mn when m and n are nonnegative. Make a list of all such formulas we would need to prove in order to prove that the rules of exponents of Part 253b do hold for all nonnegative and negative m and n.
- (d) If the rules hold, give enough of the proof to show that you know how to do it; otherwise give a counterexample. •254. If a finite set of permutations satisfies the closure property is it a permutation group? Online hint.

Note

2The concept of a permutation group is a special case of the concept of a group that one studies in abstract algebra. When we refer to a group in what follows, if you know what groups are in the more abstract sense, you may use the word in this way. If you do not know about groups in this more abstract sense, then you may assume we mean permutation group when we say group.

•255. There are three-dimensional geometric motions of the square that return it to its original location but move some of the vertices to other positions. For example, if we flip the square around a diagonal, most of it moves out of the plane during the flip, but the square ends up in the same location. Draw a figure like Figure 6.1 that shows all the possible results of such motions, including the ones shown in Figure 6.1. Do the corresponding permutations form a group? 256. Let σ and ϕ be permutations.

- Why must σ ◦ ϕ have an inverse?
- Is (σ ◦ϕ) −1 = σ −1ϕ −1 ? (Prove or give a counter-example.) Online hint.
- Is (σ ◦ ϕ) −1 = ϕ −1σ −1 ? (Prove or give a counter-example.)

◦257. Explain why the set of all permutations of four elements is a permutation group. How many elements does this group have? This group is called the symmetric group on four letters and is denoted by S4. 6.1.3 The symmetric group In general, the set of all permutations of an n-element set is a group. It is called the symmetric group on n letters. We don’t have nice geometric descriptions (like rotations) for all its elements, and it would be inconvenient to have to write down something like “Let σ(1) = 3, σ(2) = 1, σ(3) = 4, and σ(4) = 1” each time we need to introduce a new permutation. We introduce a new notation for permutations that allows us to denote them reasonably compactly and compose them reasonably quickly. If σ is the permutation of {1, 2, 3, 4} given by σ(1) = 3, σ(2) = 1, σ(3) = 4 and σ(4) = 2, we write σ = 1 2 3 4 3 1 4 2 . We call this notation the two row notation for permutations. In the two row notation for a permutation of {a1, a2, . . . , an}, we write the numbers a1 through an in one row and we write σ(a1) through σ(an) in a row right below, enclosing both rows in parentheses. Notice that 1 2 3 4 3 1 4 2 = 2 1 4 3 1 3 2 4 , although the second ordering of the columns is rarely used. If ϕ is given by ϕ = 1 2 3 4 4 1 2 3 ,

*Figure 6.2: How to multiply permutations in two row notation. *

) ( )= ( ) 2 1 3 4 4 2 1 3 1 4 2 1 3 2 4 3 1 2 2 3 3 1 4 ( 4 then, by applying the definition of composition of functions, we may compute σ ◦ ϕ as shown in Figure 6.2. We don’t normally put the circle between two permutations in two row notation when we are composing them, and refer to the operation as multiplying the permutations, or as the product of the permutations. To see how Figure 6.2 illustrates composition, notice that the arrow starting at 1 in ϕ goes to 4. Then from the 4 in ϕ it goes to the 4 in σ and then to 2. This illustrates that ϕ(1) = 4 and σ(4) = 2, so that σ(ϕ(1)) = 2. 258. For practice, compute 1 2 3 4 5 3 4 1 5 2 1 2 3 4 5 4 3 5 1 2 . 6.1.4 The dihedral group We found four permutations that correspond to rotations of the square. In Problem 255 you found four permutations that correspond to flips of the square in space. One flip fixes the vertices in the places labeled 1 and 3 and interchanges the vertices in the places labeled 2 and 4. Let us denote it by ϕ1|3 . One flip fixes the vertices in the positions labeled 2 and 4 and interchanges those in the positions labeled 1 and 3. Let us denote it by ϕ2|4 . One flip interchanges the vertices in the places labeled 1 and 2 and also interchanges those in the places labeled 3 and 4. Let us denote it by ϕ12|34. The fourth flip interchanges the vertices in the places labeled 1 and 4 and interchanges those in the places labeled 2 and 3. Let us denote it by ϕ14|23. Notice that ϕ1|3 is a permutation that takes the vertex in place 1 to the vertex in place 1 and the vertex in place 3 to the vertex in place 3, while ϕ12|34 is a permutation that takes the edge between places 1 and 2 to the edge between places 2 and 1 (which is the same edge) and takes the edge between places 3 and 4 to the edge between places 4 and 3 (which is the same edge). This should help to explain the similarity in the notation for the two different kinds of flips.

•259. Write down the two row notation for ρ 3 , ϕ2|4 , ϕ12|34 and ϕ2|4 ◦ϕ12|34. 260. (You may have already done this problem in Problem 255, in which case you need not do it again!) In Problem 255, if a rigid motion in three-dimensional space returns the square to its original location, in how many places can vertex number one land? Once the location of vertex number one is decided, how many possible locations are there for vertex two? Once the locations of vertex one and vertex two are decided, how many locations are there for vertex three? Answer the same question for vertex four. What does this say about the relationship between the four rotations and four flips described just before Problem 259 and the permutations you described in Problem 255? The four rotations and four flips of the square described before Problem 259 form a group called the dihedral group of the square. Sometimes the group is denoted D8 because it has eight elements, and sometimes the group is denoted by D4 because it deals with four vertices! Let us agree to use the notation D4 for the dihedral group of the square. There is a similar dihedral group, denoted by Dn, of all the rigid motions of three-dimensional space that return a regular n-gon to its original location (but might put the vertices in different places).

261. Another view of the dihedral group of the square is that it is the group of all distance preserving functions, also called isometries, from a square to itself. Notice that an isometry must be a bijection. Any rigid motion of the square preserves the distances between all points of the square. However, it is conceivable that there might be some isometries that do not arise from rigid motions. (We will see some later on in the case of a cube.) Show that there are exactly eight isometries (distance preserving functions) from a square to itself. Online hint.

262. How many elements does the group Dn have? Prove that you are correct.

•263. In Figure 6.3 we show a cube with the positions of its vertices and faces labeled. As with motions of the square, we let we let ϕ(x) be the label of the place where vertex previously in position x is now. (a) Write in two row notation the permutation ρ of the vertices that corresponds to rotating the cube 90 degrees around a vertical axis through the faces t (for top) and u (for underneath). (Rotate in

*Figure 6.3: A cube with the positions of its vertices and faces labeled. *

The curved arrows point to the faces that are blocked by the cube. u b f l t r 4 3 5 1 6 8 7 2 a right-handed fashion around this axis, meaning that vertex 6 goes to the back and vertex 8 comes to the front.) (b) Write in two row notation the permutation ϕ that rotates the cube 120 degrees around the diagonal from vertex 1 to vertex 7 and carries vertex 8 to vertex 6. (c) Compute the two row notation for ρ ◦ ϕ. (d) Is the permutation ρ◦ϕ a rotation of the cube around some axis? If so, say what the axis is and how many degrees we rotate around the axis. If ρ ◦ ϕ is not a rotation, give a geometric description of it.

·264. How many permutations are in the group R? R is sometimes called the “rotation group” of the cube. Can you justify this? Online hint. 265. As with a two-dimensional figure, it is possible to talk about isometries of a three-dimensional figure. These are distance preserving functions from the figure to itself. The function that reflects the cube in Figure 6.3 through a plane halfway between the bottom face and top face exchanges the vertices 1 and 5, 2 and 6, 3 and 7, and 4 and 8 of the cube. This function preserves distances between points in the cube. However, it cannot be achieved by a rigid motion of the cube because a rigid motion that takes vertex 1 to vertex 5, vertex 2 to vertex 6, vertex 3 to vertex 7, and vertex 4 to vertex 8 would not return the cube to its original location; rather it would put the bottom of the cube where its top previously was and would put the rest of the cube above that square rather than below it.

(a) How many elements are there in the group of permutations of [8] that correspond to isometries of the cube? Online hint. (b) Is every permutation of [8] that corresponds to an isometry either a rotation or a reflection? Online hint. 6.1.5 Group tables (Optional)

We can always figure out the composition of two permutations of the same set by using the definition of composition, but if we are going to work with a given permutation group again and again, it is worth making the computations once and recording them in a table. For example, the group of rotations of the square may be represented as in Table 6.1. We list the elements of our group, with the identity first, across the top of the table and down the left side of the table, using the same order both times. Then in the row labeled by the group element σ and the column labeled by the group element ϕ, we write the composition σ ◦ ϕ, expressed in terms of the elements we have listed on the top and on the left side. Since a group of permutations is closed under composition, the result σ ◦ ϕ will always be expressible as one of these elements.

*Table 6.1: The group table for the rotations of a square. *

◦ ι ρ ρ2 ρ 3 ι ι ρ ρ2 ρ 3 ρ ρ ρ2 ρ 3 ι ρ 2 ρ 2 ρ 3 ι ρ ρ 3 ρ 3 ι ρ ρ2 266. In Table 6.1, all the entries in a row (not including the first entry, the one to the left of the line) are different. Will this be true in any group table for a permutation group? Why or why not? Also in Table 6.1 all the entries in a column (not including the first entry, the one above the line) are different. Will this be true in any group table for a permutation group? Why or why not? 267. In Table 6.1, every element of the group appears in every row (even if you don’t include the first element, the one before the line). Will this be true in any group table for a permutation group? Why or why not? Also in Table 6.1 every element of the group appears in every column (even if you don’t include the first entry, the one before the line). Will this be true in any group table for a permutation group? Why or why not?

·268. Write down the group table for the dihedral group D4. Use the ϕ notation described earlier to denote the flips. (Hints: Part of the table has already been written down. Will you need to think hard to write down the last row? Will you need to think hard to write down the last column?) You may notice that the associative law, the identity property, and the inverse property are three of the most important rules that we use in regrouping parentheses in algebraic expressions when solving equations. There is one property we have not yet mentioned, the commutative law, which would say that σ ◦ ϕ = ϕ ◦ σ. It is easy to see from the group table of the rotation group of a square that it satisfies the commutative law.

269. Does the commutative law hold in all permutation groups? 6.1.6 Subgroups We have seen that the dihedral group D4 contains a copy of the group of rotations of the square. When one group G of permutations of a set S is a subset of another group G0 of permutations of S, we say that G is a subgroup of G0 . ◦270. Find all subgroups of the group D4 and explain why your list is complete. Online hint. 271. Can you find subgroups of the symmetric group S4 with two elements? Three elements? Four elements? Six elements? (For each positive answer, describe a subgroup. For each negative answer, explain why not.)

The cycle decomposition of a permutation The digraph of a permutation gives us a nice way to think about it. Notice that the product in Figure 6.2 is 1 2 3 4 2 3 1 4 . We have drawn the directed graph of this permutation in Figure 6.4. You see that the graph Figure 6.4: The directed graph of the permutation 1 2 3 4 2 3 1 4 . 1 3 2 4 has two directed cycles, the rather trivial one with vertex 4 pointing to itself, and the nontrivial one with vertex 1 pointing to vertex 2 pointing to vertex 3 which points back to vertex 1. A permutation is called a cycle if its digraph consists of exactly one cycle. Thus 1 2 3 2 3 1 is a cycle but 1 2 3 4 2 3 1 4 is not a cycle by our definition. We write (1 2 3) or (2 3 1) or (3 1 2) to stand for the cycle σ = 1 2 3 2 3 1 . We can describe cycles in another way as well. A cycle of the permutation σ is a list (i σ(i) σ 2 (i) . . . σn (i)) that does not have repeated elements while the list (i σ(i) σ 2 (i) . . . σn (i) σ n+1(i)) does have repeated elements.

272. If the list (i σ(i) σ 2 (i) . . . σn (i)) does not have repeated elements but the list (i σ(i) σ 2 (i) . . . σn (i) σ n+1(i)) does have repeated elements, then what is σ n+1(i)? Online hint. We say σ j (i) is an element of the cycle (i σ(i) σ 2 (i) . . . σn (i)). Notice that the case j = 0 means i is an element of the cycle. Notice also that if j > n, σ j (i) = σ j−n−1 (i), so the distinct elements of the cycle are i, σ(i), σ 2 (i), through σ n (i). We think of the cycle (i σ(i) σ 2 (i) . . . σn (i)) as representing the permutation σ restricted to the set of elements of the cycle. 124 CHAPTER 6. GROUPS ACTING ON SETS We say that the cycles (i σ(i) σ 2 (i) . . . σn (i)) and (σ j (i) σ j+1(i) . . . σn (i) i σ(i) σ 2 (i) . . . σj−1 (i)) are equivalent. Equivalent cycles represent the same permutation on the set of elements of the cycle. For this reason, we consider equivalent cycles to be equal in the same way we consider 1 2 and 2 4 to be equal. In particular, this means that (i1 i2 . . . in) = (ij ij+1 . . . in i1 i2 . . . ij−1). •273. Find the cycles of the permutations ρ, ϕ1|3 and ϕ12|34 in the group D4.

◦274. Find the cycles of the permutation 1 2 3 4 5 6 7 8 9 3 4 6 2 9 7 1 5 8 . 275. If two cycles of σ have an element in common, what can we say about them? Problem 275 leads almost immediately to the following theorem. Theorem 8 For each permutation σ of a set S, there is a unique partition of S each of whose blocks is the set of elements of a cycle of σ. More informally, we may say that every permutation partitions its domain into disjoint cycles. We call the set of cycles of a permutation the cycle decomposition of the permutation. Since the cycles of a permutation σ tell us σ(x) for every x in the domain of σ, the cycle decomposition of a permutation completely determines the permutation. Using our informal language, we can express this idea in the following corollary to Theorem 8. Corollary 2 Every partition of a set S into cycles determines a unique permutation of S. 276. Prove Theorem 8. In Problems 273 and 274 you found the cycle decompositions of typical elements of the group D4 and of the permutation 1 2 3 4 5 6 7 8 9 3 4 6 2 9 7 1 5 8 . 6.2. GROUPS ACTING ON SETS 125 The group of all rotations of the square is simply the set of the four powers of the cycle ρ = (1 2 3 4). For this reason, it is called a cyclic group3 and often denoted by C4. Similarly, the rotation group of an n-gon is usually denoted by Cn. 277. Write a recurrence for the number c(k, n) of permutations of [k] that have exactly n cycles, including 1-cycles. Use it to write a table of c(k, n) for k between 1 and 7 inclusive. Can you find a relationship between c(k, n) and any of the other families of special numbers such as binomial coefficients, Stirling numbers, Lah numbers, etc. we have studied? If you find such a relationship, prove you are right. Online hint. ·278. (Relevant to Appendix C.) A permutation σ is called an involution if σ 2 = ι. When you write down the cycle decomposition of an involution, what is special about the cycles?