Math Revisited: Extending Permutation Groups to Transpositions

It's also interesting to explore a permutation "offshoot" known as a transposition. 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 x ₁,  x ₂ ……x _n which is the product of all the factors  x _i .. x _j  with i < j. That is:

P  _n ( x ₁,  x ₂ ……x _n) = P(x _i .. x _j)

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

P  _n ( x_p(1), x_p(2). . .x_p(n)) = (sgn p)  P  _n ( x ₁,  x ₂ ……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 therefore even.

A Note on Disjoint Permutations:

Expressing a permutation as a product of disjoint cyclic permutations is not hard at all, once one gets the hang of it. The key is to “cycle through” the mapping in the original to yield the different disjoint cycles, taking care to stop when the end element leads to a number (on the top of the original) that repeats. For example:

Express as disjoint permutations:

[1 2 3 4  5  6   7]

[4 5 6 7  3  1  2]

Solution: 1 goes into 4, 4 goes into 7, 7 goes into 2 – STOP! (Since 2 commences new cycle in next top position). So first disjoint cycle is: (1, 4, 7, 2).

Now, 2 goes into 5, 5 goes into 3, STOP! (3 repeats) So cycle is: (2, 5, 3). Then 3 goes into 6, and 6 into 1. Stop.

Answer: (1, 4, 7, 2)(2, 5, 3)(6).

Math Revisited: Permutation Groups

Among the most interesting entities in abstract algebra is the permutation group. To fix ideas, consider the following example:

Let S = {1, 2, 3} and define the group G = {The set of all permutations on S}

a) Write out all the members of G

b) Show that G obeys group properties and determine whether or not it is Abelian

Solution::

We may first determine how many members G has using the fact the number of elements will be n = 3!

= 3 x 2 x 1 = 6.

The components to the elements can then be found:

(1,2, 3), (1, 3, 2), (3, 2, 1), (3, 1, 2), (2, 1, 3) and (2, 3, 1)


These are not the elements themselves, which must be written as (2 x 3) matrices. For example, the identity element will be: e =

[1 2 3]

[1 2 3]

The other elements we can write:

s1 =

 [1 2 3]

[2 3 1]


s2 =

[1 2 3]

[3 1 2]



t1 =

[1 2 3]

[1 3 2]



t2 =

 [1 2 3]

[3 2 1]


t3 =

 [1 2 3]

[2 1 3]


We can now prepare a group table to show the operation is binary and G meets the Group definition. We have for G = {The set of all permutations on S}:


        e---- s1--- s2--- t1 ---  t2 ---  t3
--------------------------------------------------
e  --   e  ---s1--- s2 --- t1 --- t2---  t3

s1  --s1--- s2--- e ----t2 ----t3 ----t1

 s2  --s2----e  ---s1---  t3---   t1----  t2

 t1  ---  t1-  t3-  t2 ---  e ---  s2 -----s1

t2  ----t2--- t1-- t3- - s1--- e------ s2

t3 -----t3 ---t2 ---t1 ---- s2 --- s1---- e
------------------------------------------


The shaded highlights shown are intended to emphasize the symmetries in the table (which can also be found for the s  elements).

Is G Abelian? If we check any two elements and find they don’t meet the commutative property (4) then the answer is no. By inspection:

t1 • t2 = s1 =

[1 2 3]

[2 3 1]


but t2  • t21 = s2     =

 [1 2 3]

[3 1 2]


So, the commutative property is not met, and G is not Abelian.

Other examples: Groups of permutations related to 1:1 mappings (functions).

Let A be a set and let s  and t be permutations of A so that s and t are both one-to-one functions mapping A onto A. Then the composite function is s t   and will be a permutation if it is one-to-one and onto A.

Definitional illustrations:

A)If  a1(s t) = a2(s t), then (a1s ) t = (a2 s ) t and (a1s) = (a1s ) (since t  is 1:1) and a1 = a2.

Hence (s t) is 1:1.

B) Let a  Î A , then since t is onto A, $ a’ Î A  such that a’t = a. Since s is onto A, $ a" Î A  such that a’ = a” s. Then, a = a’t = (a” s ) t = a” (s t).

Example: Let A = {1, 2, 3, 4, 5} and

s =

[1 2 3 4 5]
[4 2 5 3 1]

In this case: 1s = 4, 2s = 2, 3s = 5, 4s = 3, and 5s = 1

Now, let:

t =

[1 2 3 4 5]
[3 5 4 2 1]

Then: 1t = 3, 2t = 5, 3t = 4, 4t = 2, and 5t = 1

Then we can find  st  by matrix multiplication (for details of matrix multiplication, see http://brane-space.blogspot.com/2010/05/looking-at-matrix-groups.html ).


The result will be:

[1 2 3 4 5]
[2 5 1 4 3]

(Which the reader should be able to verify!)

Practice Exercise:

Let A = {1, 2, 3, 4, 5} and s  be the result above (st)  

Find: 1 t, 2t , 3t , 4t, and 5t

Solution Offered for Phoebe's Abstract Algebra Problem

Thanks to reader Caleb Shay, who "couldn't bear to see that poor girl suffer",  Phoebe's Abstract Algebra homework will be done on time!   Recall the statement of the problem:

Prepare the respective tables for the isomorphism and give specific examples in terms of the function φ, i.e. show specific mappings. (Where: φ(x) φ(y) = φ(xy) for example). Caleb's solution is as follows, originally appearing in an unpublished comment- but he preferred to have it displayed in the main blog (no problemo!):


"The solution included preparation of the respective addition table (in  Z₄ ) and multiplication table (in  Z₁₀ ). The addition table for Z4 is (see e.g. Fig. 1 in http://www.brane-space.blogspot.com/2012/11/looking-again-at-groups-sub-groups.html ):


+ /----0 ----1 ---2 ----3
-----------------------
0 --- 0------1 ---2 ----3

1 -----1 -----2 ---3---- 0

2 -----2 -----3--- 0 ----1

3----- 3 -----0 ---1---- 2
-----------------------------


The multiplication table in Z₁₀


-*--/----6 ----2 -----4 ----8
---------------------------
6 --- ---6------2 --- 4 ----8

2 ------2 ------4 ----8----6

4 ------4 ------8--- -6 ---2

8----- 8 -----6 ----2---- -4
-----------------------------

Since 6 *6 = 6 then the identity element in  Z₁₀  is 6.. So φ(x) φ(x) = φ(x^2) = (φ6)φ(6) =φ( I)

Then the mapping isomorphisms between the tables will be:


Φ: 0 -> 6 (identity to identity element)

Φ: 2 -> 4

Φ: 3 -> 8

Φ: 1 -> 2


So each of the numbers on the left side of the arrow is mapped to the corresponding number on the right side, and this is done using the two tables such that each element of Z₄  is mapped to each element of Z₁₀."

Phoebe’s bonus problems:

1) Let the set S3 of cycle permutations be S3 = {I1(12), (23), (13), (123), (132)}

We establish an automorphism by mapping image to domain within the set S3 itself, such that – for example:

Φ(12) = (13)

Then show the other mappings within S3.

2) Proposition:  Φ _x  is a homomorphism.   Prove it!

Hint: Show that   Φ _x(y o z) = Φ _x  (y) o  Φ _x (z)

Pemutation Groups

Permutation groups are another interesting  group category.

Let S = {1, 2, 3} and define the group G = {The set of all permutations on S}


a) Write out all the members of G

b) Show that G obeys group properties and determine whether or not it is Abelian


Solution::

We may first determine how many members G has using the fact the number of elements will be n = 3!

= 3 x 2 x 1 = 6.

The components to the elements can then be found:

(1,2, 3), (1, 3, 2), (3, 2, 1), (3, 1, 2), (2, 1, 3) and (2, 3, 1)


These are not the elements themselves, which must be written as (2 x 3) matrices. For example, the identity element will be: e =

[1 2 3]

[1 2 3]

The other elements we can write:

s1 =

 [1 2 3]

[2 3 1]


s2 =

[1 2 3]

[3 1 2]



t1 =

[1 2 3]

[1 3 2]



t2 =

 [1 2 3]

[3 2 1]


t3 =

 [1 2 3]

[2 1 3]


We can now prepare a group table to show the operation is binary and G meets the Group definition. We have for G = {The set of all permutations on S}:


        e---- s1--- s2--- t1 ---  t2 ---  t3
--------------------------------------------------
e  --   e  ---s1--- s2 --- t1 --- t2---  t3

s1  --s1--- s2--- e ----t2 ----t3 ----t1

 s2  --s2----e  ---s1---  t3---   t1----  t2

 t1  ---  t1-  t3-  t2 ---  e ---  s2 -----s1

t2  ----t2--- t1-- t3- - s1--- e------ s2

t3 -----t3 ---t2 ---t1 ---- s2 --- s1---- e
------------------------------------------



The shaded highlights shown are intended to emphasize the symmetries in the table (which can also be found for the s  elements).

Is G Abelian? If we check any two elements and find they don’t meet the commutative property (4) then the answer is no. By inspection:

t1 • t2 = s1 =

[1 2 3]

[2 3 1]


but t2  • t21 = s2     =

 [1 2 3]

[3 1 2]


So, the commutative property is not met, and G is not Abelian.

Other examples: Groups of permutations related to 1:1 mappings (functions).

Let A be a set and let s  and t be permutations of A so that s and t are both one-to-one functions mapping A onto A. Then the composite function is s t   and will be a permutation if it is one-to-one and onto A.

Definitional illustrations:

A)If  a1(s t) = a2(s t), then (a1s ) t = (a2 s ) t and (a1s) = (a1s ) (since t  is 1:1) and a1 = a2.

Hence (s t) is 1:1.

B) Let a  Î A , then since t is onto A, $ a’ Î A  such that a’t = a. Since s is onto A, $ a" Î A  such that a’ = a” s. Then, a = a’t = (a” s ) t = a” (s t).

Example: Let A = {1, 2, 3, 4, 5} and

s =

[1 2 3 4 5]
[4 2 5 3 1]

In this case: 1s = 4, 2s = 2, 3s = 5, 4s = 3, and 5s = 1

Now, let:

t =

[1 2 3 4 5]
[3 5 4 2 1]

Then: 1t = 3, 2t = 5, 3t = 4, 4t = 2, and 5t = 1

Then we can find  st  by matrix multiplication (for details of matrix multiplication, see http://brane-space.blogspot.com/2010/05/looking-at-matrix-groups.html ).


The result will be:

[1 2 3 4 5]
[2 5 1 4 3]

Which the reader should be able to verify!

Exercise: Let A = {1, 2, 3, 4, 5} and s  be the result above (st)  


Then find: 1 t, 2t , 3t , 4t, and 5t