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\to 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{i}\mathrm{d}}_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,\mathrm{...},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}{ccccccc}\circ & {\rho }_0& {\rho }_1& {\rho }_2& {\mu }_1& {\mu }_2& {\mu }_3\\ {\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,\mathrm{...},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,\mathrm{...},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,\mathrm{...},n\}-\{\sigma (1),\mathrm{...},\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)\mathrm{...}\cdot 2\cdot 1=n!$, as was to be shown. ∎

Theorem 5: $S_n$ is non-abelian for all $n\ge 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 \ne \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 }^{\ast }$ be the set of integers $a$ such that $\sigma (a)\ne a$. Two cycles $\sigma ,\rho$ are called disjoint if ${\sigma }^{\ast }\cap {\rho }^{\ast }=\mathrm{\varnothing }$. Also, a 2-cycle is called a transposition.

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

Theorem 7: Let $\sigma ,\rho \in S_n$. If ${\sigma }^{\ast }\cap {\rho }^{\ast }=\mathrm{\varnothing }$, then $\sigma \rho =\rho \sigma$.

Proof: For any integer $1\le a\le n$ such that $a\in {\sigma }^{\ast }$ but $a\in ̸{\rho }^{\ast }$ 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 }^{\ast }$ but $a\in ̸{\sigma }^{\ast }$. If $a\in ̸{\sigma }^{\ast }\cup {\rho }^{\ast }$, we must have $\sigma \rho (a)=\sigma (a)=a=\rho (a)=\rho \sigma (a)$. Since ${\sigma }^{\ast }\cap {\rho }^{\ast }=\mathrm{\varnothing }$, we have now exhausted every $a\in \{1,\mathrm{...},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 }^{\ast }$ and compute $\sigma (a),{\sigma }^2(a),\mathrm{...},{\sigma }^k(a)=a$. Since $S_n$ is finite of order $n!$, we know that $k$ exists and $k\le n!$. We have now found a $k$-cycle ${\sigma }_1$ including $a$. Since ${\sigma }_1^{\ast }=\{a,\sigma (a),\mathrm{...},{\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 }^{\ast }$ 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 }^{\ast }$ and writing $\sigma =(a\sigma (a){\sigma }^2(a)\mathrm{...}{\sigma }^{n-1}(a))$.

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

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

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 $\mathrm{sgn}(\sigma )=1$ if $\sigma$ is even and $\mathrm{sgn}(\sigma )=-1$ if $\sigma$ is odd.

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

Proof: Observe first that $\iota \ne (ab)$ for $a\ne b$. Thus the minimum number of transpositions necessary to represent $\iota$ is 2: $\iota =(ab)(ab)$. Now, assume that for any representation using less than $k$ transpositions must be even. Thus, let $\iota =(a_1{b}_1)\mathrm{...}(a_k{b}_k)$. Now, since in particular $\iota (a_1)=a_1$, we must have $a_1\in (a_i{b}_i{)}^{\ast }$ for some $1<i\le 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\ne a_r\ne 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 $\mathrm{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\mathrm{...}{\tau }_k={{\tau }_1}^{\prime }\mathrm{...}{\tau }_{k^{\prime }}$. Then, since $\iota$ has even parity by Lemma 11 and $\iota =\sigma {\sigma }^{-1}={\tau }_1\mathrm{...}{\tau }_k{\tau }_{k^{\prime }}\mathrm{...}{{\tau }_1}^{\prime }$. Thus, $k+k^{\prime }\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}2$, and $k\equiv k^{\prime }\mathrm{m}\mathrm{o}\mathrm{d}2$, so $\sigma$ has a uniquely defined parity, and consequentially $\mathrm{sgn}$ is well-defined. ∎

Theorem 14: Let $\sigma ,\rho \in S_n$. Then, $\mathrm{sgn}(\sigma \rho )=\mathrm{sgn}(\sigma )\mathrm{sgn}(\rho )$.

Proof: Decompose $\sigma$ and $\rho$ into transpositions: $\sigma ={\mu }_1\mathrm{...}{\mu }_k$, $\rho ={\nu }_1\mathrm{...}{\nu }_l$. Then $\sigma \rho ={\mu }_1\mathrm{...}{\mu }_k{\nu }_1\mathrm{...}{\nu }_l$ has parity given by $k+l$. If both are even or odd, $k+l$ is even and indeed $\mathrm{sgn}(\sigma )\mathrm{sgn}(\rho )=1\cdot 1=1=\mathrm{sgn}(\sigma \rho )$. If one is odd and one is even, $k+l$ is odd and again $\mathrm{sgn}(\sigma )\mathrm{sgn}(\rho )=(-1)\cdot 1=-1=\mathrm{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\to 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\ge 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) $(ab)(ab)=(abc{)}^3$,

ii) $(ab)(bc)=(cab)$, and

iii) $(ab)(cd)=(adc)(abc)$,

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, $⟨\rho ⟩$ 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 $⟨\rho ⟩$ with $\mu$. We get a list of elements $D_{2n}=\{\iota ,\rho ,\mathrm{...},{\rho }^{n-1},\mu ,\mu \rho ,\mathrm{...},\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.