Discrete Mathematics

Module-5
Introduction to Groups Theory

1
 Group Theory
Group Theory is a branch of mathematics and abstract
algebra that defines an algebraic structure named as
group.

Generally, a group comprises of a set of elements and an

operation over any two elements on that set to form a third
element also in that set.

In 1854, Arthur Cayley, the British Mathematician, gave the

modern definition of group for the first time −
“A set of symbols all of them different, and such that the
product of any two of them (no matter in what order), or
the product of any one of them into itself, belongs to the
set, is said to be a group. These symbols are not in
general convertible [commutative], but are associative.”
For instance, the set of integers and the addition operation
form a group.

That means, in simple words, a group is a combination of

a set and binary operation.
 Examples of groups

• 1)The set ᴢ (set of integers),R(set of real numbers),Q(set

of rational numbers),C (Set of complex numbers) are all
groups under usual addition +.

• 2)The set of all real valued functions with domain R

under function addition is a group.

• 3)The set of n x n matrices with real entries under

matrix addition is a group.
 Terminology of Groups
[Link] Group or Commutative Group
(G; ⋆) is said to be an abelian group, or a commutative group is a binary
operation that satisfies the commutative law, i.e., a ⋆ b = b ⋆ a for all a, b
∈ G.

[Link] Group
If the set G satisfies only closure law and associative law, then G is
called a semi-closed group or semi group.

[Link] and Infinite Group

In a group, G contains only a finite number of elements, then group G is
called a finite group; The group G = {1, 2, 3, 4, 5, 6, 7} under
multiplication modulo 8 otherwise, group G is called an infinite group,
The group (I, +).
Order of a group: The number of elements in a finite group G is called
the order of a group and is denoted by O(G). That means if the number
of elements in G is n, then O(G) = n.
 Klein 4-group
The Klein 4-group is an Abelian group. It is the smallest non-
cyclic group. It is the underlying group of the four-element
field.

The Klein 4-group consists of three elements i, j, k, and an

identity e. Every element is its own inverse, and the product
of any two distinct non-identity elements is the remaining non-
identity element and the group operation is typically denoted
as addition modulo 2.

Thus the Klein 4-group admits the following elegant

presentation:
and is often symbolized by the letter V or as
 Elements and Operation

The Klein 4-group is typically represented as

Where: e is the identity element.

a, b, and c are elements such that a ≠ b ≠ c ≠ e

The group operation is defined as:

a*a= e a*c= b
b*b= e b*a= c
c*c= e c*b= a
a*b= c e*x = x*e = x for all x ∈ V4
b*c= a
c*a= b
 Cayley Table

The Cayley table (or group table) for the Klein 4-group is
given below.
This table shows the result of the group operation for each
pair of elements.
 Properties

Abelian: The Klein 4-group is abelian, meaning that the

group operation is commutative.
x∗y = y∗x ∀ x, y∈ V

Order: Each element of V4 has order 2, meaning that

combining an element with itself yields the identity element.
x∗x=e ∀x ∈ V4

Identity Element: The identity element e satisfies

e ∗ x = x ∗ e = x for all x ∈ V4 .
Example

Consider a group V4={(0,0),(1,1),(0,1),(1,0)} under

component-wise addition modulo 2:
The identity element is (0,0)(0,0).
Each element is its own inverse:
(0,0)+(0,0)=(0,0)
(1,1)+(1,1)=(0,0)
(0,1)+(0,1)=(0,0)
(1,0)+(1,0)=(0,0)
 Applications

The Klein 4-group appears in various areas of mathematics,

including:

Geometry: Symmetries of a rectangle or other objects.

Algebra: Direct product of groups, automorphism groups.

Coding Theory: Binary operations and error

detection/correction.

Cryptography: Simple examples of group-based

cryptographic schemes.
Ex [Link] Group Properties

Verify that V4={e,a,b,c} is indeed a group.

Closure: The operation ∗ on V4 produces elements that are

within V4 . For all combinations, the results are e, a, b, or c,
which are in V4 .

Associativity:We need to verify that for any x,y,z∈V4:

:(x∗y)∗z=x∗(y∗z)
For instance, checking for a few cases:
(a∗b)∗c=c∗c=e
a∗(b∗c)=a∗a=e
Both sides equal e. Similar checks can be done for other
combinations.
Identity: The identity element e satisfies:
e∗x=x∗e=x for all x ∈ V4

Inverses: Each element is its own inverse:

x∗x=e for all x∈V4 .

Thus, V4 satisfies all group axioms.

Ex [Link] All Subgroups
List all the subgroups of the Klein 4-group V4.

Solution: A subgroup must itself be a group. The possible

subgroups of V4 include:

[Link] Subgroup: {e}

[Link] of Order 2:
1.{e,a} (since a∗a=e)
2.{e,b} (since b∗b=e)
3.{e,c} (since c∗c=e)

[Link] Group Itself: V4​={e,a,b,c}

Thus, the subgroups of V4 are:{e},{e,a},{e,b},{e,c},V4
 Additive group of integers modulo n

Definition
Let n be a positive integer. The group of integers modulo n is
an abelian group defined as follows:

• Its underlying set is the set { 0,1,2,……,n-1 }

• The rule for addition in the group is as follows.

If the integer sum a + b is between 0 and n - 1, then the sum
is defined as equal to the integer sum.

If the integer sum a + b is at least n, then the sum is defined

as a + b - n.
• The identity element of the group is 0.

• The inverse map in the group is defined as follows:

the additive inverse of 0 is 0, and the additive inverse of
any other a is, as an integer, n - a.

• The group of integers modulo n is a concrete description

of the cyclic group of order n.

This group is typically denoted as (Z/nZ,+) or simply (Z/nZ).

It is also sometimes denoted as Cn.

Here are the multiplication tables (more aptly called addition
tables, because the group is abelian and the operation is more
typically called addition) for the group of integers mod n for
small values of n:
What is a congruence class?
The congruence class of a modulo n, denoted [a], is the set of
all integers that are congruent to a modulo n;
i.e., [a] = {z ∈ Z | a − z = kn for some k ∈ Z} .

What is the formula for congruence modulo?

We say integers a and b are "congruent modulo n" if their
difference is a multiple of n. For example, 17 and 5 are
congruent modulo 3 because 17 - 5 = 12 = 4⋅3, and 184 and
51 are congruent modulo 19 since 184 - 51 = 133 = 7⋅19. We
often write this as 17 ≡ 5 mod 3 or 184 ≡ 51 mod 19.

Whether 17 is congruent to 5 modulo 6,

and Whether 24 and 14 are congruent modulo [Link] or no
 Cyclic Group

A cyclic group is a group that can be generated by a single

element. Every element of a cyclic group is a power of some
specific element which is called a generator.

Definition of a Cyclic Group:

A group G is cyclic if there exists an element g∈G such that
every element in G can be written as g^k (for additive groups,
as k⋅g), where k is an integer.
This element g is called a generator of the group, and we
denote the cyclic group generated by g as ⟨g⟩.

If G is a group and g∈G, then the subgroup generated by

g is g ={gn|n∈Z}.
 Properties of Cyclic Groups
[Link] cyclic group is Abelian:The group operation is
commutative.

[Link] of the Group: The number of elements in the group.

If the order is n, then g^n =e (the identity element).

[Link] of Cyclic Groups: Every subgroup of a cyclic

group is cyclic.

[Link]: An element g of order n generates a cyclic

group of order n.
Example
The set of complex numbers {1,−1,i,−i}
under multiplication operation is a cyclic group.
we need to demonstrate two things:

[Link] set forms a group under multiplication.

[Link] group is cyclic, meaning there is an element that

generates all other elements through repeated
multiplication.
1. Verifying the Group Structure

To verify that {1, -1, i, -i} forms a group under multiplication,

we need to check the group axioms:

•Closure: The product of any two elements in the set must

also be in the set.

•Associativity: Multiplication of complex numbers is

associative.

•Identity Element: The set must contain an identity element.

•Inverse Elements: Each element in the set must have an

inverse within the set.
Closure: We can verify closure by multiplying each pair of
elements and checking if the result is in the set:
• 1x1=1
• 1x(-1)=-1

Each product is in the set {1,−1,i,−i}, so the set is closed

under multiplication.
Associativity:
Multiplication of complex numbers is inherently associative,
so this property holds.

Identity Element: identity element under multiplication is 1,

and 1∈{1,−1, i, −i}.

Inverse Elements: Each element must have an inverse in the

set:
The inverse of 1 is 1.
The inverse of −1 is −1.
The inverse of i is −i (since i×−i= −1×−1=1).
The inverse of −i is i.
Thus, each element has an inverse in the set.
2. Verifying the Cyclic Nature
A group is cyclic if there exists an element (generator) such
that every other element in the group can be written as a
power of that element.
Let's consider the element i:

a generator.
Example: The group G={1, -1, i, -i} under usual
multiplication is a finite cyclic group with i as generator,

since i^1=i, i^2=-1, i^3=-i and i^4=1

 Cyclic Group

There are two generators − i and –i

as i^1=i, i^2=−1, i^3=−i, i^4=1 and also

(–i)^1=−i, (–i)^2=−1, (–i)^3=i, (–i)^4=1

which covers all the elements of the group. Hence, it is a

cyclic group.

Note − A cyclic group is always an abelian group but not

every abelian group is a cyclic group. The rational numbers
under addition is not cyclic but is abelian.
To show that U(14)={1,3,5,9,11,13} is a cyclic group
generated by the element 3
we need to demonstrate that every element in U(14) can be
expressed as a power of 3 modulo 14.

First, let's understand the group U(14).

This group consists of the integers less than 14 that are
relatively prime to 14, with multiplication modulo 14 as the
group operation.

The elements are {1,3,5,9,11,13}.

3^1 ≡3(mod14)

3^2≡9(mod14)
So,
15≡1(mod14)
A cyclic group is a group that can be generated by a single
element. U(14) is a cyclic group because all of its elements
can be generated by the element 3 through its successive
powers modulo 14. Hence, U(14) with elements
{1,3,5,9,11,13} is indeed cyclic, with 3 as a generator.
(a) List the generators of Z9.
(b) List the elements of the subgroup 3 of Z27.
(c) List the generators of the subgroup 3 of Z27.

(a) The generators are the elements relatively prime to 9,

namely 1, 2, 4, 5, 7, and 8.

(b) 3 ={0,3,6,9,12,15,18,21,24}.

(c) 3 is cyclic of order 9, so its generators are the elements

corresponding to the generators 1, 2, 4, 5, 7, and 8 of Z9.

Since 27 = 3·9,
we can just multiply these generators by 3. Thus, the
generators of 3 are 3, 6, 12, 15, 21, and 24.
(a) Let G be a cyclic group of order 6. How many of its
elements generate G?
(b) Answer the same question for cyclic groups of order 5,
8, and 10.
(c) How many elements of a cyclic group of order n are
generators for that group?
(The integers and the integers mod n are cyclic) Show
that Z and Zn for n>0 are cyclic.
Z is an infinite cyclic group, because every element is a
multiple of 1(or of −1). For instance,117=117·1.

(Remember that “117·1” is really shorthand for 1+1+···+1—

1 added to itself 117times.) Infact, it is the only infinite cyclic
groupup to isomorphism.
Notice that a cyclic group can have more than one generator.
If n is a positive integer, Zn is a cyclic group of order n
generated by 1.
For example,1generatesZ7,
since 1+1=2 1+1+1=3 1+1+1+1=4 1+1+1+1+1=5
1+1+1+1+1+1=6 1+1+1+1+1+1+1=0
In other words, if you add 1 to itself repeatedly, you
eventually cycle back to 0.
Notice that 3 also generates Z7:
3+3=6
3+3+3=2
3+3+3+3=5
3+3+3+3+3=1
3+3+3+3+3+3=4
3+3+3+3+3+3+3=0
The“same”group can be written using multiplicative notation
this way: Z7={1,a,a2,a3,a4,a5,a6}.

In this form, a is a generator of Z7.

It turns out that in Z7={0,1,2,3,4,5,6},every n on zero

element generates the group.

On the other hand, in Z6={0,1,2,3,4,5},only 1 and 5

generate.
Determine the Number of Elements of Order 3 in a Non-
Cyclic Group of Order 57
A group G of order 57 means ∣G∣=57.

By the definition of group order, the number of elements in

G is 57.

The order of the group, 57, can be factored into primes:

57=3×19

For G of order 57:subgroups of order 3^1=3.

subgroups of order 19^1=19.
Out of these, the numbers that are congruent to 1mod 3 are
1and 19.
n 3 ≡1 (mod 3)
n3 divides 19The divisors of 19 are 1 & 19.
Therefore, n3 can be either 1 or 19.
Since G is non-cyclic, it cannot have a unique Thus, n3 must
be 19.

Now, observe that if g∈G, then the order of g is 1, 3, or 19.

Note that since G is not a cyclic group, the order of g cannot

be 57.

Therefore, the number of elements of order 3 is 57−19=38.

Note that there are 38 elements of order 19 and the identity

element is the only element of order 1.
Prove that a Group of Order 217 is Cyclic and Find the
Number of Generators

The order of a group G, denoted ∣G∣, is 217. We know that

217 factors as 217=7×31.
Multiplicative group of Integers modulo-p
The multiplicative group modulo p is the set of p−1 elements
{1,2,…,p−1} under the group operation multiplication modulo
p, where p is a prime.

"multiplicative" = we only care about multiplying the

elements.

"modulo p" = we do our multiplication operations modulo p.

"group" = it has the properties of a group.

Note that there is no zero in the set, that all the elements are
pairwise incongruent to each other modulo p, and that no
element is divisible by or has a common factor with p.
Multiplicative group of Integers modulo-p

It satisfies the five axioms for an Abelian group.

G1 Closure. Any two elements in the set multiplied together
modulo p give another element in the set.
G2 Identity. The number 1 is the multiplicative identity and
gives 1⋅x=x=x⋅1 for any x in the set.
G3 Inverses. Every element x in the set has a corresponding
inverse element x−1 in the set such that
xx−1=1=x−1x(mod p).
G4 Associativity. For any elements a,b,c in the set,
a(bc)=(ab)c(modp).
G5 Commutativity. For any two elements a,b in the set,
ab=ba(modp).
Order of the Group
Definition:
The order of a group is the number of elements in the group.

Order of Multiplicative Group Modulo-p:

For a prime p, the order is p-1.

Primitive Roots
A primitive root modulo p is an integer g such that every
number in {1, 2, ..., p-1} can be written as gᵏ mod p for some
integer k.

Example:
For p=5, 2 is a primitive root since 2¹ ≡ 2 mod 5, 2² ≡ 4 mod 5,
2³ ≡ 3 mod 5, 2⁴ ≡ 1 mod 5.
 Applications

Cryptography:
Diffie-Hellman Key Exchange: Uses properties of
multiplicative groups for secure key exchange.

RSA Encryption: Relies on the difficulty of factoring

large numbers.

Number Theory:
Studying properties of numbers and their relationships.
 Problems & Solutions
Problem: Verify if 2 is a primitive root modulo 7.
Solution:
We need to check if 2^k mod 7 produces all integers from 1
to 6 for k = 1, 2, ..., 6.
2^1 ≡ 2 mod 7
2^2 ≡ 4 mod 7
2^3 ≡ 8 ≡ 1 mod 7
2^4 ≡ 16 ≡ 2 mod 7
2^5 ≡ 32 ≡ 4 mod 7
2^6 ≡ 64 ≡ 1 mod 7

Since 2 does not produce all numbers from 1 to 6, it is not a

primitive root modulo 7.
 Problems & Solutions

Problem: Find the order of the element 3 in the

multiplicative group modulo 7.
Solution:
We need to find the smallest positive integer k such that 3^k ≡
1 mod 7.
3^1 ≡ 3 mod 7
3^2 ≡ 9 ≡ 2 mod 7
3^3 ≡ 27 ≡ 6 mod 7
3^4 ≡ 81 ≡ 4 mod 7
3^5 ≡ 243 ≡ 5 mod 7
3^6 ≡ 729 ≡ 1 mod 7
Therefore, the order of 3 modulo 7 is 6.
 Introduction to Cosets
Definition: A coset is a subset formed by multiplying a fixed
element with each element of a subgroup.

Importance: Cosets help in understanding the structure of

groups and in proving theorems like Lagrange's theorem.

Group G: A set with a binary operation that satisfies closure,

associativity, identity, and invertibility.

Subgroup H: A subset of G that is also a group under the

same operation.
 Introduction to Cosets
Left Cosets
Definition: A left coset of a subgroup H in G with respect to
an element g in G is the set gH = {gh | h ∈ H}.

Example: If G = Z6 and H = {0, 3}, then 2H = {2+0, 2+3} =

{2, 5}.

Right Cosets
Definition: A right coset of a subgroup H in G with respect
to an element g in G is the set Hg = {hg | h ∈ H}.

Example: If G = Z6 and H = {0, 3}, then H2 = {0+2, 3+2} =

{2, 5}.
 Introduction to Cosets
Properties of Cosets:
Partition of the Group: Cosets of a subgroup H partition the
group G.

Equivalent Cosets: Two left cosets g1H and g2H are either
disjoint or identical.

Example 1: G = Z12, H = {0, 4, 8}, left coset 3H = {3, 7,

11}.

Example 2: G = S3, H = {(), (12)}, left coset (13)H = {(13),

(123)}.
 Introduction to Cosets
Left Cosets
Definition: A left coset of a subgroup H in G with respect to
an element g in G is the set gH = {gh | h ∈ H}.

Example: If G = Z6 and H = {0, 3}, then 2H = {2+0, 2+3} =

{2, 5}.

Right Cosets
Definition: A right coset of a subgroup H in G with respect
to an element g in G is the set Hg = {hg | h ∈ H}.

Example: If G = Z6 and H = {0, 3}, then H2 = {0+2, 3+2} =

{2, 5}.
 Lagrange theorem
Lagrange theorem is one of the central theorems of abstract
algebra.

It states that in group theory, for any finite group say G,

the order of subgroup H of group G divides the order of
G. The order of the group represents the number of
elements.

Lagrange Theorem Statement

As per the statement, the order of the subgroup H divides

the order of the group G. This can be represented as;
|G| = |H|
 Lagrange theorem
Lemma 1: If G is a group with subgroup H, then there is a
one to one correspondence between H and any coset of H.

Lemma 2: If G is a group with subgroup H, then the left

coset relation, g1 ∼ g2 if and only if g1 ∗ H = g2 ∗ H is an
equivalence relation.

Lemma 3: Let S be a set and ∼ be an equivalence relation on

S. If A and B are two equivalence classes with A ∩ B = ∅,
then A = B.
Lagrange’s Theorem
Exercise.
Suppose that H and K are subgroups of G and assume that
|H| = 9, |K| = 6, |G| < 50.

What are the possible values of |G|?

LCM(9,6) = 18, so |G|=18 or 36

Proof of Lagrange Statement:

Suppose there is a finite group G which has an order m, and

it also has a subgroup that has an order n.

Now we will consider the coset breakdown of group G

related to H. Now we will assume that each coset of aH is
made of n different elements.

Suppose H = {h1, h2, h3, …, hn}, then ah1, ah2, ah3, ….,
ahn will be known as the n distinct members of aH.

Now we will assume ahi=ahj⇒hi=h, which is the

cancellation law of group G. Since, we know that group G is
a finite group.
That's why the number of discrete left coset will also be
finite, says p. So, np will be used to indicate the total number
of elements of all cosets.
In graph G, the total number of elements will also be equal to
np. Hence, m = np.
p = m /n

Here n is the order of subgroup H, and m is the order of

finite group G.

The above equation shows that the order of subgroup is a

divisor of the order of subgroup H. It will also show that the
index p is also a divisor of the order of group G.

Hence proved, |G| =|H|

Important Notes:

[Link] to this law, the order of group G will be

dividend of the order of subgroup H.

[Link] there is a group G that has a finite order m, the order of

group G will be divided by order of any a ∈ G and, in
particular, a^m = e.

[Link] prime order is contained by the order of finite group G,

the group will not have any proper subgroups.

[Link] there is a group that has prime order, then that group will
be a cyclic group.
Isomorphism and Homomorphism
In group theory, an Isomorphism is a bijective (one-to-one
and onto) function between two groups that preserves
the group operation.
If there exists an isomorphism between two groups, we say
that the groups are isomorphic.

Isomorphic groups are structurally identical, meaning they

have the same group structure despite potentially different
elements and operations.

In group theory, a Homomorphism is a function between

two groups that preserves the group operation. While an
isomorphism is a special type of homomorphism that is
bijective, homomorphisms do not necessarily need to be
bijective.
Isomorphism
A group homomorphism that is bijective; i.e., injective and
surjective. Its inverse is also a group homomorphism.

In this case, the groups G and H are called isomorphic; they

differ only in the notation of their elements (except of identity
element) and are identical for all practical purposes.
I.e. we re-label all elements except identity.
f is one-one
f is onto
f is homomorphism i.e. f(a + b) = f(a) * f(b) ∀ a, b ∈ G.
Examples –

1. f(x)=log(x) for groups (R+,*) and (R,+) is a group

isomorphism.
Explanation –
f(x)=f(y) => log(x)=log(y) => x=y , so f is one-one.
f(R+)=R , so f is onto.
f(x*y)=log(x*y)=log(x)+log(y)=f(x)+f(y) , so f is a
homomorphism.

Moreover one can see that any homomorphism maps identity

to identity and Inverses to inverses .
Monomorphism
A group homomorphism that is injective (or, one-to-one); i.e.,
preserves distinctness.

A morphism f :X → Y of a category C is called a

monomorphism if the induced function f∗ :Mor(Z,X) →
Mor(Z,Y) is injective for each object Z of C.

Epimorphism
A group homomorphism that is surjective (or, onto); i.e.,
reaches every point in the codomain.

A morphism f :X → Y of a category C is called an

epimorphism if the induced function. f. ∗ :Mor(Y,Z) →
Mor(X, Z) is injective for each object Z of C.
Endomorphism
A group homomorphism, h: G → G; the domain and
codomain are the same. Also called an endomorphism of G.

For example, an endomorphism of a vector space V is a linear

map f: V → V, and an endomorphism of a group G is a group
homomorphism f: G → G.

Automorphism
A group endomorphism that is bijective, and hence an
isomorphism.
The set of all automorphisms of a group G, with functional
composition as operation, itself forms a group, the
automorphism group of G.

It is denoted by Aut(G).
For a group (G,+), a mapping f : G → G is called
automorphism if
f is one-one.
f homomorphic i.e. f(a +b) = f(a) + f(b) ∀ a, b ∈ G.

Examples –

1. For any group (G,+) an identity mapping Ig: G → G, such

that Ig(g)=g , ∀g ∈ G is an automorphism.
Explanation-

as if I(a)=I(b) => a=b so I is one-one.

as I(a+b) =a+b =I(a)+I(b), so I is also a homomorphism.
 Permutation groups
A permutation group is a subgroup of a symmetric group;
that is, its elements are permutations of a given set.

It is thus a subset of a symmetric group that is closed under

composition of permutations, contains the identity
permutation, and contains the inverse permutation of each
of its elements.
Permutation groups
Permutation groups
Permutation groups
Permutation groups
 Permutation of a Set

Let A be the set { 1, 2, …, n }.

A permutation on A is a function
f:A→A
that is both one-to-one and onto.

The set of all permutations on A is denoted by Sn

A permutation is represented by a matrix :

 1 2 ……. n 
f = 
 f (1) f (2) ……. f (n) 
 Examples of Permutation

Let A be the set { 1, 2, 3, 4, 5 }

1 2 3 4 5
f = 
3
 5 1 2 4 

1 2 3 4 5
g= 
4
 2 5 3 1
f and g are elements of S5
Permutation groups
Permutation groups
Permutation groups
Permutation groups
Product of Permutations

The product of f and g is the composition function

f。g

1 2 3 4 5 1 2 3 4 5
f ∘g =    
 5 1 2 
3 4 4 1
2 5 3 

1 2 3 4 5
f ∘g =  
2 ? ? ? ? 
 Cycles : A special kind of Permutation

An element f of Sn is a cycle (r-cycle) if there exists

{ i1 , i 2 ,… . , i r }  { 1, 2,… … , n }
such that
f (i1 ) = i2 , f (i2 ) = i3 ,… . , f (ir−1 ) = ir , f (ir ) = i1
and f (m) = m for all other m {i 1 ,i2 ,…...,ir }

Cycles will be written simply as (i1, i2, ... , ir)


Example : 
1 2 3 4 5
=(1, 3, 4)
3 2 4 1 5
 
Cycles : A special kind of Permutation
Cycles : A special kind of Permutation
Cycles : A special kind of Permutation
Cycles : A special kind of Permutation
 Permutations and cycles
Every permutation can be written as a product of disjoint cycles.

For example
1 2 3 4 5 6 7 8 9
f = 
3 8 2 6 7 4 9 1 5 
We have
1→3→2 →8→1
4→6→4
5→7→9→5
We can easily verify that
f = (1, 3, 2, 8)(4, 6)(5, 7, 9)
 Example

• Factor

 1 2 3 4 5 6 7 8 9 10 11 12 13 
 = 
 5 12 2 1 9 11 4 3 7 10 13 8 6 

as a product of (pairwise) disjoint cycles.

=(1, 5, 9, 7, 4)(2, 12, 8, 3)(6, 11, 13)
 Transpositions : A special kind of cycles

A 2-cycle such as (3, 7) is called a transposition

◼ Every cycle can be written as a product of

transposition :
(i1, i2, ... , ir) = (i1, ir)(i1, ir-1) ... (i1, i3)(i1,
i2)
For example,
(1, 3, 2, 4) = (1, 4)(1, 2)(1, 3)
 Transposition
• A cycle of length 2 is called a transposition.
• Thus each transposition  has the form =(m,
n), where m≠n.

1 2 3  1 2 3
(1 2)(2 3) = 
2 1 3 
 1 3 2 

1 2 3
=  = (1 2 3)
2 3 1
 Permutations and transpositions

Since every permutation can be expressed as a product of (disjoint)

cycles, every permutation can be expressed as a product of
transpositions.
For example,

1 2 3 4 5 6 7 8 9 
f = 
 3 8 2 6 7 4 9 1 5 
= (1,3,2,8)(4,6)(5,7,9)
= (1,8)(1,2)(1,3)(4,6)(5,9)(5,7)
 Product of Transposition
Theorem If a permutation f is expressed as a product of p
transpositions and also a product of q transpositions, then p and q
are either both even or both odd.

◼ Definition A permutation that can be expressed as a

product of an even number of transpositions is called
an even permutation, and is called an odd
permutation if it can be expressed a product of odd
transpositions.
 Example

(1, 2, 3) = (1, 2)(2, 3)

(1, 2, 3, 4) = (1, 2)(2, 3)(3, 4)
(1, 2, 3, 4, 5) = (1, 2)(2, 3)(3, 4)(4, 5)
(1, 2, 3, 4, 5, 6) = (1, 2)(2, 3)(3, 4)(4, 5)(5, 6)
 Even, Odd Permutations

Observe that (1,3,2,4)(1,7,6,2) = (1,7,6,4)(2,3)

So, we can write this permutation as two different product of

transpositions :
(1,3,2,4) (1,7,6,2) = (1,4) (1,2) (1,3) (1,2) (1,6) (1,7)

(1,7,6,4) (2,3) = (1,4) (1,6) (1,7) (2,3)

◼ Note that (1,2)(1,2) is an expression of the identity

mapping, so identity is an even permutation.
 Example
• Determine the parity of
1 2 3 4 5 6 7 8 9
 =
5 4 6 1 7 8 2 9 3 

• Solution:
➢ We have  = (1, 5, 7, 2, 4)(3, 6, 8, 9)
=(1,5)(5,7)(7,2)(2,4)(3,6)(6,8)(8,9)
➢ So  is odd because it has a product of 7
transpositions.
 Example

 1 2 3 4 5 .
• Find the order of  =  
 2 3 1 5 4 

• Solution:
 = (1, 2, 3)(4, 5)
|| = 6
= lcm(2, 3)
 Example

• Find the order of

1 2 3 4 5 6 7 8 9 10 11 12 13 14.
 = 
5
 7 9 14 10 11 12 8 3 13 2 6 4 1 
• Solution:
 = (1,5,10,13,4,14)(2,7,12,6,11)(3,9)
|| = lcm(6,5,2) = 30.