Skip to main content

Section 2.6 Permutation Groups

Permutation groups are central to the study of geometric symmetries and to Galois theory, the study of finding solutions of polynomial equations. They also provide abundant examples of nonabelian groups.

Let us recall for a moment the symmetries of the equilateral triangle \(\bigtriangleup ABC\) from Chapter 2 . The symmetries actually consist of permutations of the three vertices, where a permutation of the set \(S = \{ A, B, C \}\) is a one-to-one and onto map \(\pi :S \rightarrow S\text{.}\) The three vertices have the following six permutations.

\begin{align*} \begin{pmatrix} A & B & C \\ A & B & C \end{pmatrix} \qquad \begin{pmatrix} A & B & C \\ C & A & B \end{pmatrix} \qquad \begin{pmatrix} A & B & C \\ B & C & A \end{pmatrix}\\ \begin{pmatrix} A & B & C \\ A & C & B \end{pmatrix} \qquad \begin{pmatrix} A & B & C \\ C & B & A \end{pmatrix} \qquad \begin{pmatrix} A & B & C \\ B & A & C \end{pmatrix} \end{align*}

We have used the array

\begin{equation*} \begin{pmatrix} A & B & C \\ B & C & A \end{pmatrix} \end{equation*}

to denote the permutation that sends \(A\) to \(B\text{,}\) \(B\) to \(C\text{,}\) and \(C\) to \(A\text{.}\) That is,

\begin{align*} A & \mapsto B\\ B & \mapsto C\\ C & \mapsto A\text{.} \end{align*}

The symmetries of a triangle form a group. In this section we will study groups of this type.

In general, the permutations of a set \(X\) form a group \(S_X\text{.}\) If \(X\) is a finite set, we can assume \(X=\{ 1, 2, \ldots, n\}\text{.}\) In this case we write \(S_n\) instead of \(S_X\text{.}\) The following theorem says that \(S_n\) is a group. We call this group the symmetric group on \(n\) letters.

Proof.

The identity of \(S_n\) is just the identity map that sends \(1\) to \(1\text{,}\) \(2\) to \(2\text{,}\) \(\ldots\text{,}\) \(n\) to \(n\text{.}\) If \(f : S_n \rightarrow S_n\) is a permutation, then \(f^{-1}\) exists, since \(f\) is one-to-one and onto; hence, every permutation has an inverse. Composition of maps is associative, which makes the group operation associative. We leave the proof that \(|S_n|= n!\) as an exercise.

A subgroup of \(S_n\) is called a permutation group.

Example 2.48.

Consider the subgroup \(G\) of \(S_5\) consisting of the identity permutation \(\identity\) and the permutations

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 & 5 \end{pmatrix}\\ \mu & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4 \end{pmatrix}\text{.} \end{align*}

The following table tells us how to multiply elements in the permutation group \(G\text{.}\)

\begin{equation*} \begin{array}{c|cccc} \circ & \identity & \sigma & \tau & \mu \\ \hline \identity & \identity & \sigma & \tau & \mu \\ \sigma & \sigma & \identity & \mu & \tau \\ \tau & \tau & \mu & \identity & \sigma \\ \mu & \mu & \tau & \sigma & \identity \end{array} \end{equation*}
Remark 2.49.

Though it is natural to multiply elements in a group from left to right, functions are composed from right to left. Let \(\sigma\) and \(\tau\) be permutations on a set \(X\text{.}\) To compose \(\sigma\) and \(\tau\) as functions, we calculate \((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) That is, we do \(\tau\) first, then \(\sigma\text{.}\) There are several ways to approach this inconsistency. We will adopt the convention of multiplying permutations right to left. To compute \(\sigma \tau\text{,}\) do \(\tau\) first and then \(\sigma\text{.}\) That is, by \(\sigma \tau (x)\) we mean \(\sigma( \tau( x))\text{.}\) (Another way of solving this problem would be to write functions on the right; that is, instead of writing \(\sigma(x)\text{,}\) we could write \((x)\sigma\text{.}\) We could also multiply permutations left to right to agree with the usual way of multiplying elements in a group. Certainly all of these methods have been used.

Example 2.50.

Permutation multiplication is not usually commutative. Let

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}\text{.} \end{align*}

Then

\begin{equation*} \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}\text{,} \end{equation*}

but

\begin{equation*} \tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}\text{.} \end{equation*}

Subsection 2.6.1 Cycle Notation

The notation that we have used to represent permutations up to this point is cumbersome, to say the least. To work effectively with permutation groups, we need a more streamlined method of writing down and manipulating permutations.

A permutation \(\sigma \in S_X\) is a cycle of length \(k\) if there exist elements \(a_1, a_2, \ldots, a_k \in X\) such that

\begin{align*} \sigma( a_1 ) & = a_2\\ \sigma( a_2 ) & = a_3\\ & \vdots\\ \sigma( a_k ) & = a_1 \end{align*}

and \(\sigma( x) = x\) for all other elements \(x \in X\text{.}\) We will write \((a_1, a_2, \ldots, a_k )\) to denote the cycle \(\sigma\text{.}\) Cycles are the building blocks of all permutations.

Example 2.51.

The permutation

\begin{equation*} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 6 & 3 & 5 & 1 & 4 & 2 & 7 \end{pmatrix} = (1 6 2 3 5 4 ) \end{equation*}

is a cycle of length \(6\text{,}\) whereas

\begin{equation*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 2 & 3 & 5 & 6 \end{pmatrix} = (2 4 3) \end{equation*}

is a cycle of length \(3\text{.}\)

Not every permutation is a cycle. Consider the permutation

\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} = (1 2 4 3)(5 6)\text{.} \end{equation*}

This permutation actually contains a cycle of length 2 and a cycle of length \(4\text{.}\)

Example 2.52.

It is very easy to compute products of cycles. Suppose that

\begin{equation*} \sigma = (1 3 5 2 ) \quad \text{and} \quad \tau = (2 5 6)\text{.} \end{equation*}

If we think of \(\sigma\) as

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 2, \qquad 2 \mapsto 1\text{,} \end{equation*}

and \(\tau\) as

\begin{equation*} 2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2\text{,} \end{equation*}

then for \(\sigma \tau\) remembering that we apply \(\tau\) first and then \(\sigma\text{,}\) it must be the case that

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2 \mapsto 1\text{,} \end{equation*}

or \(\sigma \tau = (1 3 5 6 )\text{.}\) If \(\mu = (1634)\text{,}\) then \(\sigma \mu = (1 6 5 2)(3 4)\text{.}\)

Two cycles in \(S_X\text{,}\) \(\sigma = (a_1, a_2, \ldots, a_k )\) and \(\tau = (b_1, b_2, \ldots, b_l )\text{,}\) are disjoint if \(a_i \neq b_j\) for all \(i\) and \(j\text{.}\)

Example 2.53.

The cycles \((1 3 5)\) and \((2 7 )\) are disjoint; however, the cycles \((1 3 5)\) and \((3 4 7 )\) are not. Calculating their products, we find that

\begin{align*} (1 3 5)(2 7 ) & = (1 3 5)(2 7 )\\ (1 3 5)(3 4 7 ) & = (1 3 4 7 5)\text{.} \end{align*}

The product of two cycles that are not disjoint may reduce to something less complicated; the product of disjoint cycles cannot be simplified.

Proof.

Let \(\sigma = (a_1, a_2, \ldots, a_k )\) and \(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) We must show that \(\sigma \tau(x) = \tau \sigma(x)\) for all \(x \in X\text{.}\) If \(x\) is neither in \(\{ a_1, a_2, \ldots, a_k \}\) nor \(\{b_1, b_2, \ldots, b_l \}\text{,}\) then both \(\sigma\) and \(\tau\) fix \(x\text{.}\) That is, \(\sigma(x)=x\) and \(\tau(x)=x\text{.}\) Hence,

\begin{equation*} \sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x)\text{.} \end{equation*}

Do not forget that we are multiplying permutations right to left, which is the opposite of the order in which we usually multiply group elements. Now suppose that \(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Then \(\sigma( a_i ) = a_{(i \bmod k) + 1}\text{;}\) that is,

\begin{align*} a_1 & \mapsto a_2\\ a_2 & \mapsto a_3\\ & \vdots\\ a_{k-1} & \mapsto a_k\\ a_k & \mapsto a_1\text{.} \end{align*}

However, \(\tau(a_i) = a_i\) since \(\sigma\) and \(\tau\) are disjoint. Therefore,

\begin{align*} \sigma \tau(a_i) & = \sigma( \tau(a_i))\\ & = \sigma(a_i)\\ & = a_{(i \bmod k)+1}\\ & = \tau( a_{(i \bmod k)+1} )\\ & = \tau( \sigma(a_i) )\\ & = \tau \sigma(a_i)\text{.} \end{align*}

Similarly, if \(x \in \{b_1, b_2, \ldots, b_l \}\text{,}\) then \(\sigma\) and \(\tau\) also commute.

Proof.

We can assume that \(X = \{ 1, 2, \ldots, n \}\text{.}\) If \(\sigma \in S_n\) and we define \(X_1\) to be \(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) then the set \(X_1\) is finite since \(X\) is finite. Now let \(i\) be the first integer in \(X\) that is not in \(X_1\) and define \(X_2\) by \(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) Again, \(X_2\) is a finite set. Continuing in this manner, we can define finite disjoint sets \(X_3, X_4, \ldots\text{.}\) Since \(X\) is a finite set, we are guaranteed that this process will end and there will be only a finite number of these sets, say \(r\text{.}\) If \(\sigma_i\) is the cycle defined by

\begin{equation*} \sigma_i( x ) = \begin{cases} \sigma( x ) & x \in X_i \\ x & x \notin X_i \end{cases}\text{,} \end{equation*}

then \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\) Since the sets \(X_1, X_2, \ldots, X_r\) are disjoint, the cycles \(\sigma_1, \sigma_2, \ldots, \sigma_r\) must also be disjoint.

Example 2.56.

Let

\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 1 & 5 & 2 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 5 & 6 & 4 \end{pmatrix}\text{.} \end{align*}

Using cycle notation, we can write

\begin{align*} \sigma & = (1624)\\ \tau & = (13)(456)\\ \sigma \tau & = (1 3 6) ( 2 4 5)\\ \tau \sigma & = (1 4 3 )(2 5 6)\text{.} \end{align*}
Remark 2.57.

From this point forward we will find it convenient to use cycle notation to represent permutations. When using cycle notation, we often denote the identity permutation by \((1)\text{.}\)

Subsection 2.6.2 Transpositions

The simplest permutation is a cycle of length \(2\text{.}\) Such cycles are called transpositions. Since

\begin{equation*} (a_1, a_2, \ldots, a_n ) = (a_1 a_n ) (a_1 a_{n-1} ) \cdots ( a_1 a_3 ) (a_1 a_2 )\text{,} \end{equation*}

any cycle can be written as the product of transpositions, leading to the following proposition.

Example 2.59.

Consider the permutation

\begin{equation*} ( 1 6 ) (2 5 3) = (1 6 )( 2 3 )( 2 5 ) = (1 6 )( 4 5 )(2 3 )( 4 5 )(2 5 )\text{.} \end{equation*}

As we can see, there is no unique way to represent permutation as the product of transpositions. For instance, we can write the identity permutation as \((1 2 )(1 2 )\text{,}\) as \((1 3 )(2 4 )(1 3 )( 2 4 )\text{,}\) and in many other ways. However, as it turns out, no permutation can be written as the product of both an even number of transpositions and an odd number of transpositions. For instance, we could represent the permutation \((1 6)\) by

\begin{equation*} (2 3 )(1 6)( 2 3) \end{equation*}

or by

\begin{equation*} (3 5) (1 6) (1 3) (1 6) (1 3) (3 5) (5 6)\text{,} \end{equation*}

but \((1 6)\) will always be the product of an odd number of transpositions.

Proof.

We will employ induction on \(r\text{.}\) A transposition cannot be the identity; hence, \(r \gt 1\text{.}\) If \(r=2\text{,}\) then we are done. Suppose that \(r \gt 2\text{.}\) In this case the product of the last two transpositions, \(\tau_{r-1} \tau_r\text{,}\) must be one of the following cases:

\begin{align*} (a b)(a b) & = \identity\\ (b c)(a b) & = (a c)(b c)\\ (c d)(a b) & = (a b)(c d)\\ (a c)(a b) & = (a b)(b c)\text{,} \end{align*}

where \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\) are distinct.

The first equation simply says that a transposition is its own inverse. If this case occurs, delete \(\tau_{r-1} \tau_r\) from the product to obtain

\begin{equation*} \identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}\text{.} \end{equation*}

By induction \(r - 2\) is even; hence, \(r\) must be even.

In each of the other three cases, we can replace \(\tau_{r - 1} \tau_r\) with the right-hand side of the corresponding equation to obtain a new product of \(r\) transpositions for the identity. In this new product the last occurrence of \(a\) will be in the next-to-the-last transposition. We can continue this process with \(\tau_{r - 2} \tau_{r - 1}\) to obtain either a product of \(r - 2\) transpositions or a new product of \(r\) transpositions where the last occurrence of \(a\) is in \(\tau_{r - 2}\text{.}\) If the identity is the product of \(r - 2\) transpositions, then again we are done, by our induction hypothesis; otherwise, we will repeat the procedure with \(\tau_{r - 3} \tau_{r - 2}\text{.}\)

At some point either we will have two adjacent, identical transpositions canceling each other out or \(a\) will be shuffled so that it will appear only in the first transposition. However, the latter case cannot occur, because the identity would not fix \(a\) in this instance. Therefore, the identity permutation must be the product of \(r-2\) transpositions and, again by our induction hypothesis, we are done.

Proof.

Suppose that

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n\text{,} \end{equation*}

where \(m\) is even. We must show that \(n\) is also an even number. The inverse of \(\sigma\) is \(\sigma_m \cdots \sigma_1\text{.}\) Since

\begin{equation*} \identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1\text{,} \end{equation*}

\(n\) must be even by Lemma 2.60 . The proof for the case in which \(\sigma\) can be expressed as an odd number of transpositions is left as an exercise.

In light of Theorem 2.61 , we define a permutation to be even if it can be expressed as an even number of transpositions and odd if it can be expressed as an odd number of transpositions.

Subsection 2.6.3 The Alternating Groups

One of the most important subgroups of \(S_n\) is the set of all even permutations, \(A_n\text{.}\) The group \(A_n\) is called the alternating group on \(n\) letters.

Proof.

Since the product of two even permutations must also be an even permutation, \(A_n\) is closed. The identity is an even permutation and therefore is in \(A_n\text{.}\) If \(\sigma\) is an even permutation, then

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{,} \end{equation*}

where \(\sigma_i\) is a transposition and \(r\) is even. Since the inverse of any transposition is itself,

\begin{equation*} \sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1 \end{equation*}

is also in \(A_n\text{.}\)

Proof.

Let \(A_n\) be the set of even permutations in \(S_n\) and \(B_n\) be the set of odd permutations. If we can show that there is a bijection between these sets, they must contain the same number of elements. Fix a transposition \(\sigma\) in \(S_n\text{.}\) Since \(n \geq 2\text{,}\) such a \(\sigma\) exists. Define

\begin{equation*} \lambda_{\sigma} : A_n \rightarrow B_n \end{equation*}

by

\begin{equation*} \lambda_{\sigma} ( \tau ) = \sigma \tau \text{.} \end{equation*}

Suppose that \(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\text{.}\) Then \(\sigma \tau = \sigma \mu\) and so

\begin{equation*} \tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu\text{.} \end{equation*}

Therefore, \(\lambda_{\sigma}\) is one-to-one. We will leave the proof that \(\lambda_{\sigma}\) is surjective to the reader.

Example 2.64.

The group \(A_4\) is the subgroup of \(S_4\) consisting of even permutations. There are twelve elements in \(A_4\text{:}\)

\begin{align*} & (1) && (12)(34) && (13)(24) && (14)(23)\\ & (123) && (132) && (124) && (142)\\ & (134) && (143) && (234) && (243)\text{.} \end{align*}

One of the end-of-chapter exercises will be to write down all the subgroups of \(A_4\text{.}\) You will find that there is no subgroup of order 6. Does this surprise you?

Subsection 2.6.4 Dihedral Groups

A special type of permutation group is the dihedral group. Recall the symmetry group of an equilateral triangle in Chapter 2 . Such groups consist of the rigid motions of a regular \(n\)-sided polygon or \(n\)-gon. For \(n = 3, 4, \ldots\text{,}\) we define the nth dihedral group to be the group of rigid motions of a regular \(n\)-gon. We will denote this group by \(D_n\text{.}\) We can number the vertices of a regular \(n\)-gon by \(1, 2, \ldots, n\) ( Figure 2.65 ). Notice that there are exactly \(n\) choices to replace the first vertex. If we replace the first vertex by \(k\text{,}\) then the second vertex must be replaced either by vertex \(k+1\) or by vertex \(k-1\text{;}\) hence, there are \(2n\) possible rigid motions of the \(n\)-gon. We summarize these results in the following theorem.

An n-gon with vertex 1 at the top, followed by 2, 3, 4, ..., n - 1, n.
Figure 2.65. A regular \(n\)-gon
Proof.

The possible motions of a regular \(n\)-gon are either reflections or rotations (Figure 2.68 ). There are exactly \(n\) possible rotations:

\begin{equation*} \identity, \frac{360^{\circ} }{n}, 2 \cdot \frac{360^{\circ} }{n}, \ldots, (n-1) \cdot \frac{360^{\circ} }{n}\text{.} \end{equation*}

We will denote the rotation \(360^{\circ} /n\) by \(r\text{.}\) The rotation \(r\) generates all of the other rotations. That is,

\begin{equation*} r^k = k \cdot \frac{360^{\circ} }{n}\text{.} \end{equation*}
Rotations and reflections of an octagon. Where the top octagon (1 (top), 2, 3, 4, 5, 6, 7, 8) is rotated to an octagon (2 (top), 3, 4, 5, 6, 7, 8, 1), and the octagon below (1 (top), 2, 3, 4, 5, 6, 7, 8) is reflected about a vertical axis to (1 (top), 8, 7, 6, 5, 4, 3, 2).
Figure 2.68. Rotations and reflections of a regular \(n\)-gon

Label the \(n\) reflections \(s_1, s_2, \ldots, s_n\text{,}\) where \(s_k\) is the reflection that leaves vertex \(k\) fixed. There are two cases of reflections, depending on whether \(n\) is even or odd. If there are an even number of vertices, then two vertices are left fixed by a reflection, and \(s_1 = s_{n/2 + 1}, s_2 = s_{n/2 + 2}, \ldots, s_{n/2} = s_n\text{.}\) If there are an odd number of vertices, then only a single vertex is left fixed by a reflection and \(s_1, s_2, \ldots, s_n\) are distinct (Figure 2.69 ). In either case, the order of each \(s_k\) is two. Let \(s = s_1\text{.}\) Then \(s^2 = 1\) and \(r^n = 1\text{.}\) Since any rigid motion \(t\) of the \(n\)-gon replaces the first vertex by the vertex \(k\text{,}\) the second vertex must be replaced by either \(k+1\) or by \(k-1\text{.}\) If the second vertex is replaced by \(k+1\text{,}\) then \(t = r^k\text{.}\) If the second vertex is replaced by \(k-1\text{,}\) then \(t = r^k s\text{.}\)  1  Hence, \(r\) and \(s\) generate \(D_n\text{.}\) That is, \(D_n\) consists of all finite products of \(r\) and \(s\text{,}\)

\begin{equation*} D_n = \{1, r, r^2, \ldots, r^{n-1}, s, rs, r^2 s, \ldots, r^{n-1} s\}\text{.} \end{equation*}

We will leave the proof that \(srs = r^{-1}\) as an exercise.

Since we are in an abstract group, we will adopt the convention that group elements are multiplied left to right.
The top hexagon (1 (top), 2, 3, 4, 5, 6) is relected to (1 (top), 6, 5, 4, 3,. 2). The bottom pentqgon (1 (top), 2, 3, 4, 5) is relected to become (1 (top), 5, 4, 3, 2).
Figure 2.69. Types of reflections of a regular \(n\)-gon
Example 2.70.

The group of rigid motions of a square, \(D_4\text{,}\) consists of eight elements. With the vertices numbered \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(4\) ( Figure 2.71 ), the rotations are

\begin{align*} r & = (1234)\\ r^2 & = (13)(24)\\ r^3 & = (1432)\\ r^4 & = (1) \end{align*}

and the reflections are

\begin{align*} s_1 & = (24)\\ s_2 & = (13)\text{.} \end{align*}

The order of \(D_4\) is \(8\text{.}\) The remaining two elements are

\begin{align*} r s_1 & = (12)(34)\\ r^3 s_1 & = (14)(23)\text{.} \end{align*}
A square with diagonal lines of symmetries connecting opposite vertices, a horzontal line of symmetry that bisects the two vertical sides of the square and a vertical line of symmetry that bisects the two horizaontal sides of the square.
Figure 2.71. The group \(D_4\)
The Motion Group of a Cube.

We can investigate the groups of rigid motions of geometric objects other than a regular \(n\)-sided polygon to obtain interesting examples of permutation groups. Let us consider the group of rigid motions of a cube. By rigid motion, we mean a rotation with the axis of rotation about opposing faces, edges, or vertices. One of the first questions that we can ask about this group is “what is its order?” A cube has \(6\) sides. If a particular side is facing upward, then there are four possible rotations of the cube that will preserve the upward-facing side. Hence, the order of the group is \(6 \cdot 4 = 24\text{.}\) We have just proved the following proposition.

Proof.

From Proposition 2.72 , we already know that the motion group of the cube has \(24\) elements, the same number of elements as there are in \(S_4\text{.}\) There are exactly four diagonals in the cube. If we label these diagonals \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) and \(4\text{,}\) we must show that the motion group of the cube will give us any permutation of the diagonals (Figure 2.74 ). If we can obtain all of these permutations, then \(S_4\) and the group of rigid motions of the cube must be the same. To obtain a transposition we can rotate the cube \(180^{\circ}\) about the axis joining the midpoints of opposite edges (Figure 2.75 ). There are six such axes, giving all transpositions in \(S_4\text{.}\) Since every element in \(S_4\) is the product of a finite number of transpositions, the motion group of a cube must be \(S_4\text{.}\)

A cube where the top vetices are labled 1, 2, 3, 4 and the bottom vertices are labled 3, 4, 1, 2. Diagonals connect vertex 1 on the top with vertex 1 on the bottom, vertex 2 on the top with vertex 2 on the bottom, vertex 3 on the top with vertex 3 on the bottom, and vertex 4 on the top with vertex 4 on the bottom,
Figure 2.74. The motion group of a cube
Two cubes where the top vetices of the first cube are labled 1, 2, 3, 4 and the bottom vertices are labled 3, 4, 1, 2 and the top vertices of the second cube are labled 2, 1, 3, 4 and the bottom vertices are labled 3, 4, 2, 1. Lines of symmetry connect the 12 edge on top with the 12 edge on the bottom in both cubes.
Figure 2.75. Transpositions in the motion group of a cube

Subsection 2.6.5 Historical Note

Lagrange first thought of permutations as functions from a set to itself, but it was Cauchy who developed the basic theorems and notation for permutations. He was the first to use cycle notation. Augustin-Louis Cauchy (1789– 1857) was born in Paris at the height of the French Revolution. His family soon left Paris for the village of Arcueil to escape the Reign of Terror. One of the family's neighbors there was Pierre-Simon Laplace (1749– 1827), who encouraged him to seek a career in mathematics. Cauchy began his career as a mathematician by solving a problem in geometry given to him by Lagrange. Cauchy wrote over 800 papers on such diverse topics as differential equations, finite groups, applied mathematics, and complex analysis. He was one of the mathematicians responsible for making calculus rigorous. Perhaps more theorems and concepts in mathematics have the name Cauchy attached to them than that of any other mathematician.

Reading Questions 2.6.6 Reading Questions

1.

What is the order of the group \(S_4\text{?}\) What is the order of the group \(A_4\text{?}\) Then, give an example of an element in \(S_4\) that is not in \(A_4\text{.}\)

2.

Write the permutation \(\sigma = \begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \\ 3 \amp 2 \amp7 \amp 5 \amp 6 \amp 4 \amp 1 \end{pmatrix}\) in cycle notation.

3.

Write \(\sigma = (142)(243)\) as a single cycle or product of disjoint cycles. Then, find \(\sigma(2)\text{.}\)

4.

After reading the section, what questions do you still have? Write at least one well formulated question (even if you think you understand everything).

Exercises 2.6.7 Practice Problems

1.

Write the following permutations in cycle notation.

  1. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 5 & 1 & 3 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix} \end{equation*}
Answer

(a) \((12453)\text{;}\) (b) \((14)(35)\text{;}\) (c) \((13)(25)\text{;}\) (d) \((24)\text{.}\)

2.

Compute each of the following.

  1. \(\displaystyle (1345)(234)\)

  2. \(\displaystyle (12)(1253)\)

  3. \(\displaystyle (143)(23)(24)\)

  4. \(\displaystyle (1423)(34)(56)(1324)\)

  5. \(\displaystyle (1254)(13)(25)\)

  6. \(\displaystyle (1254) (13)(25)^2\)

  7. \(\displaystyle (1254)^{-1} (123)(45) (1254)\)

  8. \(\displaystyle (1254)^2 (123)(45)\)

  9. \(\displaystyle (123)(45) (1254)^{-2}\)

  10. \(\displaystyle (1254)^{100}\)

  11. \(\displaystyle |(1254)|\)

  12. \(\displaystyle |(1254)^2|\)

  13. \(\displaystyle (12)^{-1}\)

  14. \(\displaystyle (12537)^{-1}\)

  15. \(\displaystyle [(12)(34)(12)(47)]^{-1}\)

  16. \(\displaystyle [(1235)(467)]^{-1}\)

Answer

(a) \((135)(24)\text{;}\) (b) \((253)\text{;}\) (c) \((14)(23)\text{;}\) (d) \((12)(56)\text{;}\) (e) \((1324)\text{;}\) (f) \((13254)\text{;}\) (g) \((134)(25)\text{;}\) (h) \((14)(235)\text{;}\) (i) \((143)(25)\text{;}\) (j) \((1)\text{;}\) (k) \(4\) (i.e., the order of the element); (l) \(2\text{;}\) (m) \((12)\text{;}\) (n) \((17352)\text{;}\) (o) \((374)\text{;}\) (p) \((476)(1532)\text{.}\)

3.

Express the following permutations as products of transpositions and identify them as even or odd.

  1. \(\displaystyle (14356)\)

  2. \(\displaystyle (156)(234)\)

  3. \(\displaystyle (1426)(142)\)

  4. \(\displaystyle (17254)(1423)(154632)\)

  5. \(\displaystyle (142637)\)

Answer

(a) \((16)(15)(13)(14)\) (even); (b) \((15)(56)(23)(24)\) (even); (c) \((16)(14)(12)\) (odd); (d) \((17)(72)(25)(54)(14)(42)(23)(15)(54)(46)(63)(32)\) (even); (e) \((14)(42)(26)(63)(37)\) (odd).

5.

List all of the subgroups of \(S_4\text{.}\) Find each of the following sets:

  1. \(\displaystyle \{ \sigma \in S_4 : \sigma(1) = 3 \}\)

  2. \(\displaystyle \{ \sigma \in S_4 : \sigma(2) = 2 \}\)

  3. \(\{ \sigma \in S_4 : \sigma(1) = 3\) and \(\sigma(2) = 2 \}\text{.}\)

Are any of these sets subgroups of \(S_4\text{?}\)

Hint

(a) \(\{ (13), (13)(24), (132), (134), (1324), (1342) \}\) is not a subgroup.

(b) \(\{(1), (134), (143), (13), (14), (34)\}\) is a subgroup.

(c) \(\{(13), (134)\}\) is not a subgroup.

6.

Find all of the subgroups in \(A_4\text{.}\) What is the order of each subgroup?

Hint

There are subgroups of orders 1, 2, 3, 4, and 12. You have multiple choices for the subgroups of order 2 and 3.

7.

Find all possible orders of elements in \(S_7\) and \(A_7\text{.}\)

Answer

The possible orders in \(S_7\) are 1, 2, 3, 4, 5, 6, 7, 10, and 12. In \(A_7\) you can only have orders 1, 2, 3, 5, 6, and 7.

8.

Show that \(A_{10}\) contains an element of order \(15\text{.}\)

Hint

\((12345)(678)\text{.}\)

9.

Does \(A_8\) contain an element of order \(26\text{?}\)

Answer

No. We will give a good reason why in chapter 6.

10.

Find an element of largest order in \(S_n\) for \(n = 3, \ldots, 10\text{.}\)

Answer

\((123)\text{,}\) \((1234)\text{,}\) \((12)(345)\text{,}\) \((123456)\text{,}\) \((123)(4567)\text{,}\) \((123)(45678)\text{,}\) \((1234)(56789)\text{,}\) \((12)(345)(678910)\text{.}\)

Exercises 2.6.8 Collected Homework

C1.

Consider the group \(S_7\) and its 5040 elements. Let \(\sigma = (142376)\text{.}\)

  1. Find \(\langle \sigma \rangle\text{,}\) the cyclic subgroup of \(S_7\) generated by \(\sigma\text{.}\) (Just list out all its elements.)

  2. What is \(\sigma^{5040}\text{?}\) Justify your answer.

C2.

In the previous problem you found a cyclic subgroup of order 6 in \(S_7\text{.}\) What is the order of the largest cyclic subgroup in \(S_7\text{?}\) Is \(S_7\) itself cyclic? Explain.