Abstract Algebra/Group Theory/Permutation groups

From Wikibooks, open books for an open world
Jump to: navigation, search

Symmetric groups[edit]

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<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 \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[edit]

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.