## Friday, December 19, 2008

### Some Fun with Transpositions

Various aspects of math can provide hours of fun, and amusement. One of these entails transpositions. Some basics on transpositions (and even and odd permutations) first:

A transposition is a permutation which interchanges two numbers and leaves the others fixed. The inverse of a transposition T is equal to the transposition T itself, so that:

T2 = I (identity permutation, e.g the permutation such that I(i) = i for all i = 1,...n)

A permutation p of the integers {1, . . . n} is denoted by

[1 .. . .. n]

[p(1).. p(n)]

So that, for example:

[1 2 3]

[2 1 3]

denotes the permutation p such that p(1) = 2, p(2) = 1, and p(3) = 3.

Now, let's look at EVEN and ODD permutations:

Let P_n denote the polynomial of n variables x1, x2……xn which is the product of all the factors x_i … xj with i < j. That is,

P_n(x1, x2... . xn) = P(x_i .. x_j)

The symmetric group S(n) acts on the polynomial P_n by permuting the variables. For p C S(n) we have:

P_n( x_p(1), x_p(2). . .x_p(n)) = (sgn p) P_n (x_1, x_2…..x_n)

where sgn p = +/-1. If the sign is positive then p is called an even permutation, if the sign is negative then p is called an odd permutation. Thus: the product of two even or two odd permutations is even. The product of an even and an odd permutation is odd.

Back to transpositions!

We just saw:

[1 2 3]

[2 1 3]

The above permutation is actually a transposition 2 <-> 1 (leaving 3 fixed).

Now, let p' be the permutation:

[1 2 3]

[3 1 2]

Then pp' is the permutation such that:

pp'(1) = p(p'(1)) = p(3) = 3

pp'(2) = p(p'(2)) = p(1) = 2

pp'(3) = p(p'(3)) = p(2) = 1

It isn’t difficult to ascertain that: sgn (ps) = (sgn p) (sgn s)

so that we may write:

pp' =

[1 2 3]

[3 2 1]

Now, find the inverse p^-1 of the above. (Note: the inverse permutation, denoted by p^-1 is defined as the map: p^-1 : Zn -> Zn),

Since p'(1) = 3, then p ^-1(3) = 1

Since p'(2) = 1 then p^ -1(1) = 2

Since p'(3) = 2 then p^ -1(2) = 3

Therefore:

p^-1 =

[1 2 3]

[ 2 3 1]

Problem: Express

p =

[1 2 3 4]

[2 3 1 4]

as the product of transpositions, and determine the sign (+1 or -1) of the resulting end permutation.

Let T1 be the transposition 2 <-> 1 leaving 3, 4 fixed, so:

T1 p =

[1 2 3 4]

[1 3 2 4]

Let T2 be the transposition 2 <-> 3 leaving 1, 4 fixed, so:

T2 T1 p =

[1 2 3 4]

[1 2 3 4]

Then:

T2 T1 p = I (identity)

TWO transpositions (T1, T2) operated on p, so that the sign of the resulting permutation (to reach identity) is +1

The permutation is even.