# Abstract Algebra/Group Theory/Permutation groups

## 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. 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.