Thread: What is the permutation of pi?

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

"If , then cannot be both an odd permutation and an even permutation."

--where is a symmetric group.

There's a website that tells:

PlanetMath



But I can't figure out what will be here?

"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 S₃, 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:



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



in particular, if σ is a transposition, then:



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:

(x₁ - x₂)(x₁ - x₃)(x₂ - x₃) to see how this actually works.

Originally Posted by Deveno

"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.

Thanks for extra explanation. I understand the proof now completely.

Originally Posted by Deveno

...

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



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



in particular, if σ is a transposition, then:



...

Deveno you said that:



How did you come to that? Can you kindly tell me how did you figure that out?

Don't worry. I figured it out. If




Thanks for your insight.

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 S₃ do to p(x₁,x₂,x₃) = (x₁-x₂)(x₁-x₃)(x₂-x₃).

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

2. (1 2) switches 1 and 2, so we get: (x₂-x₁)(x₂-x₃)(x₁-x₃)

= -(x₁-x₂)(x₂-x₃)(x₁-x₃) = -(x₁-x₂)(x₁-x₃)(x₂-x₃) = -p

3. (1 3) switches 1 and 3 so we get: (x₂-x₃)(x₃-x₁)(x₁-x₃) = -p (the factor x₁-x₃ is the only one that changes sign)

4. with (2 3) we get: (x₁-x₃)(x₁-x₂)(x₃-x₂) (the only sign change is x₂-x₃ to x₃-x₂).

5. with (1 2 3) 1-->2, 2-->3, 3-->1, so we get (x₂-x₃)(x₂-x₁)(x₃-x₁) = (x₂-x₃)(-(x₁-x₂))(-(x₁-x₃))

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

6. finally with (1 3 2) we get: (x₃-x₁)(x₃-x₂)(x₁-x₂) = 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. (x_a-x_b) which goes to (x_b-x_a) = -(x_a-x_b) <--always a change of sign.
2. factors of the form (x_a-x_j) which become factors of the form (x_b-x_j). 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 (x_j-x_b) is a factor of p, so (x_b-x_j) 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 (x_b-x_j) 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 (x_i-x_b) which becomes factors of the form (x_i-x_a).

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) - 1}p = -p.

Thanks Deveno.