15.2: Permutation Groups

Last updated
Save as PDF

Page ID: 97964

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Entire books have been written on the theory of the mathematical structures known as groups. However, our study of Pólya's enumeration theorem requires only a few facts about a particular class of groups that we introduce in this section. First, recall that a bijection from a set \(X\) to itself is called a permutation. A permutation group is a set \(P\) of permutations of a set \(X\) so that

the identity permutation \(ι\) is in \(P\);
if \(\pi_1,\pi_2 \in P\), then \(\pi_2 \circ \pi_1 \in P\); and
if \(\pi_1 \in P\), then \(\pi_1^{-1} \in P\).

For our purposes, \(X\) will always be finite and we will usually take \(X=[n]\) for some positive integer \(n\). The symmetric group on \(n\) elements, denoted \(S_n\), is the set of all permutations of \([n]\). Every finite permutation group (and more generally every finite group) is a subgroup of \(S_n\) for some positive integer \(n\).

As our first example of a permutation group, consider the set of permutations we discussed in Section 15.1, called the dihedral group of the square. We will denote this group by \(D_8\). We denote by \(D_{2n}\) the similar group of transformations for a regular \(n\)-gon, using \(2n\) as the subscript because there are \(2n\) permutations in this group. The first criterion to be a permutation group is clearly satisfied by \(D_8\). Verifying the other two is quite tedious, so we only present a couple of examples. First, notice that \(r_2 \circ r_1=r_3\). This can be determined by carrying out the composition of these functions as permutations or by noting that rotating \(90^\circ\) clockwise and then \(180^\circ\) clockwise is the same as rotating \(270^\circ\) clockwise. For \(v \circ r\), we find \(v \circ r(1)=1, v \circ r(3)=3, v \circ r(2)=4\), and \(v \circ r(4)=2\), so \(v \circ r=n\). For inverses, we have already discussed that \(r_1^{−1}=r_3\). Also, \(v^{−1}=v\), and more generally, the inverse of any flip is that same flip.

15.2.1 Representing permutations

The way a permutation rearranges the elements of \(X\) is central to Pólya's enumeration theorem. A proper choice of representation for a permutation is very important here, so let's discuss how permutations can be represented. One way to represent a permutation \(\pi\) of \([n]\) is as a \(2 \times n\) matrix in which the first row represents the domain and the second row represents \(\pi\) by putting \(\pi(i)\) in position \(i\). For example,