Permutation Groups

For any finite non-empty set S, A(S) the set of all 1-1 transformations (mapping) of S onto S forms a group called Permutation group and any element of A(S) i.e., a mapping from S onto itself is called Permutation.

Symmetric groups

Theorem 1: Let ${\displaystyle A}$ be any set. Then, the set ${\displaystyle S_{A}}$ of bijections from ${\displaystyle A}$ to itself, ${\displaystyle f\,:,A\rightarrow A}$, form a group under composition of functions.

Proof: We have to verify the group axioms. Associativity is fulfilled since composition of functions is always associative: ${\displaystyle (f\circ g)\circ h(x)=f\circ g(h(x))=f(g(h(x)))=f(g\circ h(x))=f\circ (g\circ h)(x)}$ where the composition is defined. The identity element is the identity function given by ${\displaystyle \mathrm {id} _{A}(a)=a}$ for all ${\displaystyle a\in A}$. Finally, the inverse of a function ${\displaystyle f}$ is the function ${\displaystyle f^{-1}}$ taking ${\displaystyle f(a)}$ to ${\displaystyle a}$ for all ${\displaystyle a\in A}$. This function exists and is unique since ${\displaystyle f}$ is a bijection. Thus ${\displaystyle S_{A}}$ is a group, as stated. ∎

${\displaystyle S_{A}}$ is called the symmetric group on ${\displaystyle A}$. When ${\displaystyle A=\{1,2,...,n\}\,,\,n\in \mathbb {N} }$, we write its symmetric group as ${\displaystyle S_{n}}$, and we call this group the symmetric group on ${\displaystyle n}$ letters. It is also called the group of permutations on ${\displaystyle n}$ letters. As we will see shortly, this is an appropriate name.

Instead of ${\displaystyle e}$, we will use a different symbol, namely ${\displaystyle \iota }$, for the identity function in ${\displaystyle S_{n}}$.

When ${\displaystyle \sigma \in S_{n}}$, we can specify ${\displaystyle \sigma }$ by specifying where it sends each element. There are many ways to encode this information mathematically. One obvious way is to identify ${\displaystyle \sigma }$ as the unique ${\displaystyle n\times n}$ matrix with value ${\displaystyle 1}$ in the entries ${\displaystyle (i,\sigma (i))}$ and ${\displaystyle 0}$ elsewhere. Composition of functions then corresponds to multiplication of matrices. Indeed, the matrix corresponding to ${\displaystyle \rho }$ has value ${\displaystyle 1}$ in the entries ${\displaystyle (i,\rho (i))}$, which is the same as ${\displaystyle (\sigma (j),\rho (\sigma (j)))}$, so the product has value ${\displaystyle 1}$ in the entries ${\displaystyle (j,\rho (\sigma (j)))}$. This notation may seem cumbersome. Luckily, there exists a more convenient notation, which we will make use of.

We can represent any ${\displaystyle \sigma \in S_{n}}$ by a ${\displaystyle 2\times n}$ matrix ${\displaystyle \left({\begin{array}{cccc}1&2&\dots &n\\\sigma (1)&\sigma (2)&\dots &\sigma (n)\end{array}}\right)}$. We obviously lose the correspondence between function composition and matrix multiplication, but we gain a more readable notation. For the time being, we will use this.

Remark 2: Let ${\displaystyle \sigma ,\rho \in S_{n}}$. Then the product ${\displaystyle \sigma \rho \equiv \sigma \circ \rho }$ is the function obtained by first acting with ${\displaystyle \rho }$, and then by ${\displaystyle \sigma }$. That is, ${\displaystyle \sigma \rho (x)=\sigma (\rho (x))}$. This point is important to keep in mind when computing products in ${\displaystyle S_{n}}$. Some textbooks try to remedy the frequent confusion by writing functions like ${\displaystyle (x)\rho \sigma }$, that is, writing arguments on the left of functions. We will not do this, as it is not standard. The reader should use the next example and theorem to get a feeling for products in ${\displaystyle S_{n}}$.

Example 3: We will show the multiplication table for ${\displaystyle S_{3}}$. We introduce the special notation for ${\displaystyle S_{3}}$: ${\displaystyle \iota =\rho _{0}}$, ${\displaystyle \rho _{1}=\left({\begin{array}{ccc}1&2&3\\2&3&1\end{array}}\right)}$, ${\displaystyle \rho _{2}=\left({\begin{array}{ccc}1&2&3\\3&1&2\end{array}}\right)}$, ${\displaystyle \mu _{1}=\left({\begin{array}{ccc}1&2&3\\1&3&2\end{array}}\right)}$, ${\displaystyle \mu _{2}=\left({\begin{array}{ccc}1&2&3\\3&2&1\end{array}}\right)}$ and ${\displaystyle \mu _{3}=\left({\begin{array}{ccc}1&2&3\\2&1&3\end{array}}\right)}$. The multiplication table for ${\displaystyle S_{3}}$ is then

${\displaystyle {\begin{array}{c|cccccc}\circ &\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\hline \rho _{0}&\rho _{0}&\rho _{1}&\rho _{2}&\mu _{1}&\mu _{2}&\mu _{3}\\\rho _{1}&\rho _{1}&\rho _{2}&\rho _{0}&\mu _{3}&\mu _{1}&\mu _{2}\\\rho _{2}&\rho _{2}&\rho _{0}&\rho _{1}&\mu _{2}&\mu _{3}&\mu _{1}\\\mu _{1}&\mu _{1}&\mu _{2}&\mu _{3}&\rho _{0}&\rho _{2}&\rho _{1}\\\mu _{2}&\mu _{2}&\mu _{3}&\mu _{1}&\rho _{1}&\rho _{0}&\rho _{2}\\\mu _{3}&\mu _{3}&\mu _{1}&\mu _{2}&\rho _{2}&\rho _{1}&\rho _{0}\end{array}}}$

Theorem 4: ${\displaystyle S_{n}}$ has order ${\displaystyle n!}$.

Proof: This follows from a counting argument. We can specify a unique element in ${\displaystyle S_{n}}$ by specifying where each ${\displaystyle i\in \{1,2,...,n\}}$ is sent. Also, any permutation can be specified this way. Let ${\displaystyle \sigma \in S_{n}}$. In choosing ${\displaystyle \sigma (1)}$ we are completely free and have ${\displaystyle n}$ choices. Then, when choosing ${\displaystyle \sigma (2)}$ we must choose from ${\displaystyle \{1,...,n\}-\{\sigma (1)\}}$, giving a total of ${\displaystyle n-1}$ choices. Continuing in this fashion, we see that for ${\displaystyle \sigma (i)}$ we must choose from ${\displaystyle \{1,...,n\}-\{\sigma (1),...,\sigma (i-1)\}}$, giving a total of ${\displaystyle n+1-i}$ choices. The total number of ways in which we can specify an element, and thus the number of elements in ${\displaystyle S_{n}}$ is then ${\displaystyle |S_{n}|=\prod _{i=1}^{n}(n+1-i)=n(n-1)...\cdot 2\cdot 1=n!}$, as was to be shown. ∎

Theorem 5: ${\displaystyle S_{n}}$ is non-abelian for all ${\displaystyle n\geq 3}$.

Proof: Let ${\displaystyle \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&1&3&\dots &n\end{array}}\right)}$ be the function only interchanging 1 and 2, and ${\displaystyle \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\1&3&2&\dots &n\end{array}}\right)}$ be the function only interchanging 2 and 3. Then ${\displaystyle \sigma \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&3&1&\dots &n\end{array}}\right)}$ and ${\displaystyle \rho \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\3&1&2&\dots &n\end{array}}\right)}$. Since ${\displaystyle \sigma \rho \neq \rho \sigma }$, ${\displaystyle S_{n}}$ is not abelian. ∎

Definition 6: Let ${\displaystyle \sigma \in S_{n}}$ such that ${\displaystyle \sigma ^{k}=\iota }$ for some ${\displaystyle k\in \mathbb {Z} }$. Then ${\displaystyle \sigma }$ is called an ${\displaystyle k}$-cycle, where ${\displaystyle k}$ is the smallest positive such integer. Let ${\displaystyle \sigma ^{*}}$ be the set of integers ${\displaystyle a}$ such that ${\displaystyle \sigma (a)\neq a}$. Two cycles ${\displaystyle \sigma ,\rho }$ are called disjoint if ${\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset }$. Also, a 2-cycle is called a transposition.

Remark 3: It's important to realize that if ${\displaystyle a\in \sigma ^{*}}$, then so is ${\displaystyle \sigma (a)}$. If ${\displaystyle \sigma (a)=b\neq a}$, then if ${\displaystyle \sigma (b)=b}$ we have that ${\displaystyle \sigma }$ is not 1–1.

Theorem 7: Let ${\displaystyle \sigma ,\rho \in S_{n}}$. If ${\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset }$, then ${\displaystyle \sigma \rho =\rho \sigma }$.

Proof: For any integer ${\displaystyle 1\leq a\leq n}$ such that ${\displaystyle a\in \sigma ^{*}}$ but ${\displaystyle a\not \in \rho ^{*}}$ we have ${\displaystyle \sigma \rho (a)=\sigma (\iota (a))=\sigma (a)=\iota (\sigma (a))=\rho (\sigma (a))=\rho \sigma (a)}$. A similar argument holds for ${\displaystyle a\in \rho ^{*}}$ but ${\displaystyle a\not \in \sigma ^{*}}$. If ${\displaystyle a\not \in \sigma ^{*}\cup \rho ^{*}}$, we must have ${\displaystyle \sigma \rho (a)=\sigma (a)=a=\rho (a)=\rho \sigma (a)}$. Since ${\displaystyle \sigma ^{*}\cap \rho ^{*}=\emptyset }$, we have now exhausted every ${\displaystyle a\in \{1,...,n\}}$, and we are done. ∎

Theorem 8: Any permutation can be represented as a composition of disjoint cycles.

Proof: Let ${\displaystyle \sigma \in S_{n}}$. Choose an element ${\displaystyle a\in \sigma ^{*}}$ and compute ${\displaystyle \sigma (a),\sigma ^{2}(a),...,\sigma ^{k}(a)=a}$. Since ${\displaystyle S_{n}}$ is finite of order ${\displaystyle n!}$, we know that ${\displaystyle k}$ exists and ${\displaystyle k\leq n!}$. We have now found a ${\displaystyle k}$-cycle ${\displaystyle \sigma _{1}}$ including ${\displaystyle a}$. Since ${\displaystyle \sigma _{1}^{*}=\{a,\sigma (a),...,\sigma ^{k-1}(a)\}}$, this cycle may be factored out from ${\displaystyle \sigma }$ to obtain ${\displaystyle \sigma =\sigma _{1}\sigma ^{\prime }}$. Repeat this process, which terminates since ${\displaystyle \sigma ^{*}}$ is finite, and we have constructed a composition of disjoint cycles that equals ${\displaystyle \sigma }$. ∎

Now that we have shown that all permuations are just compositions of disjoint cycles, we can introduce the ultimate shorthand notation for permutations. For an ${\displaystyle n}$-cycle ${\displaystyle \sigma }$, we can show its action by choosing any element ${\displaystyle a\in \sigma ^{*}}$ and writing ${\displaystyle \sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)}$.

Theorem 9: Any ${\displaystyle n}$-cycle can be represented as a composition of transpositions.

Proof: Let ${\displaystyle \sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)}$. Then, ${\displaystyle \sigma =\left(a\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)\left(a\ \sigma (a)\right)}$ (check this!), omitting the composition sign ${\displaystyle \circ }$. Interate this process to obtain ${\displaystyle \sigma =\left(a\ \sigma ^{n-1}(a)\right)...\left(a\ \sigma ^{2}(a)\right)\left(a\ \sigma (a)\right)}$. ∎

Note 10: This way of representing ${\displaystyle \sigma }$ as a product of transpositions is not unique. However, as we will see now, the "parity" of such a representation is well defined.

Definition 11: The parity of a permutation is even if it can be expressed as a product of an even number of transpositions. Otherwise, it is odd. We define the function ${\displaystyle \operatorname {sgn}(\sigma )=1}$ if ${\displaystyle \sigma }$ is even and ${\displaystyle \operatorname {sgn}(\sigma )=-1}$ if ${\displaystyle \sigma }$ is odd.

Lemma 12: The identity ${\displaystyle \iota }$ has even parity.

Proof: Observe first that ${\displaystyle \iota \neq (a\ b)}$ for ${\displaystyle a\neq b}$. Thus the minimum number of transpositions necessary to represent ${\displaystyle \iota }$ is 2: ${\displaystyle \iota =(a\ b)(a\ b)}$. Now, assume that for any representation using less than ${\displaystyle k}$ transpositions must be even. Thus, let ${\displaystyle \iota =(a_{1}\ b_{1})...(a_{k}\ b_{k})}$. Now, since in particular ${\displaystyle \iota (a_{1})=a_{1}}$, we must have ${\displaystyle a_{1}\in (a_{i}\ b_{i})^{*}}$ for some ${\displaystyle 1<i\leq k}$. Since disjoint transpositions commute, and ${\displaystyle (a_{r}\ a_{s})(a_{i}\ a_{r})=(a_{i}\ a_{s})(a_{r}\ a_{s})}$ where ${\displaystyle a_{i}\neq a_{r}\neq a_{s}}$, it is always possible to configure the transpositions such that the first two transpositions are either ${\displaystyle (a_{1}\ b_{1})(a_{1}\ b_{1})=\iota }$, reducing the number of transposition by two, or ${\displaystyle (a_{1}\ b_{1})(a_{1}\ b_{2})=(a_{1}\ b_{2})(b_{1}\ b_{2})}$. In this case we have reduced the number of transpositions involving ${\displaystyle a_{1}}$ by 1. We restart the same process as above. with the new representation. Since only a finite number of transpositions move ${\displaystyle a_{1}}$, we will eventually be able to cancel two permutations and be left with ${\displaystyle k-2}$ transpositions in the product. Then, by the induction hypothesis, ${\displaystyle k-2}$ must be even and so ${\displaystyle k}$ is even as well, proving the lemma. ∎

Theorem 13: The parity of a permutation, and thus the ${\displaystyle \operatorname {sgn} }$ function, is well-defined.

Proof: Let ${\displaystyle \sigma \in S_{n}}$ and write ${\displaystyle \sigma }$ as a product of transposition in two different ways: ${\displaystyle \sigma =\tau _{1}...\tau _{k}=\tau _{1}^{\prime }...\tau _{k^{\prime }}^{\prime }}$. Then, since ${\displaystyle \iota }$ has even parity by Lemma 11 and ${\displaystyle \iota =\sigma \sigma ^{-1}=\tau _{1}...\tau _{k}\tau _{k^{\prime }}^{\prime }...\tau _{1}^{\prime }}$. Thus, ${\displaystyle k+k^{\prime }\equiv 0\ \mathrm {mod} \ 2}$, and ${\displaystyle k\equiv k^{\prime }\ \mathrm {mod} \ 2}$, so ${\displaystyle \sigma }$ has a uniquely defined parity, and consequentially ${\displaystyle \operatorname {sgn} }$ is well-defined. ∎

Theorem 14: Let ${\displaystyle \sigma ,\rho \in S_{n}}$. Then, ${\displaystyle \operatorname {sgn}(\sigma \rho )=\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )}$.

Proof: Decompose ${\displaystyle \sigma }$ and ${\displaystyle \rho }$ into transpositions: ${\displaystyle \sigma =\mu _{1}...\mu _{k}}$, ${\displaystyle \rho =\nu _{1}...\nu _{l}}$. Then ${\displaystyle \sigma \rho =\mu _{1}...\mu _{k}\nu _{1}...\nu _{l}}$ has parity given by ${\displaystyle k+l}$. If both are even or odd, ${\displaystyle k+l}$ is even and indeed ${\displaystyle \operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=1\cdot 1=1=\operatorname {sgn}(\sigma \rho )}$. If one is odd and one is even, ${\displaystyle k+l}$ is odd and again ${\displaystyle \operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=(-1)\cdot 1=-1=\operatorname {sgn}(\sigma \rho )}$, proving the theorem. ∎

Lemma 15: The number of even permutations in ${\displaystyle S_{n}}$ equals the number of odd permutations.

Proof: Let ${\displaystyle \sigma }$ be any even permutation and ${\displaystyle \tau }$ a transposition. Then ${\displaystyle \tau \sigma }$ has odd parity by Theorem 14. Let ${\displaystyle E}$ be the set of even permutations and ${\displaystyle O}$ the set of odd permutations. Then the function ${\displaystyle f:E\rightarrow O}$ given by ${\displaystyle f(\sigma )=\tau \sigma }$ for any ${\displaystyle \sigma \in E}$ and a fixed transposition ${\displaystyle \tau }$, is a bijection. (Indeed, it is a transposition in ${\displaystyle S_{S_{n}}}$!) Thus ${\displaystyle E}$ and ${\displaystyle O}$ have the same number of elements, as stated. ∎

Definition 16: Let the set of all even permutations in ${\displaystyle S_{n}}$ be denoted by ${\displaystyle A_{n}}$. ${\displaystyle A_{n}}$ is called the alternating group on ${\displaystyle n}$ letters.

Theorem 17: ${\displaystyle A_{n}}$ is a group, and is a subgroup of ${\displaystyle S_{n}}$ of order ${\displaystyle {\frac {n!}{2}}}$.

Proof: We first show that ${\displaystyle A_{n}}$ is a group under composition. Then it is automatically a subgroup of ${\displaystyle S_{n}}$. That ${\displaystyle A_{n}}$ is closed under composition follows from Theorem 14 and associativity is inherited from ${\displaystyle S_{n}}$. Also, the identity permutation is even, so ${\displaystyle \iota \in A_{n}}$. Thus ${\displaystyle A_{n}}$ is a group and a subgroup of ${\displaystyle S_{n}}$. Since the number of even and odd permutations are equal by Lemma 14, we then have that ${\displaystyle |A_{n}|={\frac {|S_{n}|}{2}}={\frac {n!}{2}}}$, proving the theorem. ∎

Theorem 18: Let ${\displaystyle n\geq 3}$. Then ${\displaystyle A_{n}}$ is generated by the 3-cycles in ${\displaystyle S_{n}}$.

Proof: We must show that any even permutation can be decomposed into 3-cycles. It is sufficient to show that this is the case for pairs of transpositions. Let ${\displaystyle a,b,c,d\in S_{n}}$ be distinct. Then, by some casework,

i) ${\displaystyle (a\ b)(a\ b)=(a\ b\ c)^{3}}$,

ii) ${\displaystyle (a\ b)(b\ c)=(c\ a\ b)}$, and

iii) ${\displaystyle (a\ b)(c\ d)=(a\ d\ c)(a\ b\ c)}$,

proving the theorem. ∎

In a previous section we proved Lagrange's Theorem: The order of any subgroup divides the order of the parent group. However, the converse statement, that a group has a subgroup for every divisor of its order, is false! The smallest group providing a counterexample is the alternating group ${\displaystyle A_{4}}$, which has order 12 but no subgroup of order 6. It has subgroups of orders 3 and 4, corresponding respectively to the cyclic group of order 3 and the Klein 4-group. However, if we add any other element to the subgroup corresponding to ${\displaystyle C_{3}}$, it generates the whole group ${\displaystyle A_{4}}$. We leave it to the reader to show this.

Dihedral Groups

The dihedral groups are the symmetry groups of regular polygons. As such, they are subgroups of the symmetric groups. In general, a regular ${\displaystyle n}$-gon has ${\displaystyle n}$ rotational symmetries and ${\displaystyle n}$ reflection symmetries. The dihedral groups capture these by consisting of the associated rotations and reflections.

Definition 19: The dihedral group of order ${\displaystyle 2n}$, denoted ${\displaystyle D_{2n}}$, is the group of rotations and reflections of a regular ${\displaystyle n}$-gon.

Theorem 20: The order of ${\displaystyle D_{2n}}$ is precisely ${\displaystyle 2n}$.

Proof: Let ${\displaystyle \rho }$ be a rotation that generates a subgroup of order ${\displaystyle n}$ in ${\displaystyle D_{2n}}$. Obviously, ${\displaystyle \langle \rho \rangle }$ then captures all the pure rotations of a regular ${\displaystyle n}$-gon. Now let ${\displaystyle \mu }$ be any rotation in The rest of the elements can then be found by composing each element in ${\displaystyle \langle \rho \rangle }$ with ${\displaystyle \mu }$. We get a list of elements ${\displaystyle D_{2n}=\{\iota ,\rho ,...,\rho ^{n-1},\mu ,\mu \rho ,...,\mu \rho ^{n-1}\}}$. Thus, the order of ${\displaystyle D_{2n}}$ is ${\displaystyle 2n}$, justifying its notation and proving the theorem. ∎

Remark 21: From this proof we can also see that ${\displaystyle \{\rho ,\mu \}}$ is a generating set for ${\displaystyle G}$, and all elements can be obtained by writing arbitrary products of ${\displaystyle \rho }$ and ${\displaystyle \mu }$ and simplifying the expression according to the rules ${\displaystyle \rho ^{n}=\iota }$, ${\displaystyle \mu ^{2}=\iota }$ and ${\displaystyle \rho \mu =\mu \rho ^{-1}}$. Indeed, as can be seen from the figure, a rotation composed with a reflection is new reflection.