Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section15.3Permutation Groups

Subsection15.3.1The Symmetric Groups

At the risk of boggling the reader's mind, we will now examine groups whose elements are functions. Recall that a permutation on a set \(A\) is a bijection from \(A\) into \(A\text{.}\) Suppose that \(A = \{1, 2, 3\}\). There are \(3! = 6\) different permutations on \(A\text{.}\) We will call the set of all 6 permutations \(S_3\). They are listed in the following table. The matrix form for describing a function on a finite set is to list the domain across the top row and the image of each element directly below it. For example \(r_1(1) = 2\).

\(i =\left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{array} \right)\) \(r_1=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{array} \right)\) \(r_2=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right)\)
\(f_1=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \\ \end{array} \right) \) \(f_2=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \\ \end{array} \right)\) \(f_3=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \\ \end{array} \right)\)
Table15.3.1Elements of \(S_3\)

The operation that will give \(\left\{i,r_1,r_2,f_1,f_2,f_3\right\}\) a group structure is function composition. Consider the “product” \(r_1\circ f_3\): \begin{equation*} \begin{array}{c} r_1\circ f_3(1) =r_1\left(f_3(1)\right)= r_1(2)=3 \\ r_1\circ f_3(2)=r_1\left(f_3(2)\right)= r_1(1)= 2 \\ r_1\circ f_3(3)=r_1\left(f_3(3)\right)= r_1(3)= 1\\ \end{array} \text{.} \end{equation*}

The images of 1, 2, and 3 under \(r_1\circ f_3\) and \(f_2\) are identical. Thus, by the definition of equality for functions, we can say \(r_1\circ f_3=f_2\) . The complete table for the operation of function composition is given in Table 15.3.2.

\(\begin{array}{c|cccccc} \circ & i &r_1 & r_2 & f_1 & f_2 & f_3 \\ \hline i & i &r_1 & r_2 & f_1 & f_2 & f_3 \\ r_1 & r_1 &r_2 & i & f_3 & f_1 & f_2 \\ r_2 & r_2 &i & r_1 & f_2 & f_3 & f_1 \\ f_1 & f_1 & f_2 & f_3 & i & r_1 & r_2 \\ f_2 & f_2 &f_3 & f_1 & r_2 & i & r_1 \\ f_3 & f_3 & f_1 & f_2 & r_1 & r_2 & i \\ \end{array}\)
Table15.3.2Operation Table for \(S_3\)
List15.3.3

We don't even need the table to verify that we have a group. Based on the following observations, the set of all permutations on any finite set will be a group.

  1. Function composition is always associative.

  2. The identity for the group is \(i\text{.}\) If \(g\) is any one of the permutations on \(A\) and \(x\in A\), \begin{equation*} \begin{array}{lr} (g\circ i)(x) = g(i(x)) = g(x) &(i\circ g)(x) = i(g(x)) = g(x)\\ \end{array} \end{equation*} Therefore \(g\circ i = i\circ g=g\).

  3. A permutation, by definition, is a bijection. In Chapter 7 we proved that this implies that it must have an inverse and the inverse itself is a bijection and hence a permutation. Hence all elements of \(S_3\) have an inverse in \(S_3\). If a permutation is displayed in matrix form, its inverse can be obtained by exchanging the two rows and rearranging the columns so that the top row is in order. The first step is actually sufficient to obtain the inverse, but the sorting of the top row makes it easier to recognize the inverse.

    For example, lets consider a typical permutation on \(\{1,2,3,4,5\}\), \(f= \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 2 & 1 & 4 \\ \end{array} \right)\). \begin{equation*} f^{-1}= \left( \begin{array}{ccccc} 5 & 3 & 2 & 1 & 4 \\ 1 & 2 & 3 & 4 & 5 \\ \end{array} \right)= \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \\ \end{array} \right) \text{.} \end{equation*}

Note15.3.4

From Table 15.3.2, we can see that \(S_3\) is non-abelian. Remember, non-abelian is the negation of abelian. The existence of two elements that don't commute is sufficient to make a group non-abelian. In this group, \(r_1\) and \(f_3\) is one such pair: \(r_1\circ f_3= f_2\) while \(f_3\circ r_1= f_1\), so \(r_1\circ f_3\neq f_3\circ r_1\). Caution: Don't take this to mean that every pair of elements has to have this property. There are several pairs of elements in \(S_3\) that do commute. In fact, the identity, \(i\text{,}\) must commute with everything. Also every element must commute with its inverse.

Definition15.3.5Symmetric Group

Let \(A\) be a nonempty set. The set of all permutations on \(A\) with the operation of function composition is called the symmetric group on A, denoted \(S_A\).

The cardinality of a finite set \(A\) is more significant than the elements, and we will denote by \(S_n\) the symmetric group on any set of cardinality \(n\). \(n\geq 1\).

Example15.3.6The significance of \(S_3\)

Our opening example, \(S_3\), is the smallest non-abelian group. For that reason, all of its proper subgroups are abelian: in fact, they are all cyclic. Figure 15.3.7 shows the Hasse diagram for the subgroups of \(S_3\).

Lattice diagram of subgroups of \(S_3\)
Figure15.3.7Lattice diagram of subgroups of \(S_3\)
Example15.3.8Smallest Symmetric Groups

The only abelian symmetric groups are \(S_1\) and \(S_2\) , with 1 and 2 elements, respectively. The elements of \(S_2\) are \(i = \left( \begin{array}{cc} 1 & 2 \\ 1 & 2 \\ \end{array} \right)\) and \(\alpha = \left( \begin{array}{cc} 1 & 2 \\ 2 & 1 \\ \end{array} \right)\)

\(S_2\) is isomorphic to \(\mathbb{Z}_2\).

Proof

Subsection15.3.2Cycle Notation

A second way of describing a permutation is by means of cycles, which we will introduce first with an example. Consider \(f\in S_8\) defined using the now-familiar matrix notation: \[f=\left( \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 2 & 7 & 6 & 5 & 4 & 1 & 3 \\ \end{array} \right)\] Consider the images of 1 when \(f\) is applied repeatedly. The images \(f(1)\), \(f(f(1))\), \(f(f(f(1))), \ldots\) are \(8, 3, 7, 1, 8, 3, 7,\ldots\). If \(j\geq 1\), In Figure 15.3.2(a), this situation is represented by the component of the graph that consists of 1, 8, 3, and 7 and shows that the values that you get by repeatedly applying \(f\) cycle through those values. This is why we refer to this part of \(f\) as a cycle of length 4. . Of course starting at 8, 3, or 7 also produces the same cycle with only the starting valued changing.

Representations of a cycle of length 4
Figure15.3.10Representations of a cycle of length 4

Figure 15.3.10(a) illustrates how the cycle can be represented in a visual manner, but it is a bit awkward to write.. Part (b) of the figure presents a more universally recognized way to write a cycle. In (b), a cycle is represented by a list where the image of any number in the list is its successor. In addition, the last number in the list has as its image the first number.

The other elements of the domain of \(f\text{,}\) are never reached if you start in the cycle \((1,8,3,7)\), and so looking at image of these other numbers will produce numbers that are disjoint from the set \(\{1,8,3,7\}\). The other disjoint cycles of \(f\) are (2), (4, 6), and (5). We can express \(f\) as a product of disjoint cycles: \(f= (1, 8, 3, 7)(2)(4, 6)(5)\) or \(f= (1,8,3,7)(4,6)\), where the absence of 2 and 5 implies that \(f(2) = 2\) and \(f(5) = 5\).

Note15.3.11Disjoint Cycles

We say that two cycles are disjoint if no number appears in both cycles, as is the case in our expressions for \(f\) above. Disjoint cycles can be written in any order. Thus, we could also say that \(f=(4,6)(1,8,3,7)\).

Note15.3.12Composition of Permutations

We will now consider the composition of permutations written in cyclic form by an example. Suppose that \(f = (1,8, 3, 7)(4, 6)\) and \(g = (1, 5, 6)(8, 3, 7, 4)\) are elements of \(S_8\). To calculate \(f\circ g\), we start with simple concatenation: \begin{gather} f \circ g = (1,8, 3, 7)(4, 6)(1,5,6)(8, 3, 7,4)\label{equation-cycle-composition-1}\tag{15.3.1} \end{gather} Although this is a valid expression for \(f \circ g\), our goal is to express the composition as a product of disjoint cycles as \(f\) and \(g\) were individually written. We will start by determining the cycle that contains 1. When combining any number of cycles, they are always read from right to left, as with all functions. The first cycle in (15.3.1) does not contain 1; thus we move on to the second. The image of 1 under that cycle is 5. Now we move on to the next cycle, looking for 5, which doesn't appear. The fourth cycle does not contain a 5 either; so \(f\circ g(1) = 5\).

At this point, we would have written “\(f \circ g = (1,5\quad \)” on paper. We repeat the steps to determine \(f\circ g(5)\). This time the second cycle of (15.3.1) moves 5 to 6 and then the third cycle moves 6 to 4. Therefore, \(f\circ g(5) = 4\). We continue until the cycle (1, 5, 4, 3) is completed by determining that \(f\circ g(3) = 1\). The process is then repeated starting with any number that does not appear in the cycle(s) that have already been completed.

The final result for our example is \(f \circ g = (1, 5, 4, 3)(6, 8, 7)\). Since \(f(2) = 2\) and \(g(2) = 2\), \(f\circ g(2) = 2\) and we need not include the one-cycle (2) in the final result, although it can be included.

Example15.3.13Some Compositions

  1. \((1, 2, 3, 4)(1, 2, 3, 4) = (1, 3)(2, 4)\)

  2. \((1, 4)(1, 3)(1, 2) = (1, 2, 3, 4)\).

Notice that cyclic notation does not indicate the set which is being permuted. The examples above could be in \(S_5\), where the image of 5 is 5. This ambiguity is usually overcome by making the context clear at the start of a discussion.

Definition15.3.14Transposition

A transposition is a cycle of length 2.

Observation15.3.15About transpositions

\(f= (1, 4)\) and \(g=(4,5)\) are transpositions in \(S_5\). However, \(f\circ g = (1,4, 5)\) and \(g \circ f = (1, 5, 4)\) are not transpositions; thus, the set of transpositions is not closed under composition. Since \(f^2=f\circ f\) and \(g^2=g\circ g\) are both equal to the identity permutation, \(f\) and \(g\) are their own inverses. In fact, every transposition is its own inverse.

Proof

Of course, a product of cycles can be written as a product of transpositions just as easily by applying the rule above to each cycle. For example, \[(1, 3, 5, 7)(2, 4, 6) = (1, 7)(1, 5)(1, 3)(2, 6)(2, 4)\] Unlike the situation with disjoint cycles, we are not free to change the order of these transpositions.

Subsection15.3.3Parity of Permutations and the Alternating Group

A decomposition of permutations into transpositions makes it possible to classify then and identify an important family of groups.

The proofs of the following theorem appears in many abstract algebra texts.

Theorem 15.3.17 suggests that \(S_n\) can be partitioned into its “even” and “odd” elements. For example, the even permutations of \(S_3\) are \(i\), \(r_1=(1,2,3)=(1,3)(1,2)\) and \(r_2=(1,3,2)=(1,2)(1,3)\) . They form a subgroup, \(\left\{i,r_1,r_2\right\}\) of \(S_3\).

In general:

Definition15.3.18The Alternating Group

Let \(n \geq 2\). The set of even permutations in \(S_n\) is a proper subgroup of \(S_n\) called the alternating group on \(\{1, 2, \ldots, n\}\), denoted \(A_n\).

We justify our statement that \(A_n\) is a group:

Proof
Example15.3.20The Sliding Tile Puzzle

Consider the sliding-tile puzzles pictured in Figure 15.3.21. Each numbered square is a tile and the dark square is a gap. Any tile that is adjacent to the gap can slide into the gap. In most versions of this puzzle, the tiles are locked into a frame so that they can be moved only in the manner described above. The object of the puzzle is to arrange the tiles as they appear in Configuration (a). Configurations (b) and (c) are typical starting points. We propose to show why the puzzle can be solved starting with (b), but not with (c).

Configurations of the sliding tile puzzle
Figure15.3.21Configurations of the sliding tile puzzle

We will associate a change in the configuration of the puzzle with an element of \(S_{16}\). Imagine that a tile numbered 16 fills in the gap. For any configuration of the puzzle, the identity \(i\text{,}\) is the function that leave the configurate “as is.” In general, if \(f \in S_{16}\), and \(1 \leq k \leq 16\), \(f(k)\) is the position to which the tile in position \(k\) is moved by \(f\). that appears in the position of \(k\) in configuration (a). If we call the functions that, starting with configuration (a), result in configurations (b) and (c) by the names \(f_1\) and \(f_2\), respectively, \[f_1 = (1, 5, 3, 7)(2, 6, 4, 8)(9, 10)(11, 14, 13, 12)(15)(16)\] and \[f_2 = (1, 5, 3, 7, 15)(2, 6, 4, 8)(9, 10)(11, 14, 13, 12)(16)\].

How can we interpret the movement of one tile as a permutation? Consider what happens when the 12 tile of \(i\) slides into the gap. The result is a configuration that we would interpret as \((12,16)\), a single transposition. Now if we slide the 8 tile into the 12 position, the result is or \((8, 16, 12)\). Hence, by “exchanging” the tiles 8 and 16, we have implemented the function \((8, 12) (12, 16) = (8, 12, 16)\).

The configuration \((8, 12, 16)\)
Figure15.3.22The configuration \((8, 12, 16)\)

Every time you slide a tile into the gap, the new permutation is a transposition composed with the old permutation. Now observe that to start with initial configuration and terminate after a finite number of moves with the gap in its original position, you must make an even number of moves. Thus, configuration corresponding any permutation that leaves 16 fixed cannot be solved if the permutation is odd. Note that \(f_2\) is an odd permutation; thus, Puzzle (c) can't be solved. The proof that all even permutations, such as \(f_1\), can be solved is left to the interested reader to pursue.

Subsection15.3.4Dihedral Groups

Observation15.3.23Realizations of Groups

By now we've seen several instances where a group can appear through an isomorphic copy of itself in various settings. The simplest such example is the cyclic group of order 2. When this group is mentioned, we might naturally think of the group \(\left[\mathbb{Z}_2,+_2\right]\), but the groups \([\{-1,1\},\cdot ]\) and \(\left[S_2,\circ \right]\) are isomorphic to it. None of these groups are necessarily more natural or important than the others. Which one you use depends on the situation you are in and all are referred to as realizations of the cyclic group of order 2. The next family of groups we will study, the dihedral groups, has two natural realizations, first as permutations and second as geometric symmetries.

The family of dihedral groups is indexed by the positive integers greater than or equal to 3. For \(k \geq 3\), \(D_k\) will have \(2k\) elements. We first describe the elements and the operation on them using geometry.

We can describe \(D_n\) in terms of symmetries of a regular \(n\)-gon (\(n = 3\): equilateral triangle, \(n = 4\): square, \(n = 5\): regular pentagon,\( \ldots \)). Here we will only concentrate on the case of \(D_4\). If a square is fixed in space, there are several motions of the square that will, at the end of the motion, not change the apparent position of the square. The actual changes in position can be seen if the corners of the square are labeled. In Figure 15.3.24, the initial labeling scheme is shown, along with the four axes of symmetry of the square.

Axes of symmetry of the square
Figure15.3.24Axes of symmetry of the square

It might be worthwhile making a square like this with a sheet of paper. Be careful to label the back so that the numbers match the front. Two motions of the square will be considered equivalent if the square is in the same position after performing either motion. There are eight distinct motions. The first four are \(0{}^{\circ}\), \(90{}^{\circ}\), \(180{}^{\circ}\), and \(270{}^{\circ}\) clockwise rotations of the square, and the other four are the \(180{}^{\circ}\) flips along the axes \(l_1\), \(l_2\), \(l_3\), and \(l_4\). We will call the rotations \(i, r_1\), \(r_2\), and \(r_3\), respectively, and the flips \(f_1\), \(f_2\), \(f_3\), and \(f_4\), respectively. Figure 15.3.25 illustrates \(r_1\) and \(f_1\). For future reference, we also include the permutations to which they correspond.

Two elements of \(D_4\)
Figure15.3.25Two elements of \(D_4\)

What is the operation on this set of symmetries? We will call the operation “followed by” and use the symbol \(*\) to represent it. The operation will be to combine motions, applying motions from right to left, as with functions. We will illustrate how \(*\) is computed by finding \(r_1*f_1\). Starting with the initial configuration, if you perform the \(f_1\) motion, and then immediately perform \(r_1\) on the result, we get the same configuration as if we just performed \(f_4\), which is to flip the square along the line \(l_4\). Therefore, \(r_1*f_1 = f_4\). An important observation is that \(f_1*r_1 \neq f_4\), meaning that this group is nonabelian. The reader is encouraged to verify this on their own.

We can also realize the dihedral groups as permutations. For any symmetric motion of the square we can associate with it a permutation. In the case of \(D_4\), the images of each of the numbers 1 through 4 are the positions on the square that each of the corners 1 through 4 are moved to. For example, since corner 4 moves to position 1 when you perform \(r_1\), the corresponding function will map 4 to 1. In addition, 1 gets mapped to 2, 2 to 3 and 3 to 4. Therefore, \(r_1\) is the cycle \((1,2,3,4)\) . The flip \(f_1\) transposes two pairs of corners and corresponds to \((1,4)(2,3)\). If we want to combine these two permutations, using the same names as with motions, we get \[r_1\circ f_1= (1,2,3,4)\circ (1,4)(2,3)=(1)(2,4)(3) = (2,4)\] Notice that this permutation corresponds with the flip \(f_4\).

Although \(D_4\) isn't cyclic (since it isn't abelian), it can be generated from the two elements \(r_1\) and \(f_1\): \[D_4= \left\langle r_1,f_1\right\rangle = \left\{i, r_1, r_1{}^2, r_1{}^3, f_1, r_1\circ f_1, r_1{}^2\circ f_1, r_1{}^3\circ f_1\right\}\]

It is quite easy to describe any of the dihedral groups in a similar fashion. Let \(r= (1,2, \ldots , n)\), an \(n\)-cycle, and \(f= (1,n)(2,n-1)\ldots\) Then \[D_n= \langle r,f\rangle = \left\{i, r, r^2, \ldots, r^{n-1}, f, r\circ f, r^2\circ f, \ldots, r^{n-1}\circ f\right\}\]

Example15.3.26A Letter-facing Machine

An application of \(D_4\) is in the design of a letter-facing machine. Imagine letters entering a conveyor belt to be postmarked. They are placed on the conveyor belt at random so that two sides are parallel to the belt. Suppose that a postmarker can recognize a stamp in the top right corner of the envelope, on the side facing up. In Figure 15.3.27, a sequence of machines is shown that will recognize a stamp on any letter, no matter what position in which the letter starts. The letter \(P\) stands for a postmarker. The letters \(R\) and \(F\) stand for rotating and flipping machines that perform the motions of \(r_1\) and \(f_1\).

A letter facer
Figure15.3.27A letter facer

The arrows pointing up indicate that if a letter is postmarked, it is taken off the conveyor belt for delivery. If a letter reaches the end, it must not have a stamp. Letter-facing machines like this have been designed (see Gallian's paper). One economic consideration is that \(R\)-machines tend to cost more than \(F\)-machines. \(R\)-machines also tend to damage more letters. Taking these facts into consideration, the reader is invited to design a better letter-facing machine. Assume that \(R\)-machines cost \(\$800\) and \(F\)-machines cost \(\$500\). Be sure that all corners of incoming letters will be examined as they go down the conveyor belt.

Subsection15.3.5Exercises for Section 15.3

1

Given \(f=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \right)\), \(g=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \right)\), and \(h=\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \\ \end{array} \right)\), compute

  1. \(f\circ g\)

  2. \(g\circ h\)

  3. \((f\circ g)\circ h\)

  4. \(f\circ (g\circ h)\)

  5. \(h^{-1}\)

  6. \(h^{-1} g\circ h\)

  7. \(f^{-1}\)

Answer
2

Write \(f\text{,}\) \(g\text{,}\) and \(h\) from Exercise 1 as products of disjoint cycles and determine whether each is odd or even.

3

Do the left cosets of \(A_3=\left\{i,r_1,r_2\right\}\) over \(S_3\) form a group under the induced operation on left cosets of \(A_3\)? What about the left cosets of \(\left\langle f_1\right\rangle\)?

Answer
4

In its realization as permutations, the dihedral group \(D_3\) is equal to \(S_3\). Can you give a geometric explanation why? Why isn't \(D_4\) equal to \(S_4\)?

5

  1. Complete the list of elements of \(D_4\) and write out a table for the group in its realization as symmetries.

  2. List the subgroups of \(D_4\) in a lattice diagram. Are they all cyclic? To what simpler groups are the subgroups of \(D_4\) isomorphic?

Answer
6

Design a better letter-facing machine (see Example 15.3.26). How can you verify that a letter-facing machine does indeed check every corner of a letter? Can it be done on paper without actually sending letters through it?

7

Prove by induction that if \(r \geq 1\) and each \(t_i\), is a transposition, then \(\left(t_1\circ t_2\circ \cdots \circ t_r\right){}^{-1}=t_r\circ \cdots \circ t_2\circ t_1\)

Answer
8

How many elements are there in \(D_5\) ? Describe them geometrically.

9

Complete the proof of Theorem 15.3.9.

Answer
10

How many left cosets does \(A_n\), \(n\geq 2\) have?

11

Prove that \(f\circ r= r^{n-1}\circ f\) in \(D_n\).

12

  1. Prove that the tile puzzles corresponding to \(A_{16}\cap \left\{ \left.f \in S_{16} \right| f(16) = 16\right\}\) are solvable.

  2. If \(f(16)\neq 16\), how can you determine whether f's puzzle is solvable?

13

  1. Prove that \(S_3\) is isomorphic to \(R_3\), the group of \(3 \times 3\) rook matrices (see Section 11.2 exercises).

  2. Prove that for each \(n \geq 2\), \(R_n\) is isomorphic to \(S_n\).

Answer