Monday, June 10, 2024

Computations With Simple Permutation Groups

Definition:   The set of all permutations of a set S is denoted by Sym(S).

The set of all permutations of the set {1,2,...,n} is denoted by Sn

Proposition. If S is any nonempty set, then Sym(S) is a group under the operation of composition of functions.

Theorem. Every permutation in Sn can be written as a product of disjoint cycles. The cycles that appear in the product are unique.

 

Proposition. If a permutation in Sn is written as a product of disjoint cycles, then its order is the least common multiple of the lengths of its cycles.

 

Definition. Any subgroup of the symmetric group Sym(S) on a set S is called a permutation group or group of permutations.

 

Definition. A permutation is called even if it can be written as a product of an even number of transpositions, and odd if it can be written as a product of an odd number of transpositions.

 

Proposition. The set of all even permutations of Sn is a subgroup of Sn.

 

Definition. The set of all even permutations of Sn is called the alternating group on n elements, and will be denoted by An.

 

Among the most interesting entities in abstract algebra is the permutation group   In this post we look at some basic examples to get a handle on these groups.

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 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

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

t ----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 t • 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!

Suggested Problem
:

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


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

Compare to:  st, 2st , 3st , 4st, and 5st

No comments: