# 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 $A$  be any set. Then, the set $S_{A}$  of bijections from $A$  to itself, $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: $(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 $\mathrm {id} _{A}(a)=a$  for all $a\in A$ . Finally, the inverse of a function $f$  is the function $f^{-1}$  taking $f(a)$  to $a$  for all $a\in A$ . This function exists and is unique since $f$  is a bijection. Thus $S_{A}$  is a group, as stated.

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

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

When $\sigma \in S_{n}$ , we can specify $\sigma$  by specifying where it sends each element. There are many ways to encode this information mathematically. One obvious way is to identify $\sigma$  as the unique $n\times n$  matrix with value $1$  in the entries $(i,\sigma (i))$  and $0$  elsewhere. Composition of functions then corresponds to multiplication of matrices. Indeed, the matrix corresponding to $\rho$  has value $1$  in the entries $(i,\rho (i))$ , which is the same as $(\sigma (j),\rho (\sigma (j)))$ , so the product has value $1$  in the entries $(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 $\sigma \in S_{n}$  by a $2\times n$  matrix $\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 $\sigma ,\rho \in S_{n}$ . Then the product $\sigma \rho \equiv \sigma \circ \rho$  is the function obtained by first acting with $\rho$ , and then by $\sigma$ . That is, $\sigma \rho (x)=\sigma (\rho (x))$ . This point is important to keep in mind when computing products in $S_{n}$ . Some textbooks try to remedy the frequent confusion by writing functions like $(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 $S_{n}$ .

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

${\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: $S_{n}$  has order $n!$ .

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

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

Proof: Let $\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 $\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 $\sigma \rho =\left({\begin{array}{ccccc}1&2&3&\dots &n\\2&3&1&\dots &n\end{array}}\right)$  and $\rho \sigma =\left({\begin{array}{ccccc}1&2&3&\dots &n\\3&1&2&\dots &n\end{array}}\right)$ . Since $\sigma \rho \neq \rho \sigma$ , $S_{n}$  is not abelian.

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

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

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

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

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

Proof: Let $\sigma \in S_{n}$ . Choose an element $a\in \sigma ^{*}$  and compute $\sigma (a),\sigma ^{2}(a),...,\sigma ^{k}(a)=a$ . Since $S_{n}$  is finite of order $n!$ , we know that $k$  exists and $k\leq n!$ . We have now found a $k$ -cycle $\sigma _{1}$  including $a$ . Since $\sigma _{1}^{*}=\{a,\sigma (a),...,\sigma ^{k-1}(a)\}$ , this cycle may be factored out from $\sigma$  to obtain $\sigma =\sigma _{1}\sigma ^{\prime }$ . Repeat this process, which terminates since $\sigma ^{*}$  is finite, and we have constructed a composition of disjoint cycles that equals $\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 $n$ -cycle $\sigma$ , we can show its action by choosing any element $a\in \sigma ^{*}$  and writing $\sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)$ .

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

Proof: Let $\sigma =\left(a\ \sigma (a)\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)$ . Then, $\sigma =\left(a\ \sigma ^{2}(a)\ ...\ \sigma ^{n-1}(a)\right)\left(a\ \sigma (a)\right)$  (check this!), omitting the composition sign $\circ$ . Interate this process to obtain $\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 $\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 $\operatorname {sgn}(\sigma )=1$  if $\sigma$  is even and $\operatorname {sgn}(\sigma )=-1$  if $\sigma$  is odd.

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

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

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

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

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

Proof: Decompose $\sigma$  and $\rho$  into transpositions: $\sigma =\mu _{1}...\mu _{k}$ , $\rho =\nu _{1}...\nu _{l}$ . Then $\sigma \rho =\mu _{1}...\mu _{k}\nu _{1}...\nu _{l}$  has parity given by $k+l$ . If both are even or odd, $k+l$  is even and indeed $\operatorname {sgn}(\sigma )\operatorname {sgn}(\rho )=1\cdot 1=1=\operatorname {sgn}(\sigma \rho )$ . If one is odd and one is even, $k+l$  is odd and again $\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 $S_{n}$  equals the number of odd permutations.

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

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

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

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

Theorem 18: Let $n\geq 3$ . Then $A_{n}$  is generated by the 3-cycles in $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 $a,b,c,d\in S_{n}$  be distinct. Then, by some casework,

i) $(a\ b)(a\ b)=(a\ b\ c)^{3}$ ,
ii) $(a\ b)(b\ c)=(c\ a\ b)$ , and
iii) $(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 $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 $C_{3}$ , it generates the whole group $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 $n$ -gon has $n$  rotational symmetries and $n$  reflection symmetries. The dihedral groups capture these by consisting of the associated rotations and reflections.
Definition 19: The dihedral group of order $2n$ , denoted $D_{2n}$ , is the group of rotations and reflections of a regular $n$ -gon.
Theorem 20: The order of $D_{2n}$  is precisely $2n$ .
Proof: Let $\rho$  be a rotation that generates a subgroup of order $n$  in $D_{2n}$ . Obviously, $\langle \rho \rangle$  then captures all the pure rotations of a regular $n$ -gon. Now let $\mu$  be any rotation in The rest of the elements can then be found by composing each element in $\langle \rho \rangle$  with $\mu$ . We get a list of elements $D_{2n}=\{\iota ,\rho ,...,\rho ^{n-1},\mu ,\mu \rho ,...,\mu \rho ^{n-1}\}$ . Thus, the order of $D_{2n}$  is $2n$ , justifying its notation and proving the theorem.
Remark 21: From this proof we can also see that $\{\rho ,\mu \}$  is a generating set for $G$ , and all elements can be obtained by writing arbitrary products of $\rho$  and $\mu$  and simplifying the expression according to the rules $\rho ^{n}=\iota$ , $\mu ^{2}=\iota$  and $\rho \mu =\mu \rho ^{-1}$ . Indeed, as can be seen from the figure, a rotation composed with a reflection is new reflection.