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   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 identify   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.

Remark 3: It's important to realize that if  , then so is  . If  , then if   we have that   is not 1–1.

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 from   to obtain  . Repeat this process, which terminates since   is finite, and we have constructed a composition of disjoint cycles that equals  .

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 identity   has even parity.

Proof: Observe first that   for  . Thus the minimum number of transpositions necessary to represent   is 2:  . Now, assume that for any representation using less than   transpositions must be even. Thus, let  . Now, since in particular  , 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.

Dihedral Groups

The lines represent the reflection symmetries of a regular hexagon
Illustration of the elements of the dihedral group   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  -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.