Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

PERMUTATION GROUPS
DEFINITION 1: Let S be a finite set
...

Let f be a permutation on a set S  a1 , a 2 ,
...
Then f is denoted by

 a1
f  
 f a1 

a2
...

f a2 
...

The identity mapping on S is known as the identity permutation
...
Then the set of all permutations on S

Let

2
3

3  1 2
, 
2   2 1

3  1 2 3  1
, 
, 
3   2 3 1  3

2
1

3  1
, 
2   3

2
2

is

3 

...
,an 
...

( f  g )a2 
...


an

NOTE 2: The multiplication of permutations is nothing but composition of two bijective
mappings on a set
...
As a
result, multiplication of permutations is not, in general, commutative
...
g  
1

2
3

2
2

3
 , then
1

3
1
 but g
...
So f
...
f
...

3 
1

3
...
an 
,
f a2 
...
f (an ) 

...

3   2 3 1

THEOREM 1: Let S be a set with n elements
...

PROOF: Since composition of two bijective mappings from S onto S is again a bijective
mapping from S onto S,  f, g  T, f
...
So multiplication of permutations is a binary
operation on T
...

The identity mapping i: S  S defined by i(x) = x, is the identity element of T under
‘
...
i = i
...

For every f  T, the inverse permutation f

1

is the inverse of f under ‘
...


Hence, (T,
...

REMARK 2: The above group is known as the SYMMETRIC GROUP of DEGREE n and
is denoted by S n
...

EXAMPLE 2:

1
S 3  
1

2
2

3 1
, 
3 1

2
3

3  1 2
, 
2   2 1

3 1 2 3  1
, 
, 
3  2 3 1  3

2
1

3  1
, 
2   3

2
2

3 

...
,an 
...
,air 
...
,air  S such that f ai1  ai2 ,

 

f ai2  ai3 , …
...
,air
...

which is a 2-cycle, 
 2 3 4 1

DEFINITION 4: A cycle of length 2 is called a TRANSPOSITION
...

PROOF: Let S  a1 , a2 ,
...
Since S is a
finite set,

f (a1 ), f 2 (a1 )  ( f  f )(a1 ),
...
cannot all be distinct
...
Then



p1  a1 , f (a1 ),
...


If r = n, the f itself is a cycle and the result is proved
...
, f



If for some x  S  a1 , f (a1 ),
...




(a1 ) , f ( x)  x, we choose am to be first

element among a 2 , a3 ,
...

Arguing as before we get the least positive integer t such that f t (am )  am and thus





obtain a t-cycle p2  am , f (am ),
...
Then p1 and p2 are disjoint cycles
...

If r + t < n, then we proceed as before
...

Consequently the theorem is proved
...

THEOREM 3: Every r-cycle (r  2) can be expressed as product of transpositions
...
,ar   a1 , ar a1 , ar 1 
...

EXAMPLE 4: Express the following permutations as product of cycles
...


1)

1
f  
5

2
7

3 4 5 6 7 8 9
 in S9
...

7 

4
4

8
2

9
 in S9
...

1 2 3 4
2)   
4 7 3 1

5
9

6
6

7
8

8
2

9
 = (1, 4) (2, 7, 8) (5, 9) [product of disjoint
5 

cycles]
= (1, 4) (2, 8) (2, 7) (5, 9) [expressed as product of transpositions]
...

7 

REMARK 5: Every transposition is self-inverse
...
For example, on the set S = {a, b, c, d, e, f}, The
a b c d
identity permutation 
a b c d

e
e

f
f


 = (a, b) (a, b) = (a, b) (a, b) (d, f) (d, f) or


likewise
...


PERMUTATION GROUPS

Page 4

EXAMPLE 5: In Example 4 above, f and  are even permutations whereas  is an odd
permutation
...

REMARK 7: Product of two even or two odd permutations is even
...
Inverse of an odd or even permutation is odd
(respectively even), because product of a permutation and its inverse is the identity
permutation which is even
...
Then the number of even
permutations on S is equal to the number of odd permutations on S
...
Let 
be a transposition on S
...

Let us define a mapping : E  O by () = 
...

Therefore,  is an injective mapping
...

Therefore,  is surjective
...

Since, E and O are finite sets, they have same number of elements
...

PERMUTATION GROUPS

Page 5

THEOREM 5: The set of all even permutations on a finite set T with n elements is a
subgroup of Sn
...
Let iT be the identity
permutation on T
...
So W  
...

For any ,  W,  W since product of two even permutations is even
...

Hence W is a subgroup of Sn
...

REMARK 8: The above subgroup of Sn is known as the ALTERNATING GROUP of
degree n and is denoted by An
...

2

Page 6



---