Results 1 to 8 of 8
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - What is the permutation of pi?

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    What is the permutation of pi?

    Mr. Pinter's abstract algebra book on page-81 states that:

    "If \pi \in S_n, then \pi cannot be both an odd permutation and an even permutation."

    --where S_n is a symmetric group.

    There's a website that tells:

    PlanetMath

    \pi=\left( \begin{array}{ccccccc} 1 & 2 & \cdots & m-r+1 & m-r+2 & \cdots & m \\ r & r+1 & \cdots & m & 1 & \cdots & r-1 \end{array} \right)

    But I can't figure out what will be r here?
    Last edited by x3bnm; December 15th 2012 at 02:12 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: What is the permutation of pi?

    "pi" here just represents an arbitrary permutation, it's just a "variable symbol" (like x, or y, or n), and does not refer to a SPECIFIC permutation (it's just often used as a "typical permutation" because "pi" is the greek letter corresponding to "p" for "permutation").

    let me elaborate on what Mr. Pinter is getting at:

    a given permutation, like say (1 2 3) in S3, can be written as a product of transpositions in more than one way:

    (1 2 3) = (1 3)(1 2)
    (1 2 3) = (2 3)(1 3)
    (1 2 3) = (1 2)(1 3)(1 2)(1 3)

    or, even more trivially:

    (1 2 3) = (1 3)(1 2)(1 2)(1 2)

    note that all of these have an EVEN number of transpositions in the product (2 for the first 2, 4 for the second 2).

    but...how do we know there is NO way to write (1 2 3) as a product of 7 transpositions, or 5, or 23? that is, how do we know the PARITY of the number of transposition factors is invariant? (parity is just a fancy word for "even- or odd-ness").

    this is not so obvious...there are clearly an infinite number of ways to write any permutation as a product of 2-cycles (we can always insert a pair (a b)(a b) in-between any such product to get a new one equal to the old one), so a direct proof is not going to be easy.

    the way this is normally proved is to use a very special polynomial in n variables:

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

    it can be shown that for a permutation σ in Sn:

    p(x_{\sigma(1)},\dots,x_{\sigma(n)}) = \pm p(x_1,\dots,x_n)

    in particular, if σ is a transposition, then:

    p(x_{\sigma(1)},\dots,x_{\sigma(n)}) = -p(x_1,\dots,x_n)

    so if a permutation σ fixes the sign of p, it must change the sign of an even number of the factors of p, and for a permutation to be both even AND odd, we would have to have p = -p, and thus p = 0, which is clearly not the case.

    i urge you to play around with this for the case n = 3, in which case p is the polynomial:

    (x1 - x2)(x1 - x3)(x2 - x3) to see how this actually works.
    Last edited by Deveno; December 15th 2012 at 02:39 PM.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: What is the permutation of pi?

    Quote Originally Posted by Deveno View Post
    "pi" here just represents an arbitrary permutation, it's just a "variable symbol" (like x, or y, or n), and does not refer to a SPECIFIC permutation (it's just often used as a "typical permutation" because "pi" is the greek letter corresponding to "p" for "permutation").
    Thanks for clarification.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: What is the permutation of pi?

    Thanks for extra explanation. I understand the proof now completely.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: What is the permutation of pi?

    Quote Originally Posted by Deveno View Post

    ...

    the way this is normally proved is to use a very special polynomial in n variables:

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

    it can be shown that for a permutation σ in Sn:

    p(x_{\sigma(1)},\dots,x_{\sigma(n)}) = \pm p(x_1,\dots,x_n)

    in particular, if σ is a transposition, then:

    p(x_{\sigma(1)},\dots,x_{\sigma(n)}) = -p(x_1,\dots,x_n)

    ...

    Deveno you said that:

    p(x_{\sigma(1)},\dots,x_{\sigma(n)}) = \pm p(x_1,\dots,x_n)

    How did you come to that? Can you kindly tell me how did you figure that out?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: What is the permutation of pi?

    Don't worry. I figured it out. If n = 3

    p(x_1, x_2, x_3) = (x_1 - x_3)(x_2 - x_3)(x_1 - x_2) = -(-x_1 + x_3)(-x_2 + x_3)(-x_1 + x_2)


    Thanks for your insight.
    Last edited by x3bnm; December 15th 2012 at 04:13 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: What is the permutation of pi?

    suppose we look in detail at what p is when we have i = 1,2,or 3 (like i suggested above). here is what the various elements of S3 do to p(x1,x2,x3) = (x1-x2)(x1-x3)(x2-x3).

    1. the identity doesn't change a thing, we get p right back again.

    2. (1 2) switches 1 and 2, so we get: (x2-x1)(x2-x3)(x1-x3)

    = -(x1-x2)(x2-x3)(x1-x3) = -(x1-x2)(x1-x3)(x2-x3) = -p

    3. (1 3) switches 1 and 3 so we get: (x2-x3)(x3-x1)(x1-x3) = -p (the factor x1-x3 is the only one that changes sign)

    4. with (2 3) we get: (x1-x3)(x1-x2)(x3-x2) (the only sign change is x2-x3 to x3-x2).

    5. with (1 2 3) 1-->2, 2-->3, 3-->1, so we get (x2-x3)(x2-x1)(x3-x1) = (x2-x3)(-(x1-x2))(-(x1-x3))

    = -(-p) = p (we have two sign changes, which "cancel").

    6. finally with (1 3 2) we get: (x3-x1)(x3-x2)(x1-x2) = p, like with #5 above.

    ******************

    in the general case, we just need to show that (a b) turns p to -p, for then, writing a permutation σ as a product of k transpositions, we have σ(p) = (-1)kp, and (-1)k has just two possible values: 1 and -1.

    which factors does (a b) affect?

    1. (xa-xb) which goes to (xb-xa) = -(xa-xb) <--always a change of sign.
    2. factors of the form (xa-xj) which become factors of the form (xb-xj). note this means j > a.

    now, we have 1 ≤ a < b ≤ n. this means that j might be any number from a+1 to n (except b), for a total of n-a-1 factors affected. these fall into 2 categories (the case j = b is #1 above):

    2a) j < b

    in this case (xj-xb) is a factor of p, so (xb-xj) is a change of sign.

    we have b-a-1 sign changes here (only b-2 j are less than b (but not a), and a-1 of these are less than a, and (b-2)-(a-1) = b-a-1).

    2b) j > b in this case (xb-xj) is a factor of p, so there is no sign change.

    it is easy to see that this accounts for n-b factors (and n-b + b-a-1 = n-a-1, so we've counted everything).

    3. factors of the form (xi-xb) which becomes factors of the form (xi-xa).

    again, here, we have that i might be any number from 1 to b-1 (except a), so we have a total of b-2 factors affected. again, we have two possibilities:

    3a) i < a

    in this case there is no sign change. this happens for a-1 factors.

    3b) i > a

    here we have a sign change, and there are b-a-1 factors affected ((b-2)-(a-1) = b-a-1).

    now let's count the total number of sign changes (cases 1, 2a and 3b):

    1 + (b-a-1) + (b-a-1) = 2(b-a) - 1. this is a positive odd number (b > a, so b-a is at least 1, so 2(b-a) is at least 2, so 2(b-a) - 1 is at least 1).

    this means that (a b) sends p to (-1)2(b-a) - 1p = -p.
    Thanks from x3bnm
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: What is the permutation of pi?

    Thanks Deveno.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 3rd 2009, 09:02 AM
  2. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 30th 2009, 12:31 PM
  3. Permutation Help!
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 18th 2009, 09:47 PM
  4. Permutation.......
    Posted in the Statistics Forum
    Replies: 5
    Last Post: March 24th 2008, 03:41 AM
  5. not a permutation? then how?
    Posted in the Statistics Forum
    Replies: 3
    Last Post: March 16th 2008, 12:50 AM

Search Tags


/mathhelpforum @mathhelpforum