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<i\leq k$. 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 lines represent the reflection symmetries of a regular hexagon

Illustration of the elements of the dihedral group $D_{16}$ as rotations and reflections of a stop sign.

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.