Abstract Algebra/Group Theory/Permutation groups

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 indentify $\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^n=\iota$ for some $n\in \mathbb{Z}$. Then $\sigma$ is called an $n$-cycle, where $n$ 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.

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 $\sigma$, obtaining $\sigma=\sigma_1\sigma^\prime$. Repeat this process, which terminates since $\sigma^*$ is finite, and we have contructed a composition of disjoint cycles which equal $\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 $\sgn(\sigma)=1$ if $\sigma$ is even and $\sgn(\sigma)=-1$ if $\sigma$ is odd.

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

Proof: Observe first that $\iota \neq (a\ b)$ for $a\neq b$. Thus the minimum number of transpositions neccesary 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 paticular $\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 $\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 $\sgn$ is well-defined.

Theorem 14: Let $\sigma,\rho\in S_n$. Then, $\sgn(\sigma\rho)=\sgn(\sigma)\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 $\sgn(\sigma)\sgn(\rho)=1\cdot 1=1=\sgn(\sigma\rho)$. If one is odd and one is even, $k+l$ is odd and again $\sgn(\sigma)\sgn(\rho)=(-1)\cdot 1=-1=\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.