## Section 10.2 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. Plus, as we have just seen, every group is isomorphic to a subgroup of a permutation group. So let's study them.

In general, the permutations of a set \(X\) form a group we call \(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.

###### Theorem 10.3.

The symmetric group on \(n\) letters, \(S_n\text{,}\) is a group with \(n!\) elements, where the binary operation is the composition of maps.

###### 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 10.4.

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

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

###### Remark 10.5.

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 10.6.

Permutation multiplication is not usually commutative. Let

Then

but

### Subsection 10.2.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

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 10.7.

The permutation

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

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

Not every permutation is a cycle. Consider the permutation

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

###### Example 10.8.

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

If we think of \(\sigma\) as

and \(\tau\) as

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

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 10.9.

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

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

###### Proposition 10.10.

Let \(\sigma\) and \(\tau\) be two disjoint cycles in \(S_X\text{.}\) Then \(\sigma \tau = \tau \sigma\text{.}\)

###### 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,

*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,

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

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

###### Theorem 10.11.

Every permutation in \(S_n\) can be written as the product of disjoint cycles.

###### 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

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 10.12.

Let

Using cycle notation, we can write

###### Remark 10.13.

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{.}\)

### Worksheet 10.2.2 Activity: Writing Cycles and Permutations

Goal: Understand how elements of \(S_n\) can be represented as cycles and products of cycles.

###### 1.

Can every permutation in \(S_n\) be represented using cycle notation? How could you represent the permutation \(\begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8 \amp 9 \\ 3 \amp 5 \amp 2 \amp 8 \amp 7 \amp 9 \amp 6 \amp 1 \amp 4 \end{pmatrix}\text{?}\)

###### 2.

How should we define “cycle”? Write a definition. Some considerations: is \((132)(45)\) a single cycle or two cycles? Is \((3124)\) a cycle? What should we call the length of a cycle?

###### 3.

Here are a few permutations of \(S_7\text{,}\) written as products of cycles. Are there other ways to write each of these using cycle notation? What makes two products of cycles the *same*?

A *transposition* (or \(2\)-cycle) is a cycle of *length* 2. That is, it swaps (transposes) a pair of elements.

###### 4.

Can the cycle \((13254)\) be written as the product of transpositions? Can it be written as the product of transpositions in more than one way?

###### 5.

What about the product \((124)(2354)\text{?}\)

###### 6.

Can you write \((13)(24)(45)(15)(26)(13)\) as the product of more than 6 transpositions? Fewer than 6 transpositions? Can you write it as the product of an odd number of transpositions?

###### 7.

What numbers of transpositions can you write the identity \((1)\) as?

### Subsection 10.2.3 Transpositions

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

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

###### Proposition 10.14.

Any permutation of a finite set containing at least two elements can be written as the product of transpositions.

###### Example 10.15.

Consider the permutation

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

or by

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

###### Lemma 10.16.

If the identity is written as the product of \(r\) transpositions,

then \(r\) is an even number.

###### 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:

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

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.

###### Theorem 10.17.

If a permutation \(\sigma\) can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling \(\sigma\) must also contain an even number of transpositions. Similarly, if \(\sigma\) can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling \(\sigma\) must also contain an odd number of transpositions.

###### Proof.

Suppose that

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

\(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 10.2.4 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.

###### Theorem 10.18.

The set \(A_n\) is a subgroup of \(S_n\text{.}\)

###### 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

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

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

###### Proposition 10.19.

The number of even permutations in \(S_n\text{,}\) \(n \geq 2\text{,}\) is equal to the number of odd permutations; hence, the order of \(A_n\) is \(n!/2\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

by

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

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

###### Example 10.20.

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

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 10.2.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.

### Exercises 10.2.6 Practice Problems

###### 1.

Write the following permutations in cycle notation.

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

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

###### 2.

Compute each of the following.

\(\displaystyle (1345)(234)\)

\(\displaystyle (12)(1253)\)

\(\displaystyle (143)(23)(24)\)

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

\(\displaystyle (1254)(13)(25)\)

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

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

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

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

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

\(\displaystyle |(1254)|\)

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

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

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

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

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

(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.

\(\displaystyle (14356)\)

\(\displaystyle (156)(234)\)

\(\displaystyle (1426)(142)\)

\(\displaystyle (17254)(1423)(154632)\)

\(\displaystyle (142637)\)

(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:

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

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

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

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

(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?

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{.}\)

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{.}\)

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

###### 9.

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

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{.}\)

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

### Exercises 10.2.7 Collected Homework

###### 1.

The identity can be written as \(\varepsilon = (13)(24)(35)(14)(12)(15)(34)(45)\text{.}\) Mimic the proof that \(\varepsilon\) must be even and show how to eliminate \(x = 5\) from the product of transpositions and write \(\varepsilon\) as the product of 2 fewer transpositions in the process. Show all intermediate steps.

###### 2.

Bonus: One way you could prove that \(|A_n| = \frac{n!}{2}\) is to show that \(S_n\) has an equal number of even permutations as odd permutations. One way you could do this is by finding a bijection from the set of even permutations to the set of odd permutations. Define \(f:A_n \to \overline{A_n}\) (here \(\overline{A_n}\) is the compliment of \(A_n\text{,}\) so the set of all odd permutations) by \(f(\tau) = (12)\tau\text{.}\)

Prove that \(f\) really is a bijection. Careful: there are multiple ways to write permutations as products of transpositions.