# Math Help - What is the permutation of pi?

1. ## 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?

2. ## 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.

3. ## Re: What is the permutation of pi?

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.

4. ## Re: What is the permutation of pi?

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

5. ## Re: What is the permutation of pi?

Originally Posted by Deveno

...

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?

6. ## 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)$

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

8. ## Re: What is the permutation of pi?

Thanks Deveno.