1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that the order of An is (1/2)n!

  1. Oct 30, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that the order of An (the subgroup of all even permutation of Sn) is (1/2)n!
    And even permutation is one that must be written with an even number of transpositions (2-cycles)

    2. Relevant equations



    3. The attempt at a solution

    I know that being (1/2)n! means half of Sn is even. I think I'm supposed to show why the subgroup must be half. I have in my notes something about a mapping, it was one of those days where I couldn't read my prof's handwriting (same as always) and I wasn't feeling up to asking him what the heck the board said. Something about a mapping Phi, that maps evens into odds.

    This is just one in a long line of theorems I'm studying this weekend, and my brain is about fried. Please be clear, and try not to make it too hard. :frown:
     
  2. jcsd
  3. Oct 30, 2011 #2
    This is what wikipedia says, "If n>1, then there are just as many even permutations in Sn as there are odd ones;[3] consequently, An contains n!/2 permutations. [The reason: if σ is even, then (12)σ is odd; if σ is odd, then (12)σ is even; the two maps are inverse to each other.][3]"

    But I don't get why this implies that there must be an equal number of even permuations and odd permutations in Sn.
     
  4. Oct 30, 2011 #3

    I like Serena

    User Avatar
    Homework Helper

    For each even element there is a unique odd element.
    That is, there is a 1-1 relation between the two (a "bijection").
    So the number of even elements must be equal to the number of odd elements.
     
  5. Oct 30, 2011 #4
    Why is there a 1-1 relationship between them?
     
  6. Oct 30, 2011 #5

    Deveno

    User Avatar
    Science Advisor

    one way to see this is using the "sign" function:

    sgn(p) = 1, if p is even
    sgn(p) = -1, if p is odd.

    this is, in fact a homomorphism from Sn to {-1,1}, which is cyclic of order 2.

    even more nicely, this homomorphism is onto, which means that {-1,1} ≅ Sn/ker(sgn).

    and, ker(sgn) = {even permutations} = An.

    so we know that |Sn/An| = 2.

    can you do the rest?
     
  7. Oct 30, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

    Ah, forget 1-1. It's true, but it makes it more complex.


    An element is either even or odd.

    Take the mapping from the even permutations to odd permutations, given by a → (1 2)a.
    Each even element is mapped onto a (different) odd element.
    So there are at least as many odd elements as even elements.

    Similarly take the mapping from the odd permutations to the even permutations, given by b → (1 2)b.
    Each odd element is mapped onto a (different) even element.
    So there are at least as many even elements as odd elements.

    Therefore there must be the same number of even as odd elements.
     
    Last edited: Oct 30, 2011
  8. Oct 30, 2011 #7
    We haven't done homomorphs or isomorphs or any-morphs yet. Also, what does ker mean? kernal? I assume sgn means sign?
     
  9. Oct 30, 2011 #8
    why do the elements have to map to each other?
     
  10. Oct 30, 2011 #9

    Deveno

    User Avatar
    Science Advisor

    then you'll have to use I like Serena's method.

    the "hard part" is showing that p ---> (1 2)p is a bijection between the odd permutations and even permutations.
     
  11. Oct 30, 2011 #10

    I like Serena

    User Avatar
    Homework Helper

    (1 2) is an odd permutation.

    An even permution is one that can be written as the product of an even number of transpositions.
    If we add another transposition (an odd permutation), we get the product of an odd number of transpositions.
     
  12. Oct 30, 2011 #11

    Deveno

    User Avatar
    Science Advisor

    suppose q is any even permutation. we want to find some odd permutation p, such that:

    (1 2)p = q.

    this will show that p ---> (1 2)p is onto, and since Sn is finite, a surjection on a finite set is bijective.

    well, if q is even, then (1 2)q is odd (adding another transpositon changes the parity, or sign).

    so we can choose as our odd permutation p = (1 2)q:

    (1 2)p = (1 2)(1 2)q = q.
     
  13. Oct 30, 2011 #12
    Well, say we were in S4, and we took an arbitrary permutation, say (1 2 3 4), and then it is written as (3 2)(4 3)(1 4), so it's odd (is that right, i thought even length mean it was even?) so we know (1 2) is in S4, because it's in all Sn greater than or equal to two, so we know (1 2 3 4)*(1 2) is in S4, and we know this new permutation will have opposite parity from (1 2 3 4) because if (1 2) is in (1 2 3 4) then we take away one if it's not, we add one. and so suppose (assuming I'm right about (1 2 3 4) being odd) there are k odd permutations in S4, how do I know there will be at least k even permutations (how do I know each mapping will map to a different even permutation)?
     
  14. Oct 30, 2011 #13

    I like Serena

    User Avatar
    Homework Helper

    You have it right. Even length means odd permution.
    Think of (1 2) which has an even length, but is only 1 transposition (odd!).



    Perhaps I should remark that the number of transpositions is not fixed.
    An odd permutation can be written as any odd number of permutations (with a certain minimum).
    For instance (1 2)=(1 2)(1 2)(1 2).


    Very sharp! :smile:

    Suppose a and b are different odd permutations that map to the same even permutation.
    So (1 2)a = (1 2)b.
    Then (1 2)(1 2)a = (1 2)(1 2)b, that is, a=b, which is a contradiction.
    So each odd permutation maps onto a different even permutation.
     
  15. Oct 30, 2011 #14
    ah, left cancellation law. Okay, this helped. Thanks ILS. How come you know all this stuff anyway? You know a great level of detail of wide-ranging math subjects. How come you don't forget stuff? Shouldn't you only have a narrow band of this level of knowledge, maintained by everyday use ?
     
  16. Oct 30, 2011 #15

    I like Serena

    User Avatar
    Homework Helper

    Thanks! :blushing:

    Actually, I'm a software engineer who doesn't do math or physics (that's why I'm so active on PF! :wink:).

    But in my spare time I'm a private tutor.
    Currently I have a student who is already a math teacher, but who needs to learn algebra to upgrade her level.
    I also have a number of psychology students who have difficulty learning statistics.
     
  17. Oct 30, 2011 #16
    So it's a fascinating coincidence? Well, I think you're a great tutor. :) You going to help me with diffyQ next semester?
     
  18. Oct 30, 2011 #17

    I like Serena

    User Avatar
    Homework Helper

    Not really a coincidence.
    I also do mechanics, electronics, linear algebra, differential equations, etcetera.
    I'm currently (re)practicing/learning thermodynamics on PF. :biggrin:
    And every now and then I try my hand at chemistry, but I'm a bit scared someone (Borek?) will find out I'm not so good at it. :redface:

    I saw you were helping people on PF as well! :smile:

    I'll look forward to seeing you with diffyQ. :cool:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook