Results 1 to 8 of 8

Math Help - Permutations

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Permutations

    How can I show that the number of even permutations is equal to the number of odd permutations?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Permutations

    Quote Originally Posted by jzellt View Post
    How can I show that the number of even permutations is equal to the number of odd permutations?
    You know that \left[S_n:A_n\right]=2 and so S_n=A_n\cup xA_n for any x\notin A_n, but since all cosets have the same size this implies that \displaystyle |A_n|=|xA_n|=\frac{n!}{2} but you can easily check that xA_n are the odd permutations of S_n.

    Another, essentially the same, idea is to prove that the map \sigma\mapsto x\sigma is a bijection A_n\to\{\text{odd permutations}\} where x is any odd permutation.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Re: Permutations

    Thanks. Is it true an odd permutation can be expressed as an even permutation and visa versa? Can you give an example of this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Permutations

    Quote Originally Posted by jzellt View Post
    Thanks. Is it true an odd permutation can be expressed as an even permutation and visa versa? Can you give an example of this?
    I'm not quite sure what you mean. It's NOT true that there are permutations which are both even and odd.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Re: Permutations

    I thought if you have a product of even transpositions, it can be "messed" with and be expressed as a product of odd transpostions... Maybe I'm way off here though...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Permutations

    Quote Originally Posted by jzellt View Post
    I thought if you have a product of even transpositions, it can be "messed" with and be expressed as a product of odd transpostions... Maybe I'm way off here though...
    Yeah, that's precisely what CAN'T happen, it is actually phrased the exact way you did, with the appropriate negation insereted, in most textbooks. A different way of looking at this is that there is a natural action of S_n on the set \left\{\pm \Delta\right\} where \displaystyle \Delta(x)=\prod_{i<j}(x_i-x_j) and the action is \displaystyle \sigma(\Delta)=\prod_{i<j}(x_{\sigma}(i)}-x_{\sigma(j)}). We can then think of the set of even actions as the stabilizer of \Delta from where everything I've told you follows.

    If you haven't done group actions yet, just ignore that.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Re: Permutations

    A finite set with two or more elements has equal numbers of even and odd permutations.

    Proof. For each even permutation, we can obtain a unique odd permutation by transposing the first two elements. This defines a one-to-one correspondence between even and odd permutations, hence there are equal numbers of each.

    I found this proof somewhere. Can you explain with an example what they mean by transposing the first two elements. This is what I was meaning...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,369
    Thanks
    739

    Re: Permutations

    the key fact here is that if a permutation can be expressed as a product of an odd (resp. even) number of transpositions, it can ONLY be expressed as a product of an odd (resp.even) number of transpositions.

    this is a deep fact, and one which is often used to PROVE that [Sn:An] = 2. this is equivalent to proving the "signum" (or sign) function sgn:Sn-->{-1,1} is well-defined, after which it is easy to show that |An| = |Sn|/2, and that An is normal. one way of proving this is to invoke the Vandermonde polynomial:

    p(x_1,x_2,...,x_n) = \prod_{i<j}(x_i-x_j)

    and let a permutation σ in Sn act on p by taking:

    p(x_1,x_2,...,x_n) \rightarrow \prod_{i<j} (x_{\sigma(i)}-x_{\sigma(j)})

    odd permutations take p-->-p, while even permutations take p-->p.

    my point is: all the difficulty is buried in ensuring that "even permutation" and "odd permutation" are well-defined terms, that we cannot have a permutation that is both. until this is done, An is not a well-defined set.

    Quote Originally Posted by jzellt View Post
    A finite set with two or more elements has equal numbers of even and odd permutations.
    Proof. For each even permutation, we can obtain a unique odd permutation by transposing the first two elements. This defines a one-to-one correspondence between even and odd permutations, hence there are equal numbers of each.
    I found this proof somewhere. Can you explain with an example what they mean by transposing the first two elements. This is what I was meaning...
    if we call our initial (even) permutation σ, and our second permutation τ, then this means:

    τ(1) = σ(2)
    τ(2) = σ(1)
    τ(k) = σ(k), k = 3,4,...,n

    this is equivalent to writing: τ = (σ(1) σ(2))σ.

    note that τ has one more transpostion in its product than σ does.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2010, 06:48 AM
  2. Permutations
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 9th 2010, 10:24 PM
  3. Permutations Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2010, 07:30 PM
  4. permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2009, 05:42 PM
  5. Permutations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 16th 2008, 06:59 PM

Search Tags


/mathhelpforum @mathhelpforum