Introduction to permutation groups

Definition6.1.1

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

Example6.1.2

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

Definition6.1.3

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

Warning6.1.4

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

Example6.1.5

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

Definition6.1.6

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

Theorem6.1.7

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

\(S_A\) is a group under permutation multiplication.
If \(A\) has finite cardinality \(n\text{,}\) then \(|S_A|=n!\) (if \(|A|=\infty\) then \(|S_A|\) is also \(\infty\)).
\(S_A\) is abelian if \(|A|=1\) or \(2\text{,}\) and nonabelian otherwise.

Let \(\sigma, \tau \in S_A\text{.}\) Since a composition of bijections is a bijection (see Theorem 1.2.11), \(\sigma \tau\) is a bijection from \(A\) to \(A\text{,}\) hence is in \(S_A\text{.}\) So \(\langle S_A,\circ\rangle\) is a binary structure

Next, function composition is always associative.

The identity function \(1_A : A\to A\) defined by
\begin{equation*} 1_A(a)=a \text{ for all \(a\in A\)} \end{equation*}
clearly acts as an identity element in \(S_A\text{.}\) Henceforth, we will denote \(1_A\) by \(e\text{.}\)

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

So \(S_A\) is a group.
Clearly \(|S_A|=\infty\) when \(|A|=\infty\text{,}\) and a straightforward combinatorial argument yields that when \(|A|=n \in \Z^+\text{,}\) we have \(|S_A|=n!\text{.}\)
Finally, if \(|A|=1\) or \(2\text{,}\) 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\text{.}\) Then \(A\) contains at least three distinct elements, say \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) Let \(\sigma\) be the permutation of \(A\) swapping \(x\) and \(y\) and fixing every other element of \(A\text{,}\) and let \(\tau\) be the permutation of \(A\) swapping \(y\) and \(z\) and fixing every other element of \(A\text{.}\) Then \(\sigma \tau(x)=y\) while \(\tau \sigma(x)=z\text{,}\) so \(\sigma \tau \neq \tau \sigma\text{,}\) and hence \(S_A\) is nonabelian.

Definition6.1.8

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

Remark6.1.9

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

First-Semester Abstract AlgebraA Structural Approach

Section6.1Introduction to permutation groups¶ permalink