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.

No comments: