What is the permutation of pi?

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

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

--where $\displaystyle S_n$ is a symmetric group.

There's a website that tells:

PlanetMath

$\displaystyle \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 $\displaystyle r$ here?

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 S_{3}, 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:

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

it can be shown that for a permutation σ in S_{n}:

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

in particular, if σ is a transposition, then:

$\displaystyle 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:

(x_{1} - x_{2})(x_{1} - x_{3})(x_{2} - x_{3}) to see how this actually works.

Re: What is the permutation of pi?

Quote:

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.

Re: What is the permutation of pi?

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

Re: What is the permutation of pi?

Quote:

Originally Posted by

**Deveno**

...

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

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

it can be shown that for a permutation σ in S_{n}:

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

in particular, if σ is a transposition, then:

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

...

Deveno you said that:

$\displaystyle 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?

Re: What is the permutation of pi?

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

$\displaystyle 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.

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 S_{3} do to p(x_{1},x_{2},x_{3}) = (x_{1}-x_{2})(x_{1}-x_{3})(x_{2}-x_{3}).

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_{2}-x_{1})(x_{2}-x_{3})(x_{1}-x_{3})

= -(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}) = -(x_{1}-x_{2})(x_{1}-x_{3})(x_{2}-x_{3}) = -p

3. (1 3) switches 1 and 3 so we get: (x_{2}-x_{3})(x_{3}-x_{1})(x_{1}-x_{3}) = -p (the factor x_{1}-x_{3} is the only one that changes sign)

4. with (2 3) we get: (x_{1}-x_{3})(x_{1}-x_{2})(x_{3}-x_{2}) (the only sign change is x_{2}-x_{3} to x_{3}-x_{2}).

5. with (1 2 3) 1-->2, 2-->3, 3-->1, so we get (x_{2}-x_{3})(x_{2}-x_{1})(x_{3}-x_{1}) = (x_{2}-x_{3})(-(x_{1}-x_{2}))(-(x_{1}-x_{3}))

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

6. finally with (1 3 2) we get: (x_{3}-x_{1})(x_{3}-x_{2})(x_{1}-x_{2}) = 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)^{k}p, 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.

Re: What is the permutation of pi?