Wednesday, April 19, 2017

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 • t2s1 =

[1 2 3]

[2 3 1]


but t • t21s2     =

 [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 st 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’ Î such that a’t = a. Since s is onto A, $ a" Î such that a’ = a” s. Then, a = a’t = (a” st = 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 be the result above (st)  

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

No comments: