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}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section5.1Definitions and Notation

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

Proof

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

Example5.2

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}. \end{align*} The following table tells us how to multiply elements in the permutation group \(G\).

\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*}

Remark5.3

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\). To compose \(\sigma\) and \(\tau\) as functions, we calculate \((\sigma \circ \tau)(x) = \sigma( \tau(x))\). That is, we do \(\tau\) first, then \(\sigma\). There are several ways to approach this inconsistency. We will adopt the convention of multiplying permutations right to left. To compute \(\sigma \tau\), do \(\tau\) first and then \(\sigma\). That is, by \(\sigma \tau (x)\) we mean \(\sigma( \tau( x))\). (Another way of solving this problem would be to write functions on the right; that is, instead of writing \(\sigma(x)\), we could write \((x)\sigma\). 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.

Example5.4

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}. \end{align*} Then \begin{equation*}\sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix},\end{equation*} but \begin{equation*}\tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}. \end{equation*}

SubsectionCycle 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\). We will write \((a_1, a_2, \ldots, a_k )\) to denote the cycle \(\sigma\). Cycles are the building blocks of all permutations.

Example5.5

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

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).\end{equation*} This permutation actually contains a cycle of length 2 and a cycle of length 4.

Example5.6

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).\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,\end{equation*} and \(\tau\) as \begin{equation*}2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2,\end{equation*} then for \(\sigma \tau\) remembering that we apply \(\tau\) first and then \(\sigma\), 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,\end{equation*} or \(\sigma \tau = (1 3 5 6 )\). If \(\mu = (1634)\), then \(\sigma \mu = (1 6 5 2)(3 4)\).

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

Example5.7

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). \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
Example5.10

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

Remark5.11

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

SubsectionTranspositions

The simplest permutation is a cycle of length 2. 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 ), \end{equation*} any cycle can be written as the product of transpositions, leading to the following proposition.

Example5.13

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 ).\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 )\), as \((1 3 )(2 4 )(1 3 )( 2 4 )\), 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),\end{equation*} but \((1 6)\) will always be the product of an odd number of transpositions.

Proof

In light of Theorem 5.15, 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.

SubsectionThe Alternating Groups

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

Proof
Example5.18

The group \(A_4\) is the subgroup of \(S_4\) consisting of even permutations. There are twelve elements in \(A_4\): \begin{align*} & (1) && (12)(34) && (13)(24) && (14)(23) \\ & (123) && (132) && (124) && (142) \\ & (134) && (143) && (234) && (243). \end{align*} One of the end-of-chapter exercises will be to write down all the subgroups of \(A_4\). You will find that there is no subgroup of order 6. Does this surprise you?

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