Abstract Algebra - Kutztown University of Pennsylvania

Abstract Algebra - Kutztown University of Pennsylvania

SECTION 9 Orbits, Cycles, and the Alternating Groups Given a set A, a relation in A is defined by : For a, bA, let ab if and only if b = n(a) for some nZ. (1) We can check that the relation is indeed an equivalent relation. (Reflexive, Symmetric, Transitive) Since an equivalence relation on a set yields a natural partition of the set, then we have the following Definition Let be a permutation of a set A. The equivalence classes in A determined by the equivalence relation (1) are the orbits of . Example Example: Let A={a, b, c, d}, and be the identity permutation of A. Find the orbits of in A. Solution: The orbits of are: {a}, {b}, {c}, {d} Find the orbits of the permutation

1 2 3 4 5 6 7 8 in S8. 3 8 6 7 4 1 5 2 Solution: The orbits containing 1 is {1, 3, 6} The orbits containing 2 is {2, 8} The orbits containing 4 is {4, 7, 5} Since these three orbits include all integers from 1 to 8, the complete list

of orbits of is {1, 3 ,6}, {2, 8}, {4, 7, 5} Cycles For the remainder of this section, we suppose that A= {1, 2, 3, , n} and that we are dealing with the elements of the symmetric group Sn. 12345678 has orbits : {1, 3 ,6}, {2, 8}, {4, 7, 5}, which 3 8 6 7 4 1 5 2 Recall can be indicated graphically by using circles. Such a permutation, described graphically be a single circle, is called a cycle. Note: we also consider the identity permutation to be a cycle. Here is the term cycle in a mathematically precise way: Cycle Definition

A permutation Sn is a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit. We also introduce a cyclic notation for a cycle. For example Given 1 2 3 4 5 6 7 8 . It has orbits {1, 3, 6}, {2}, {4}, {5}, {7}, {8}. 3 2 6 4 5 1 7 8

We can denote =(1, 3, 6). Note: an integer not appearing in this notation for is left fixed by . Example Example In S5, we see that Example 1 2 3 4 5 (1,3,5, 4) 3 2 5 1 4

(3,5, 4,1) (5, 4,1,3) (4,1,3,5) 1 2 3 4 5 6 7 8 3 8 6 7 4 1 5 2 (1,3,6)(2,8)(4,7,5)

Note: these cycles are disjoint, meaning that any integer is moved by at most one of these cycles; thus no one number appears in the notations of Two cycles. Theorem Theorem Every permutation of a finite set is a product of disjoint cycles. Note: Permutation multiplication is in general not commutative, but the multiplication of disjoint cycles is commutative. Example: 1 2 3 4 5 6 Given the permutation 6 5 2 4 3 1 , write it as a product of disjoint cycles. Solution: 1 2 3 4 5 6 (1,6)(2,5,3)

6 5 2 4 3 1 Example Consider the cycles (1, 4, 5, 6) and (2, 1, 5) in S6. Find (1, 4, 5, 6)(2, 1, 5) and (2, 1, 5)(1, 4, 5, 6). 1 2 3 4 5 6 Solution: (1, 4, 5, 6)(2, 1, 5)= 6 4 3 5 2 1 1 2 3 4 5 6

(2, 1, 5)(1, 4, 5, 6)= 4 1 3 2 6 5 Even and Odd Permutations Definition A cycle of length 2 is a transposition. A computation shows that (a1,a2,, an)=(a1,an)(a1,an-1)(a1,a3)(a1,a2), therefore any cycle is a product of transpositions. Corollary Any permutation of a finite set of at least two elements is a product of transpositions.

Examples Example: (1, 6)(2, 5, 3)=(1, 6)(2, 3)(2, 5) In Sn for n2, the identity permutation is the product (1, 2)(2, 1). Note: a representation of the permutation in this way is not unique, but the number of transposition must either always be even or always be odd. Theorem: No permutation is Sn can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions. Odd/Even permutation Definition A permutation of a finite set is even if it can be expressed as a product of an even number of transpositions. A permutation of a finite set is odd if it can be expressed as a product of an odd number of transpositions.

Example: The identity permutation in Sn is an even permutation since =(1, 2)(2, 1). The permutation (1, 4, 5, 6)(2,1, 5) in S6 is odd since (1, 4, 5, 6)(2,1, 5)=(1, 6)(1, 5)(1, 4)(2, 5)(2, 1) The Alternating Groups Theorem If n2, then the collection of all even permutations of {1, 2, 3,, n} forms a subgroup of order n! / 2 of the symmetric group Sn. Definition The subgroup of Sn consisting of all even permutations of n letters is the alternating groups An on n letters.

Recently Viewed Presentations

  • PowerPoint Template

    PowerPoint Template

    EVOLUTION OF MANUFACTURING INDUSTRIES IN THE LAST DECADE Quality has preserved its position as the number one competitive priority through the last 10 years. The same holds true for TQM as the most widely employed action plan. Good performance in...
  • Site Overview LTER Site Name - US Long Term Ecological ...

    Site Overview LTER Site Name - US Long Term Ecological ...

    Web sites in different content management systems, dependent on databases that are difficult to maintain under the current data management structure.
  • 4.1 Introduction to Covalent Bonding Covalent bonds result

    4.1 Introduction to Covalent Bonding Covalent bonds result

    HOW TO Draw a Lewis Structure. CH. 4 NH. 3. 4.2 Lewis Structures B. Multiple Bonds. One lone pair of e− can be converted into one bondingpair of e− for each 2 e− needed to complete an octet on a...
  • Folie 1

    Folie 1

    Eiko Fried. KU Leuven. Major Depression (MD) Prevalence. Most common psychiatric disorder. Recurrence. 50-75% suffer from more than on episode. Previous episodes reduce treatment efficacy. Disability. Greatest impactof all biomedicaldiseases on disability.
  • Movement Motivates the Mind….

    Movement Motivates the Mind….

    "AM physical education days is always helpful with the classroom routine. Students are more settled on days after we have P.E." Mrs. Moody. Better Listeners (Mrs. Bowen, Verona Elementary) Settle in quicker (Mrs. Bowen, Verona Elementary)
  • EntertainmentIndustry Pioneers - Sports Career Consulting, LLC

    EntertainmentIndustry Pioneers - Sports Career Consulting, LLC

    The Grinch and The Cat in the Hat) Click to add notes. ... no music act had ever rung up even 1 million digital tracks in a single week. In that same period, fans also bought more than 2.3 million...
  • A Hierarchical Mathematical Model for Automatic Pipelining and

    A Hierarchical Mathematical Model for Automatic Pipelining and

    A Hierarchical Mathematical Modelfor Automatic Pipelining and Allocation using Elastic Systems. Jordi Cortadella and Jordi Petit. Universitat Politècnica de Catalunya, Barcelona
  • Give Me Liberty! Ch16 - shshistory.com

    Give Me Liberty! Ch16 - shshistory.com

    Some Indians sought solace in the Ghost Dance, a religious revitalization campaign reminiscent of the pan-Indian movements led by earlier prophets like Neolin and Tenskwatawa . On December 29, 1890, soldiers opened fire on Ghost Dancers encamped on Wounded Knee...