6.1: Introduction to Permutation Groups

Definition: Permutation

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

Example \(\PageIndex{1}\)

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

Definition: Permutation Multiplication

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

Note

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!)

Example \(\PageIndex{2}\)

Let \(A\text{,}\) \(\sigma\text{,}\) and \(\tau\) be as in Example \(6.1.1\). 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*}

Definition

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

Theorem \(\PageIndex{1}\)

Given a set \(A\text{:}\)

1. \(S_A\) is a group under permutation multiplication.

2. If \(A\) has finite cardinality \(n\text{,}\) then \(|S_A|=n!\) (if \(|A|=\infty\) then \(|S_A|\) is also \(\infty\)).

3. \(S_A\) is abelian if \(|A|=1\) or \(2\text{,}\) and nonabelian otherwise.

Proof

1. Let \(σ,τ∈S_A\). Since a composition of bijections is a bijection (see Theorem \(1.2.3\)), \(στ\) is a bijection from \(A\) to \(A\), hence is in \(S_A\). So \(\langle S_A, \circ \rangle\) is a binary structure

Next, function composition is always associative.

The identity function \(1_A:A→A\) defined by

\(1_A(a)=a \text{ for all } a∈A\)

clearly acts as an identity element in \(S_A\). Henceforth, we will denote \(1_A\) by \(e\).

Finally, let \(σ∈S_A\). Since \(σ\) is a bijection, \(σ\) has an inverse function \(σ^{−1}\) that is also a bijection from \(A\) to \(A\) (Theorem \(1.2.1\)). Since \(σ^{−1}∈S_A\) with \(σσ^{−1}=σ^{−1}σ=1_A\), every element of \(S_A\) has an inverse element in \(S_A\).

So \(S_A\) is a group.

2. Clearly \(|S_A|=∞\) when \(|A|=∞\), and a straightforward combinatorial argument yields that when \(|A|=n∈\mathbb{Z}^+\), we have \(|S_A|=n!\).

3. Finally, if \(|A|=1\) or \(2\), then \(|S_A|=1!=1\) or \(|S_A|=2!=2\) so \(S_A\) must be abelian (as it's a group of order \(1\) or \(2\)). On the other hand, suppose \(|A|>2\). Then \(A\) contains at least three distinct elements, say \(x\), \(y\), and \(z\). Let \(σ\) be the permutation of \(A\) swapping \(x\) and \(y\) and fixing every other element of \(A\), and let \(τ\) be the permutation of \(A\) swapping \(y\) and \(z\) and fixing every other element of \(A\). Then \(στ(x)=y\) while \(τσ(x)=z\), so \(στ≠τσ\), and hence \(S_A\) is nonabelian.

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

Definition: Permutation Group

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

Remark

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 \mathbb{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 \mathbb{Z}^+\)).