This document provides an overview of permutation groups and related concepts. It begins by defining permutation groups and noting their importance in studying symmetries and solving polynomial equations. It then gives examples of permutations of sets and subgroups of the symmetric group. The document introduces cycle notation as a more efficient way to represent permutations. It defines transpositions and the alternating group, proving various properties. It concludes by introducing dihedral groups.
This document provides an overview of permutation groups and related concepts. It begins by defining permutation groups and noting their importance in studying symmetries and solving polynomial equations. It then gives examples of permutations of sets and subgroups of the symmetric group. The document introduces cycle notation as a more efficient way to represent permutations. It defines transpositions and the alternating group, proving various properties. It concludes by introducing dihedral groups.
This document provides an overview of permutation groups and related concepts. It begins by defining permutation groups and noting their importance in studying symmetries and solving polynomial equations. It then gives examples of permutations of sets and subgroups of the symmetric group. The document introduces cycle notation as a more efficient way to represent permutations. It defines transpositions and the alternating group, proving various properties. It concludes by introducing dihedral groups.
This document provides an overview of permutation groups and related concepts. It begins by defining permutation groups and noting their importance in studying symmetries and solving polynomial equations. It then gives examples of permutations of sets and subgroups of the symmetric group. The document introduces cycle notation as a more efficient way to represent permutations. It defines transpositions and the alternating group, proving various properties. It concludes by introducing dihedral groups.
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 8
Chapter 4
PERMUTATION GROUPS In this chapter one should be able: 1. To 2. 3. 4. 5.
construct
some
finite
groups
whose
elements,
called
permutations act on finite sets.
To make cyclic permutations and transpositions. To know the symmetric and alternating groups. To determine dihedral group. To know the Cayleys theorem.
4.1. Permutation Groups
Permutation Groups are central to the study of geometric symmetries and to Galois theory, the study of finding solutions of polynomial equations. They also provide abundant examples of nonabelian groups. The symmetries actually consist of permutations of the three vertices, where a permutation of the set S = fA;B;Cg is aone-to-one and onto mapping SS. The three vertices have the following six permutations. ABC ABC
ABC BCA
ABC CBA
ABC CAB
ABC ACB
ABC BAC
We have used the array
ABC BCA to denote the permutation that sends A to B, B to C, and C to A. The symmetries of a triangle form a group. Definition: In general, the permutations of a set X form a group SX. If X is a _niteset, we can assume X = f1; 2; : : : ; ng. In this case we write Sn instead ofSX. The following theorem says that Sn is a group. We call this group the symmetric group on n letters. Theorem 4.1. The symmetric group on n letters, Sn, is a group with n! elements, where the binary operation is the composition of maps. Example 1. Consider the subgroup G of S5 consisting of the identity permutation id and the permutations 12345 12354 12345 32145 12345 32154 The following table tells us how to multiply elements in the permutation group G.
Remark. Though it is natural to multiply elements in a group from left to
right, functions are composed from right to left. Let and be
permutations on a set X. To compose and as functions, we calculate (
()x) = ( ( x)). Example 2. Permutation multiplication is not usually commutative. Let 1234 4123 1234 2143 Then 1234 1432 but 1234 3214 4.2. Cycle Notation The notation that we have used to represent permutations up to this point is cumbersome, to say the least. To work effectively with permutation groups, we need a more streamlined method of writing down and manipulating permutations. A permutation SX is a cycle of length k if there exist elements a1; a2 . . .ak X such that (a1) = a2 (a2) = a3 . . . (ak) = a1 and (x) = x for all other elements x 2 X. We will write (a1; a2; : : : ; ak) to denote the cycle . Cycles are the building blocks of all permutations. Example 3. The permutation
1234567 6351427 (162354) is a cycle of length 6, whereas 123456 142356 (243) is a cycle of length 3. Not every permutation is a cycle. Consider the permutation 123456 241365 (1243)(56): This permutation actually contains a cycle of length 2 and a cycle of length 4. Theorem 5.3. Every permutation in Sn can be written as the product of disjoint cycles. Example 6. Let 123456 643152 123456 321564 Using cycle notation, we can write = (1624) = (13)(456) = (136)(245) = (143)(256): Remark. From this point forward we will _nd it convenient to use cycle notation to represent permutations. When using cycle notation, we often denote the identity permutation by (1). 4.2.1. Transpositions The simplest permutation is a cycle of length 2. Such cycles are called transpositions. Since (a1; a2; : : : ; an) = (a1an)(a1an-1) . . .(a1a3)
(a1a2); any cycle can be written as the product of transpositions, leading
to the following proposition. Proposition 5.4. Any permutation of a finite set containing at least two elements can be written as the product of transpositions. Example 7. Consider the permutation (16)(253) = (16)(23)(25) = (16)(45)(23)(45)(25): As we can see, there is no unique way to represent permutation as the product of transpositions. For instance, we can write the identity permutation as (12)(12), as (13)(24)(13)(24), and in many other ways. However, as it turns out, no permutation can be written as the product of both an even number of transpositions and an odd number of transpositions. For instance, we could represent the permutation (16) by (23)(16)(23) or by (35)(16)(13)(16)(13)(35)(56); but (16) will always be the product of an odd number of transpositions. Lemma 5.5 If the identity is written as the product of r transpositions, id = 1, 2, n; then is an even number. Theorem 5.6. If a permutation _ can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling _ must also contain an even number of transpositions. Similarly, if _ can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling _ must also contain an odd number of transpositions. 4.3. The Alternating Groups
One of the most important subgroups of Sn is the set of all even
permutations, An. The group An is called the alternating group on n letters. Theorem 5.7. The set An is a subgroup of Sn. Proposition 5.8. The number of even permutations in Sn, n _ 2, is equal to the number of odd permutations; hence, the order of An is n!=2. Example 8. The group A4 is the subgroup of S4 consisting of even permutations. There are twelve elements in A4: (1) (12)(34) (13)(24) (14)(23) (123) (132) (124) (142) (134) (143) (234) (243): 4.4. Dihedral Groups Another special type of permutation group is the dihedral group.
Exercises: Objective: To asses students knowledge, skills, and understanding on the topic permutation groups. 1. Write the following in cycle notation.
