Page 40 - DMTH403_ABSTRACT_ALGEBRA

Unit 2: Groups

Let X be a non-empty set. We have seen that the composition of functions defines a binary Notes
operation on the set F(X) of all functions from X to X. This binary operation is associative.
I , the identity map, is the identity in F(X).
X
Now consider the subset S(X) of F(X) given by
S(X) = {f  F(X) | f is bijective }.

So f  S(X) iff f : X  X exists. Remember that f o f = f . o f = I . This also shows that f  S(X).
-1
-1
-1
-l
X
Now, for all f, g in S(X),
(g o f) o (f o g ) = I = (f o g ) o (g o f), i.e., g o f  S(X).
-1
-1
-1
-1
X
Thus, o is a binary operation on S(X).
Let us check that (S(X), o) is a group.
(i) o is associative since (fog) o h = f o (g o h)  f, g, h E S(X).
(ii) I is the identity element because f o I = I o f  f  S(X).
X
X
X
(iii) f is the inverse off, for any f  S(X).
-1
Thus, (S(X), o) is a group. It is called the symmetric group on X.
If the set X is finite, say X = (1, 2, 3 ...... n), then we denote S(X) by S,, and each f  S, is called a
permutation on n symbols.
Suppose we want to construct an element f in S . We can start by choosing f(1). Now, f(1) can
n
be any one of the n symbols 1,2, ..... n. Having chosen f(l), we can choose f(2) from the set
{ l,2 ........ n } \ { f(l) }, i.e., in (n – 1) ways. This is because f is 1 – 1. Inductively, after choosing f(i),
we can choose f(i + l) in (n – i) ways. Thus, f can be chosen in (1 × 2 × .... × n) = n ! ways, i.e.,
S contains n ! elements.
n
For our convenience, we represent f  S, by

 1 2 .......... n 
 .......... f(n) 
 f(1) f(2) 

 1 2 3 4 
For example,  2 4 3 1  represents the function f : (1, 2. 3. 4)  {1. 2, 3. 4) : f (1) = 2, f(2) = 4,
 
f (3) = 3, f (4) = 1. The elements in the top row can be placed in any order as long as the order of
the elements in the bottom row is changed accordingly.

 2 1 3 4 
Thus,   also represents the same function f.
 4 2 3 1 
Definition: We say that f  S is a cycle of length r if there are x,, ...., x, in X = { 1, 2, ....., n) such that
n
f(x ) = x for 1  i  r – 1, f(x ) = x and f(t) = t for t # x, ..., x,. In this case f is written as (x .... x,).
1
i
r
i+1
1
For example, by f = (2 4 5 10)  S , we mean f (2) = 4, f (4) = 5, f (5) = 10, f (10) = 2 and f (j) = j for
10
j # 2, 4, 5, 10.
 1 2 3 4 5 6 7 8 9 10 
i.e., f   
 1 4 3 5 10 6 7 8 9 2 

LOVELY PROFESSIONAL UNIVERSITY 33