Skip to main content
\(\def\Z{\mathbb{Z}} \def\zn{\mathbb{Z}_n} \def\znc{\mathbb{Z}_n^\times} \def\R{\mathbb{R}} \def\Q{\mathbb{Q}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\M{\mathbb{M}} \def\G{\mathcal{G}} \def\0{\mathbf 0} \def\Gdot{\langle G, \cdot\,\rangle} \def\phibar{\overline{\phi}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Ker}{Ker} \def\siml{\sim_L} \def\simr{\sim_R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section6.1Introduction to permutation groups


A permutation on a set \(A\) is a bijection from \(A\) to \(A\text{.}\) We say a permutation \(\sigma\) on \(A\) fixes \(a\in A\) if \(\sigma(a)=a\text{.}\)


Let \(A\) be the set \(A=\{\Delta, \star, 4\}\text{.}\) Then the functions \(\sigma : A\to A\) defined by

\begin{equation*} \sigma(\Delta)=\star, \sigma(\star)=\Delta, \text{and } \sigma(4)=4; \end{equation*}

and \(\tau : A\to A\) defined by

\begin{equation*} \tau(\Delta)=4, \tau(\star)=\Delta, \text{and } \tau(4)=\star \end{equation*}

are both permutations on \(A\text{.}\)


Composition of permutations on a set \(A\) is often called permutation multiplication, and if \(\sigma\) and \(\tau\) are permutations on a set \(A\text{,}\) we usually omit the composition symbol and write \(\sigma \circ \tau\) simply as \(\sigma \tau\text{.}\)


For us, if \(\sigma\) and \(\tau\) are permutations on a set \(A\text{,}\) then applying \(\sigma \tau\) to \(A\) means first applying \(\tau\) and then applying \(\sigma\text{.}\) This is due to the conventional right-to-left reading of function compositions.

That is, if \(a\in A\text{,}\) by \(\sigma \tau(a)\) we mean \(\sigma(\tau(a))\text{.}\) (Some other books/mathematicians do not use this convention, and read permutation multiplication from left-to-right. Make sure to always know what convention your particular author or colleague is using!)


Let \(A\text{,}\) \(\sigma\text{,}\) and \(\tau\) be as in Example 6.1.2. Then \(\sigma \tau\) is the function from \(A\) to \(A\) defined by

\begin{equation*} \sigma \tau(\Delta)=4, \sigma \tau(\star)=\star, \text{and } \sigma \tau(4)=\Delta, \end{equation*}

while \(\tau \sigma\) is the function from \(A\) to \(A\) defined by

\begin{equation*} \tau \sigma (\Delta)=\Delta, \tau \sigma (\star)=4, \text{and } \tau \sigma(4)=\star \end{equation*}

Given a set \(A\text{,}\) we define \(S_A\) to be the set of all permutations on \(A\text{.}\)


We will in the future use language provided by the following definition:


A group is said to be a permutation group if it is a subgroup of \(S_A\) for some set \(A\text{.}\)


Notice that if \(A\) and \(B\) are sets, then \(|A|=|B|\) if and only if \(S_A\simeq S_B\text{.}\)

Thus, for any set \(B\) with \(|B|=n \in \Z^+\text{,}\) we have \(S_B\simeq S_A\text{,}\) where \(A=\{1,2,\ldots,n\}\text{.}\) Since we are concerned in this course primarily with group structures which are invariant under isomorphism, we may focus now on groups of permutations on the set \(\{1,2,\ldots, n\}\) (\(n\in \Z^+\)).