Results 1 to 4 of 4

Math Help - Abstract Algebra: Permutations Proof

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    Abstract Algebra: Permutations Proof

    Hi guys (i gotta stop saying that, since we now have JaneBennet ),

    ahem, Hi Mathematicians,

    Is there anyone familiar with permutations in Abstract Algebra (if you are, skip to the "Problem:" section, the problem is in bold font, if not, you may read through this very brief introduction to permutations). permutations are one-to-one mapping diagrams with the natural numbers as the domain, kind of. for instance,

    \left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array} \right)

    is an S_3* permutation in which 1 \mapsto 2, 2 \mapsto 1 and 3 \mapsto 3

    we may also write these as cycles. that is, the above can be written as (1~2)(3) = (1~2) we omit (3) because it maps to itself and this is understood.

    how did we get that form? we did the following.

    start with the lowest number in the domain, obviously 1, here

    so we write (1

    but 1 maps to 2, so we write (1 2

    and 2 maps back to 1, this is a cycle, so we close brackets here, because we go back to the beginning. so we have (1 2)

    now we start at the next lowest number, 3.

    but 3 maps to itself, so we have, (1 2)(3), which we can write as (1 2), because it is understood if any number in the domain is omitted, it maps to itself.

    hope that crash course helped someone to understand the problem...



    Problem:

    I need to show that every element of S_n is a 2-cycle or can be written as a product of 2-cycles. I am given a "suggestion," \bold{(a_1a_2 \cdots a_k) = (a_1a_k) \cdots (a_1a_3)(a_1a_2)}



    *) we say a permutation is of group S_n if it is of the form

    \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ \_\_ & \_\_ & \cdots & \_\_ \end{array} \right)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Any permutation can be written as a product of disjoint cycles. Now each cycle (a1,...,ak) can be decomposed into transpositions. So that completes the proof.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    Any permutation can be written as a product of disjoint cycles. Now each cycle (a1,...,ak) can be decomposed into transpositions. So that completes the proof.
    the thing is, i know that. the problem is, those do not appear as theorems or anything in the book. i believe the book mentioned them, or they were mentioned in class, but since it is not a theorem, i think we would be expected to write out why those claims are true. (the professor i have makes us write everything out, once it's not a theorem or definition, or the proof is not in the appendix. he says we should do our work so that your dumbest classmate can follow with ease)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    the thing is, i know that. the problem is, those do not appear as theorems or anything in the book. i believe the book mentioned them, or they were mentioned in class, but since it is not a theorem, i think we would be expected to write out why those claims are true. (the professor i have makes us write everything out, once it's not a theorem or definition, or the proof is not in the appendix. he says we should do our work so that your dumbest classmate can follow with ease)
    Suppose we have a permutation \sigma on \{1,2,...,9\} it is defined as:
    1 --> 5
    2 --> 9
    3 --> 6
    4 --> 2
    5 --> 8
    6 --> 7
    7 --> 1
    8 --> 3
    9 --> 4

    Then let pick the number 1 and see it gets mapped into 5 and 5 gets mapped into 8 and 8 gets mapped into 3 and 3 gets mapped into 6 and 6 gets mapped into 7 and 7 gets mapped into 1 again. The notation (1,5,8,3,6,7) represents the permutation that maps 1->5->8->3->6->7 and leaves everything untouched. Now look at number 2, which was untouched by the permutation. Now 2 gets mapped into 9 and 9 gets mapped into 4 and 4 gets mapped into 2 again. The notation (2,9,4) represents the permutation 2->9->4 and everything else untouched.

    Then if you think about it, it should seem clear that \sigma = (1,5,8,3,6,7)(2,9,4). Note it is disjoint so the 3-cycle does not affect the 6-cycle and conversly. But then you can decompose (1,5,8,3,6,7) = (1,5)(5,8)(8,3)(3,6)(6,7) and (2,9,4) = (2,9)(9,4). Thus, \sigma = (1,5)(5,8)(8,3)(3,6)(6,7)(2,9)(9,4). And the same idea works in general.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Abstract Algebra proof help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 17th 2010, 12:20 PM
  2. abstract algebra proof
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 3rd 2010, 08:23 AM
  3. Proof-Abstract Algebra
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 22nd 2009, 07:48 PM
  4. Abstract algebra proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2008, 01:22 PM
  5. Abstract Algebra: Proof Help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 31st 2008, 05:59 PM

Search Tags


/mathhelpforum @mathhelpforum