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

  • Yom Kippur & the Book of Hebrews

    Yom Kippur & the Book of Hebrews

    For example, during these days he himself tosses the blood of the daily sacrifice onto the altar in the morning and evenings; he offers up the incense on the golden incense altar; he attends to the service of the menorah...
  • Principles of Bobath Approach

    Principles of Bobath Approach

    PRINCIPLES OF BOBATH APPROACH BY - GAJANAN BHALERAO What is Bobath therapy? Bobath therapy is an interdisciplinary approach to the management of cerebral palsy involving occupational therapy, physiotherapy and speech and language therapy.
  • My work during the summer - openlab-plugfest.npafi.org

    My work during the summer - openlab-plugfest.npafi.org

    MySlice. A ready-made and easily customizable user interface for testbeds. Is responsible for providing the testbed resource descriptions. Provides a modular implementation of independent plugins and a message passing interface shared between them.
  • Benefits and Products offered by our founder Venerable

    Benefits and Products offered by our founder Venerable

    Benefits and Products offered by our founder Venerable Michael J. McGivney * * Knights of Columbus Faith Based Products The Primary Goal of the Knights of Columbus: "To render Financial Aid to its members and the beneficiaries of members." -From...
  • Chempack - Virginia Department of Health

    Chempack - Virginia Department of Health

    State On Scene Coordinator (SOSC): Department of Environmental Quality (DEQ) Navy On Scene Coordinator (NOSC): NAS Oceana CO (Responsible Party) Local On Scene Coordinator (LOSC): City Emergency Manager. Virginia Beach Department of Public Health/VDH was a "Cooperating Agency" … not...
  • Texture Mapping - Computer Science and Engineering

    Texture Mapping - Computer Science and Engineering

    Anti-aliasing for Texture Mapping. Quality considerations. So far we just mapped one point. ... Calculate (or approximate) the integral of the texture function under this area. Approximate: ... Find level of the mip-map where the area of each mip-map pixel...
  • Planning and Managing European Projects, Grundvig course AT ...

    Planning and Managing European Projects, Grundvig course AT ...

    METHODOLOGY -Classroom based teaching. During the course, we were exposed to a range of classroom lessons mixed with practical exercises (and group work). The course provided blended learning with some parts offered by the e-learning platform of the association (mainly...
  • Place Value, Decimals and Fractions Negative numbers Objectives

    Place Value, Decimals and Fractions Negative numbers Objectives

    Year 3/4. Objectives. Day 1. Place negative numbers on a line; order positive and negative numbers. Place negative numbers on a line; order positive and negative numbers.