Abstract Algebra/Group Theory/Permutation groups
Theorem 1: Let be any set. Then, the set of bijections from to itself, , 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: where the composition is defined. The identity element is the identity function given by for all . Finally, the inverse of a function is the function taking to for all . This function exists and is unique since is a bijection. Thus is a group, as stated. ∎
is called the symmetric group on . When , we write its symmetric group as , and we call this group the symmetric group on letters. It is also called the group of permutations on letters. As we will see shortly, this is an appropriate name.
Instead of , we will use a different symbol, namely , for the identity function in .
When , we can specify by specifying where it sends each element. There are many ways to encode this information mathematically. One obvious way is to indentify as the unique matrix with value in the entries and elsewhere. Composition of functions then corresponds to multiplication of matrices. Indeed, the matrix corresponding to has value in the entries , which is the same as , so the product has value in the entries . This notation may seem cumbersome. Luckily, there exists a more convenient notation, which we will make use of.
We can represent any by a matrix . 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 . Then the product is the function obtained by first acting with , and then by . That is, . This point is important to keep in mind when computing products in . Some textbooks try to remedy the frequent confusion by writing functions like , 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 .
Example 3: We will show the multiplication table for . We introduce the special notation for : , , , and . The multiplication table for is then
Theorem 4: has order .
Proof: This follows from a counting argument. We can specify a unique element in by specifying where each is sent. Also, any permutation can be specified this way. Let . In choosing we are completely free and have choices. Then, when choosing we must choose from , giving a total of choices. Continuing in this fashion, we see that for we must choose from , giving a total of choices. The total number of ways in which we can specify an element, and thus the number of elements in is then , as was to be shown. ∎
Theorem 5: is non-abelian for all .
Proof: Let be the function only interchanging 1 and 2, and be the function only interchanging 2 and 3. Then and . Since , is not abelian. ∎
Definition 6: Let such that for some . Then is called an -cycle, where is the smallest positive such integer. Let be the set of integers such that . Two cycles are called disjoint if . Also, a 2-cycle is called a transposition.
Theorem 7: Let . If , then .
Proof: For any integer such that but we have . A similar argument holds for but . If , we must have . Since , we have now exhausted every , and we are done. ∎
Theorem 8: Any permutation can be represented as a composition of disjoint cycles.
Proof: Let . Choose an element and compute . Since is finite of order , we know that exists and . We have now found a -cycle including . Since , this cycle may be factored out , obtaining . Repeat this process, which terminates since is finite, and we have contructed a composition of disjoint cycles which equal . ∎
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 -cycle , we can show its action by choosing any element and writing .
Theorem 9: Any -cycle can be represented as a composition of transpositions.
Proof: Let . Then, (check this!), omitting the composition sign . Interate this process to obtain . ∎
Note 10: This way of representing 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 if is even and if is odd.
Lemma 12: The indentity has even parity.
Proof: Observe first that for . Thus the minimum number of transpositions neccesary to represent is 2: . Now, assume that for any representation using less than transpositions must be even. Thus, let . Now, since in paticular , we must have for some . Since disjoint transpositions commute, and where , it is always possible to configure the transpositions such that the first two transpositions are either , reducing the number of transposition by two, or . In this case we have reduced the number of transpositions involving by 1. We restart the same process as above. with the new representation. Since only a finite number of transpositions move , we will eventually be able to cancel two permutations and be left with transpositions in the product. Then, by the induction hypothesis, must be even and so is even as well, proving the lemma. ∎
Theorem 13: The parity of a permutation, and thus the function, is well-defined.
Proof: Let and write as a product of transposition in two different ways: . Then, since has even parity by Lemma 11 and . Thus, , and , so has a uniquely defined parity, and consequentially is well-defined. ∎
Theorem 14: Let . Then, .
Proof: Decompose and into transpositions: , . Then has parity given by . If both are even or odd, is even and indeed . If one is odd and one is even, is odd and again , proving the theorem. ∎
Lemma 15: The number of even permutations in equals the number of odd permutations.
Proof: Let be any even permutation and a transposition. Then has odd parity by Theorem 14. Let be the set of even permutations and the set of odd permutations. Then the function given by for any and a fixed transposition , is a bijection. (Indeed, it is a transposition in !) Thus and have the same number of elements, as stated. ∎
Definition 16: Let the set of all even permutations in be denoted by . is called the alternating group on letters.
Theorem 17: is a group, and is a subgroup of of order .
Proof: We first show that is a group under composition. Then it is automatically a subgroup of . That is closed under composition follows from Theorem 14 and associativity is inherited from . Also, the identity permutation is even, so . Thus is a group and a subgroup of . Since the number of even and odd permutations are equal by Lemma 14, we then have that , proving the theorem. ∎
Theorem 18: Let . Then is generated by the 3-cycles in .
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 be distinct. Then, by some casework,
- i) ,
- ii) , and
- iii) ,
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 , 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 , it generates the whole group . We leave it to the reader to show this.
The dihedral groups are the symmetry groups of regular polygons. As such, they are subgroups of the symmetric groups. In general, a regular -gon has rotational symmetries and reflection symmetries. The dihedral groups capture these by consisting of the associated rotations and reflections.
Definition 19: The dihedral group of order , denoted , is the group of rotations and reflections of a regular -gon.
Theorem 20: The order of is precisely .
Proof: Let be a rotation that generates a subgroup of order in . Obviously, then captures all the pure rotations of a regular -gon. Now let be any rotation in The rest of the elements can then be found by composing each element in with . We get a list of elements . Thus, the order of is , justifying its notation and proving the theorem. ∎
Remark 21: From this proof we can also see that is a generating set for , and all elements can be obtained by writing arbitrary products of and and simplifying the expression according to the rules , and . Indeed, as can be seen from the figure, a rotation composed with a reflection is new reflection.