MMT-003

ALGEBRA
Indira Gandhi National Open University
School of Sciences

Block

2
SPECIAL GROUPS AND SEMIGROUPS
Block Introduction 3
Notations and Symbols 4
UNIT 4
Matrix Groups 5
UNIT 5
Abelian Groups 27
UNIT 6
Group Presentations 57
UNIT 7
Applications of Semigroups 77
 Course Design Committee*
Prof. Gurmeet Kaur Bakshi Prof. Parvati Shastri
Deptt. of Mathematics, Centre for Excellence in Basic Sciences
Panjab University Mumbai University

Dr. Anuj Bishnoi Faculty members

Deptt. of Mathematics, School of Sciences, IGNOU
University of Delhi Dr. Deepika
Prof. K. N. Raghavan Prof. Poornima Mital
Deptt. of Mathematics Prof. Parvin Sinclair
Institute of Mathematical Sciences, Chennai Prof. Sujatha Varma
Prof. Ravi Rao Dr. S. Venkataraman
School of Mathematics
Tata Institute of Fundamental Research
Mumbai

* The course design is based on the recommendations of the Expert Committee for the programme
M.Sc (Mathematics with Applications in Computer Science).

Block Preparation Team

Prof. B. Sury (Editor & unit writer) Prof. Parvin Sinclair (Co-editor & unit writer)
Deptt. of Mathematics School of Sciences
Indian Statistical Institute, Bengaluru IGNOU
Prof. Gurmeet Kaur Bakshi
Deptt. of Mathematics
Panjab University
Course Coordinator: Prof. Parvin Sinclair

Acknowledgement: To Sh. S. S. Chauhan for the preparation of the CRC of this block.

December, 2019
© Indira Gandhi National Open University
ISBN-8]-
All right reserved. No part of this work may be reproduced in any form, by mimeograph or any other
means, without permission in writing from the Indira Gandhi National Open University.
Further information on the Indira Gandhi National Open University courses, may be obtained from the
University’s office at Maidan Garhi, New Delhi-110 068 and IGNOU website www.ignou.ac.in.
Printed and published on behalf of the Indira Gandhi National Open University, New Delhi by
Prof. M. S. Nathawat, School of Sciences.
2
BLOCK INTRODUCTION
When some special groups touch our lives,
Then suddenly we see,
How wonderful and beautiful,
The world of maths can be!

In the first block of this course, you studied group actions and applications of Sylow’s
theorems. In this block, comprising four units, we aim to take you deeper into the realm
of group theory.

To start with, in Unit 4 you will be studying groups that are subgroups of the general
linear group, GL n (K ), where K is a field. Here you will revisit some of the objects you
studied in your course, ‘Linear Algebra’, like orthogonal and unitary matrices. We will
be discussing the group of all orthogonal/unitary matrices, as well as the special linear
group, SL n (K ) . Through these groups we will also illustrate some of the concepts, like
group actions, orbits and stabilisers, that you studied in Unit 2. In Unit 4, you will also
be introduced to linear representations of groups, along with several examples.

In Unit 5, the focus is on an algebraic object that you would be familiar with, namely,
an abelian group. However, you will now see several aspects of such groups that you
would not have studied before. Here we will first discuss the structure of finite abelian
groups. Then we will look at finitely generated abelian groups and free abelian groups.
This study will help you to finally see what the algebraic structure of any finitely
generated abelian group is. This understanding will help you to decide how many
finitely generated abelian groups there can be, up to isomorphism, with a given ‘finite
part’ and a given rank.

In Unit 6, you will study a concept that is very new to you, that of a free group. You
will see how important this concept is for studying groups, in general. Then you will
study about generators of a group, and relations between them. Finally, you will see
how this understanding of group presentations will help you classify groups of certain
orders, going beyond the classification you did in Unit 3.

In the last unit of this block, Unit 7, you will study a concept that is usually not given
much weight, but has several very important applications. This is the concept of
semigroups. In this unit, you will study several properties of semigroups. You will also
study some of its important applications in the fields of computer science and
linguistics.

With this block we end our discussion on group theory. In the next block we will
concentrate on rings.

3
 NOTATIONS AND SYMBOLS

(Please go through the list of symbols on P.6 of Block 1 also.)

SL n (F) the special linear group over the field F

O( n ) the orthogonal group, a subgroup of GLn (R )
SO(n ) the special orthogonal group
U (n ) the unitary group, a subgroup of GLn (C)
SU (n ) the special unitary group
SP2 n (R ) the symplectic group, a subgroup of SL 2 n (R)

Bn (F) the set of upper triangular matrices in GL n (F)

H(H ∗ ) the set of Hamilton’s real quaternions (non-zero real quaternions)

H1 the group of real quaternions of norm 1

x,y the inner product of the vectors x and y

Zr Z × Z × K × Z (r times)
G ( p) the Sylow p-subgroup of the abelian group G
F(S) the free group on the set S
Tor(G ) the torsion subgroup of the abelian group G

X the group/semigroup generated by the set X

X R a presentation of X , with R being the set of relations among the

elements of X
Map(S , S) the set of mappings from a set S to itself
GS the group kernel/unit group of the monoid S

x , or l( x ) the length of a word x

(S , A , δ) the semiautomaton with S being the set of states, A being the input
alphabet and δ being the next-state function of S
(S, A1, A 2 , δ, λ) an automaton where (S, A, δ) is a semiautomaton, A 2 is the output
alphabet and λ is the output function
(A, G , →, g 0 ) a phase-structure grammar, with alphabet A, the set of grammar symbols
G, the set of rewriting rules → and initial symbol g 0

L(
) the language generated by

4
 Matrix Groups
UNIT 4 MATRIX GROUPS

Structure Page No.

4.1 Introduction 5
Objectives
4.2 Linear Groups 6
4.3 Orthogonal and Unitary Groups 10
4.4 Linear Representations 16
4.5 Summary 19
4.6 Solutions / Answers 19

4.1 INTRODUCTION
In the previous block you have seen how actions by, and on, finite and infinite
groups play a crucial role in so many areas of study. In this unit you will be
studying groups that act ‘linearly’. We know that linear transformations are
best studied through their ‘concrete’ cousins, matrices, which are easier to
manipulate. Therefore, if both matrices and groups come together, as in this
unit, this largesse is not to be taken lightly!

In the course ‘Linear Algebra’ (MMT-002), you have already studied a

considerable amount about different types of matrices and some
decompositions like QR and SVD. In this unit, we build on the learning you
have done there. Here we focus on some special matrix groups, namely, groups
of invertible matrices.

In Sec.4.2, we study groups of different types of non-singular matrices. In

particular, we focus on the general linear group over R or C, and its
subgroups.

In Sec.4.3, we carry this study further. Here you will specifically study
properties of the groups formed by considering all the unitary/orthogonal
matrices of size n.

In Sec.4.4, you will be introduced to a new concept, that of a linear

representation. As you will see, this is a device to represent groups by linear
groups, which are often easier to handle.

Let us now go through the specific learning objectives of this unit.

Objectives

After studying this unit, you should be able to:

• give examples, and non-examples, of linear groups;
• define symplectic, orthogonal and unitary groups;
• prove, and apply, the Gram-Schmidt orthogonalisation process;
• describe how SU (2) can be identified with the sphere S3 ;
• define, and give examples of, linear representations;
5
Special Groups and • use linear representations to prove that there is a homomorphism from
Semigroups SU (2) to SO(3).

4.2 LINEAR GROUPS

In your earlier studies, you have come across several examples of sets of
matrices over R or C which form a group under matrix multiplication. In fact,
the elements of such matrices can be from any field. Before going further,
recall what a field is. (You will study more about fields in Block 4.)

Definition: A non-empty set F, along with two binary operations ∗1 and ∗2

defined on it, is called a field if
i) (F, ∗1 ) is an abelian group;
ii) (F \ {0}, ∗2 ) is an abelian group;
iii) ∗2 is distributive over ∗1.

Now, let F be a field, as for example, Q, R or C. Then, recall the examples of

groups of matrices you have already worked with in MMT-002, and earlier.

i) The set of all n × n matrices with entries in F which have non-zero

determinant, is a group under matrix multiplication. This is called the
general linear group over F, and is denoted by GL n (F).
ii) The set of elements of GL n (F) which have determinant 1 forms a normal
subgroup of GLn (F). This normal subgroup is called the special linear
group over F, and is denoted by SL n (F) .
 a b  
For instance, SL 2 (R) =   a , b, c, d ∈ R, ad − bc = 1.
 c d  

Here are some exercises to help you re-acquaint yourselves with these groups.

E1) Apply the Fundamental Theorem of Homomorphism to show that

[GL n (C) SL n (C)]~ C ∗ .
E2) Give an example of an action of GLn (R ) on M n (R ), with justification.
Also obtain the orbits and stabilisers of the identity matrix and the zero
matrix with respect to this action.

E3) Prove that there is a bijection between GL n (F) and the set of all ordered
F-bases of the n-dimensional vector space Fn .

 a a  
E4) Show that G =   a ∈ R ∗  forms a group under matrix
 0 0  
multiplication, but it is not a subgroup of GL2 (R).

E5) i) Find a subgroup of GL 2 (R ) which is isomorphic to C∗ .

6
 ii) Show that GLn (C) is isomorphic to a subgroup of Matrix Groups
GL 2n (R ), ∀ n ∈ N.

There are several other matrix groups, which are subgroups of GLn (F) . They
form a subset of matrix groups that we now define.

Definition: A subgroup of a general linear group is called a linear group.

So, SL n (C) is a linear group and the group in E4 is not a linear group.
Some more examples of linear groups are: In the next section, you
will see the reason
i) The orthogonal group, O(n) = {A ∈ GL n (R) AA t = I}. behind the usage of the
word ‘orthogonal’,
ii) The special orthogonal group, which is a
SO(n) = O(n ) ∩ SL n (R) = {g ∈ SL n (R ) gg t = I}. generalisation of the
familiar word
[This is also called the group of rotations.] ‘perpendicular’.

iii) The unitary group, U(n) = {g ∈ GL n (C) g g t = I}.

If A = [a ij ] ∈ M n (C) ,
iv) The special unitary group, then A = [ a ij ] , where
SU(n) = U (n ) ∩ SL n (C) = {g ∈ SL n (C ) gg = I}.
t
z is the conjugate of
z∈C .

Note that an orthogonal group is a unitary group with elements from GL n (R ) .

You will study more about these groups later in this unit. For now, to help you
get used to these groups, try the following exercises.

E6) i) Check whether or not det : O(n ) → ({± 1}, ⋅) is a group

homomorphism. If it is, use it to find |O(n ) : SO(n )| . If det is not a
homomorphism, explain why it is not.
ii) Let Q be the quadratic form given by Q(v) = x 12 + L + x 2n , for
v = (x 1 , K, x n ) ∈ R n . Show that
O(n ) = {T : R n → R n : Q(T( v)) = Q( v)}.

E7) Give the geometrical representation of U (1).

E8) Show that:

 a b 2 
i) SO(2) =   a + b 2 = 1, a , b ∈ R  , and
 − b a  

ii) SO(2) ~ U (1) .

E9) Show that:

i) Z(GL n (F)) = {λI λ ∈ F*} , and

ii) Z(SL n (C)) is isomorphic to the group of nth roots of 1.

7
Special Groups and There is yet another important linear group that you shall now study.
Semigroups
  0 I  0 I 
Example 1: Consider SP2n (R) = g ∈ SL 2 n (R ) g t   g =  .
  − I 0  − I 0 
Check whether or not it is a linear group. (Here 0 and I denote the n × n zero
and identity matrices, respectively.)

Solution: Firstly, since I ∈ SP2 n (R), the given set is non-empty.

 0 I t −1 t −1
Next, let J = 
− I 0  . Then, for A ∈ SP2 n (R), A JA = J. So, (A ) JA = J.
 
Thus, A −1 ∈ SP2n (R).
Finally, you should check that if A, B ∈ SP2 n (R ), then so does AB.
Hence SP2n (R) is a linear group.
***

The linear group in Example 1 is called the symplectic group over R. The
name ‘symplectic’ was coined by the great mathematician Hermann Weyl.
Some people use the notation Sp(n ) or Sp(2n ) for SP2 n (R).
The elements of SP2n (R) are called symplectic matrices.

Now consider an interesting relationship between the symplectic groups and

the special linear groups over R.

Example 2: Prove that SP2 (R) = SL 2 (R) , but SP4 (R ) ≠ SL 4 (R).

 a b   a c   0 1   a b   0 1  
Solution: SP2 (R) =   ∈ SL 2 (R )       =   .
 c d   b d   − 1 0   c d   − 1 0  
So SP2 (R ) ⊆ SL 2 (R), by definition.
a b 
To prove the reverse inclusion, let A =   ∈ SL 2 (R). Now you should use
c d
 0 1  0 1
the fact that det(A) = 1 to check that A t   A =  . Thus,
 −1 0  −1 0
A ∈ SP2 (R ). Hence, SL 2 (R ) ⊆ SP2 (R).

For the second part of the problem to be solved, note that SP4 (R ) ⊆ SL 4 (R).
3 2 0 0
1 1 0 0
Now take A =  . Then A ∈ SL 4 (R), since det(A) = 1.
0 0 1 0
 
0 0 0 1
0 0 3 1
 1  0 I 
 0 I 0 0 2
However, A t   A =  ≠ . So A ∉ SP4 (R ).
 − I 0 − 3 2 0 0 − I 0
 
 1 −1 0 0
Hence the result.
***
8
Try some exercises now. Matrix Groups

E10) Consider the action of GLn (R ) on itself by (A, B) a At BA. Show that
Stab(I) = O(n ).

E11) Consider the action of SL 2 n (R) on itself by the action given in E9.
 0 I
Show that Stab(J ) = SP2 n (R) , where J =  .
− I 0

E12) Prove that {A ∈ GL 4 (R ) At DA = D} is a group, where D is the diagonal

matrix (1, − 1, − 1, − 1). [This group, denoted by O(1, 3), is called the
Lorentz group, and has several applications in physics and the other
sciences.]

E13) Check whether or not the following matrices are symplectic, where the
blocks are in GLn (R) :
0 − I 0 I  At 0   I B
 I 0  ,  I 0 ,  −1 
, 0 I 
    0 A   
where B = Bt and A−1 exists.

The orthogonal groups, unitary groups and symplectic groups are referred to as
the classical groups, as named by Hermann Weyl. Some subgroups of classical
groups are also important and we introduce them together in the following
example.

Example 3: Prove the following:

i) The set B n (F), of upper triangular invertible n × n matrices over a field
F is a group. (This is an example of a Borel subgroup of GLn (F),
named after the famous Swiss mathematician, Armand Borel.)
Fig. 1: Armand Borel
ii) The set Tn (F), of triangular matrices in Bn (F) whose diagonal entries
(1923-2003)
are all 1, forms a normal subgroup of Bn (F).

iii) The set Dn (F), of diagonal matrices in Bn (F), forms an abelian

subgroup of Bn (F).

iv) The set of n × n matrices with integer entries and determinant +1 is a

group (denoted by GL n (Z )), and is a subgroup of GLn (R ).

Solution: Firstly, note that all four sets are non-empty.

i) To prove that B n(F) is a group, note that for A ∈ B n (F), A−1 exists, and
1
A−1 = (Adj A).
|A|
Now, if A = [a ij ], with a ij = 0 for i > j, Adj (A ) = [bij ] , with bij = 0 for
i > j. Thus, A −1 ∈ B n (F) also.
9
Special Groups and Finally, if A, B ∈ Bn (F), then you can check that AB ∈ Bn (F).
Semigroups Thus, Bn (F) ≤ GL n (F).
You can prove (ii), (iii) and (iv) in the same way.
***

Here are some related exercises for you.

E14) Prove that T2 (F) is abelian, for any field F, and Tn (F) is non-abelian for
n > 2.

E15) i) For σ ∈ Sn , consider the permutation matrix P(σ), whose rows are
R σ(1) , K , R σ( n ) , where the R is are the rows of the identity matrix
(over any field). Show that PermF (n ) = {P(σ) σ ∈ Sn } is a
subgroup of GLn (F).

ii) Show that det(P(σ)) = sign (σ) for each σ ∈ Sn .

iii) Show that PermR (n ) is a subgroup of O(n ) .

Let us now focus our attention on one type of classical group, which has
several applications in other areas of mathematics and in the other sciences.

4.3 ORTHOGONAL AND UNITARY GROUPS

In the previous section, you have already noted several properties of
O(n ), SO(n ) and U (n ), for example, while doing E5, E6 and E7.
We will now discuss some more properties of elements of O(n ) and U (n ).

To begin with, let us consider what an element of O(n ) looks like. What do the
orthogonal groups have to do with orthogonality, i.e., perpendicularity? To see
this, you may recall the concept of ‘dot product’ on R n . The dot product is a
mapping from R n × R n to R, defined by v.w = v1w 1 + ⋅ ⋅ ⋅ + v n w n , for
v = ( v1 , K, v n ) and w = (w 1, K, w n ) in R n . You may also recall that

i) v.v gives the square of the length of the vector v, for v ∈ R n ;

ii) in R 2 , the cosine of the angle between two non-zero vectors v and w is
( v.w )
.
( v.v) (w.w )

Generalising this to R n , you get the concept of an ‘inner product’, as you may
recall from MMT-002. To remind you, consider the following.

Definitions: 1) Define < ⋅ , ⋅ >: C n × C n → C , the standard inner product on

n
C n , by < v , w > = ∑ vi w i = v t w ∀ v, w ∈ C n .
i=1
10
2) Two vectors v, w in C n are called orthogonal (or perpendicular) if Matrix Groups
< v , w > = 0.

Note that:
i) < v,w > = < w ,v > ,
ii) < v , v > ∈ R,

iii) < v , v > ≥ 0 ∀ v ∈ Cn ,

iv) < v , v > = 0 iff v = 0.

In what follows, when we write F we will mean either R or C. We will

denote by < ⋅ , ⋅ > the standard inner products in the two cases.

Recall that a basis {v1, ⋅ ⋅ ⋅, v n } of Fn is called

1, i = j
i) an orthogonal basis if < vi , v j > = 0 for all i ≠ j. δij = 
0, i ≠ j
ii) an orthonormal basis if < vi , v j > = δij for all i, j = 1,K, n . is the Kronecker delta
function, named after the
German mathematician,
What is the connection of such bases with the matrix groups? The following Leopold Kronecker
theorem tells us about this. (1823-1891).

Theorem 1: An n × n matrix A over R (respectively, C ) is in O(n )

(respectively, U (n )) if and only if {Ae1 , Ae 2 , ⋅ ⋅ ⋅ , Ae n } is an orthonormal basis
of R n (respectively, C n ). Here {e1,K, e n } is the standard basis of R n (or C n ).
A matrix is orthogonal
Proof: Let us first prove this for A ∈ Mn (R ). (respectively, unitary) iff
For v, w ∈ R n , < Av, Aw > = (Av ) (Aw ) = v t A t A w.
t
( ) its rows form an
n
orthonormal basis of R
If A ∈ O(n ), then At A = I. So < Av, Aw > = < v, w > for all v, w ∈ R n . Hence n
(respectively, C ).
< Aei , Ae j > = < ei , e j > = δij ∀ i, j = 1, K , n.
Thus, {Ae1 , K , Ae n } is an orthonormal basis of R n .

Conversely, let {Ae1 , K , Ae n } be an orthonormal basis of R n .

Then < Ae i , Ae j > = δ ij = < e i , e j > ∀ i, j = 1, K , n.
Thus,
t
( )
e i At A e j = e ti e j = δi j . …(1)
But, if a ij is the (i, j)-th entry of At A, then the LHS of (1) is simply a ij .
Therefore, we find At A = I . So, A ∈ O(n ).

Now, you can prove the statement about U (n ) on similar lines.

Here is a comment related to Theorem 1.

Remark 1: What Theorem 1 tells us is that orthogonal matrices preserve

angles between vectors, and lengths of vectors, in R n .

Let us see an immediate corollary to Theorem 1. 11

 Special Groups and Corollary 1: For i, j = 1, K , n, let z ij ∈ C satisfy
Semigroups
i) | z i1 |2 + | z i 2 |2 + L + | z in |2 = 1 ∀ i = 1,K , n;
Corollary 1 says that
A ∈ U (n ) iff the ii) z i1 z j1 + z i 2 z j2 + L + z in z jn = 0.
columns of A form an
orthonormal basis of R
n Prove that | z1 j |2 + | z 2 j |2 + L + | z nj |2 = 1 ∀ j = 1, K , n , and
n
(respectively, C ). z1i z1 j + z 2 j z 2 j + L + z ni z nj = 0 ∀ i ≠ j .

Proof: Let A = [z ij ] . Then, the given conditions tell us that the rows of A
form an orthonormal basis of C n. Thus, A ∈ U (n ). So, A−1 ∈ U (n ), that is,
A∗ ∈ U (n ). Hence, {A∗ e1,K , A∗ e n } forms an orthonormal basis of C n. Hence,
n n

∑ | zαj |2 = 1 ∀ j = 1, K, n and
α =1
∑z
α =1
αi z αj = 0 for i ≠ j .
n n
Thus, ∑ | z αj | 2 =1 ∀ j = 1, K, n and
α =1
∑z
α =1
z = 0 ∀ i ≠ j.
αi αj

We shall now consider another application of Theorem 1, to prove a result you

have used again and again in MMT-002, the Gram-Schmidt process. But first,
let us consider an example, to help you understand the proof.

Take a basis {v1 , v 2 , v3} = {(1, 0, 1), (0, 1, 0), (−1, 2, 0)} of R 3.
On applying the Gram-Schmidt process, w.r.t the standard inner product on
R 3 , we get the orthonormal basis
1  −1 1
w1 = (1, 0, 1), w 2 = (0, 1, 0), w 3 = 2  , 0,  .
2  2 2

1 0 − 1 1 2 0 − 1 2   2 0 −1 2
  
Here, A = 0 1 2  =  0 1 0  0 1 2 
1 0 0  1 2 0 1 2   0 0 1 2 
 
= QC
where Q = [w1 w 2 w 3 ] is in O(3), and C is in B3 (R ), with positive entries
along the diagonal.

Let us now generalise what we have seen, and done, in this example.

The Gram-Schmidt process Theorem 2 (Gram-Schmidt Orthogonalisation): Every matrix A in GLn (R )

is named after the can be uniquely expressed as A = QC, where Q ∈ O(n ) and C ∈ Bn (R), with
mathematicians Jorgen
Pedersen Gram and Erhard the diagonal entries of C being in R + .
Schmidt.
Proof: The proof is equivalent to the Gram-Schmidt orthogonalisation
process, and the QR decomposition, you have studied earlier in Unit 6 of
MMT-002. In fact, the columns of A form a basis {v1, ⋅ ⋅ ⋅, v n } of R n , as
A ∈ GL n (R). On applying the Gram-Schmidt process to the v i s , we obtain a
basis {w1 , w 2 , ⋅ ⋅ ⋅ , w n }, defined by
vi +1 − ∑ j=1 < vi +1 , w i > w i
i
n v v − < v 2 , w1 > w1
|| v || = < v , v > , v ∈ R . w1 = 1 , w 2 = 2 , K , w i +1 = ,
vi +1 − ∑ j=1 < vi +1 , w i > w i
i
v1 v 2 − < v 2 , w1 > w1
12
for i + 1 ≤ n. Matrix Groups
Note that A = [v1 v 2 L v n ] = [ w 1 w 2 L w n ] C , where C is an upper
triangular matrix with positive entries along the diagonal (as this is the matrix
which changes the basis {vi }i to the basis {w i }i ). The matrix Q, whose
columns form the orthonormal basis {w1 , ⋅ ⋅⋅, w n }, is in O(n ), by Corollary 1.
So, we get A = QC.

Next, to prove uniqueness, note that if Q1C1 = Q 2 C 2 , then

Q −21Q1 = C2C1−1 ∈ O(n ) ∩ Bn (R) . Since such a matrix is in O(n ) , it must have its
transpose (which has to be lower triangular) as its inverse. But the matrix is
also in B n (R ) , so its inverse must be upper triangular. Hence, C 2C1−1 must be
diagonal. Also, since C1 and C 2 have positive entries along the diagonal, so
does C 2C1−1. Further, since the eigenvalues of an element of O(n ) have
absolute value 1, C 2 C1−1 = I , i.e., C1 = C 2 . So, Q1 = Q 2 .

The Gram-Schmidt process is valid for C n also. It shows that each n × n

invertible complex matrix is uniquely a product kb, where k ∈ U (n ) and b is
an n × n upper triangular invertible complex matrix. Further, both in the real
and complex cases, for the groups of matrices of determinant 1, we may deduce
decompositions into corresponding determinant 1 matrices. In particular, we
have the following remark.

a b0 
Remark 2: Every matrix A =  0 ∈SL 2 (C) is expressible uniquely as a
c 0 d 0 
product A = BC , where

a 0 − c0  1 (b 0 + c0 ) / a 0 
B=   ∈ SU(2), C =   ∈ T2 (C) if a 0 ≠ 0 , and
c0 a0  0 1 
 0 b0  1 − b 0 d 0 
B =  −1  ∈ SU(2), C =   ∈ T2 (C) if a 0 = 0 .
− b 0 0 0 1 

Let us consider an example of the application of Theorem 2. Fig. 2: A stamp

commemorating Sir
William Rowan Hamilton
1 1 1 (1805 - 1865), an
Example 4: Write A = 1 1 0 as a product of an element of O(3) and an important mathematician.
1 0 0
element of B3 (R).
Solution: Using the Gram-Schmidt process, we find an orthonormal basis
{w 1, w 2 , w 3} of R3 , starting from the basis {v1 , v 2 , v3}, where
v1 = (1, 1, 1), v 2 = (1, 1, 0), v3 = (1, 0, 0).

 1 1 1  3 1 1 − 2  1 −1 
Check that w 1 =  , , , w 2 =  , , , w 3 = 2  , , 0 .
 3 3 3 2 3 3 3  2 2 

13
Special Groups and  1 1 1 
Semigroups  3 6 2 

1 1 −1 
Now, Q =  ∈O(3). So QQ t = I = Q t Q.
 3 6 2
 1 −2 
 0 
 3 6 
 1 1 1 
 3 3 3  1 1 1
 
1 − 2 
1 1 0
1
Consider C = Q t A =  
 6 6 6
 1 −1  1 0 0
 0 
 2 2 
 2 1 
 3 3 3
 
 2 1 
= 0
 6 6
 1 
0 0 
 2
So C ∈ B3 (R ) and C = Q t A. Thus A = QC.
***

Here is a related exercise for you now.

a c 
E16) Use Theorem 2 to write   ∈ GL 2 (R ) as a product QC, with
b d
Q ∈ O(2) and C ∈ B2 (R).

Let us now look at another interesting group which will turn out to be the same
as SU (2) structurally. For this, consider the set of Hamilton’s real quaternions,
H = {a + bi + cj + dk i 2 = j2 = k 2 = −1, ij = k = − ji , a , b, c, d ∈ R}.
In fact, the given conditions on i, j, k lead us to the other similar conditions:
jk = i = − kj, ki = j = −ik .
Note that (a + bi + cj + dk )(a − bi − cj − dk ) = a 2 + b 2 + c 2 + d 2 , and that
ψ : H ∗ → H ∗ : ψ (a + bi + cj + dk ) = a − bi − cj − dk is an anti-homomorphism,
that is, ψ (αβ) = ψ (β)ψ (α).
By convention, ψ (α) is denoted by α ∀ α ∈ H.
Now consider N : H∗ → R* : N(α) = α α. Then, you can check that N is a
group homomorphism.
So, for α = a + bi + cj + dk ∈ H * , we have
1 a −b −c −d
α −1 = α= + i+ j+ k.
N ( α) N (α) N (α ) N (α ) N (α)
Also, Ker N = {α ∈ H ∗ N(α) = 1}. We denote Ker N by H1.
So H1 = {a + bi + cj + dk a 2 + b 2 + c 2 + d 2 = 1} H∗ .

14 Thus, H1 is the group of quaternions of norm 1.

Note that H1 is the 3-dimensional unit sphere S3 . Matrix Groups
The unit sphere of n
We are now ready to prove our next result, about relationships between some dimensions is
of the classical groups and H1 . n
S = {( x 0 , x1 , ⋅ ⋅ ⋅ , x n ) ∈ R
n +1

2 2 2
Theorem 3: There exists an isomorphism between SU (2) and H1. Thus, x 0 + x 1 + L + x n = 1}.

SU (2) can be thought of as S3 .

Proof: Recall, from Remark 2, that any element of SU (2) is of the form
 a + ib c + id 
 , with a , b, c, d ∈ R such that a 2 + b 2 + c 2 + d 2 = 1. (We also
 − c + id a − ib 
say that this element of SU (2) is represented by (a , b, c, d ). )
Therefore, it is natural to define a map θ : SU (2) → H1 by
  a + ib c + id  
θ     = a + bi + cj + dk.
  − c + id a − ib  
You should check that θ is a homomorphism, it is 1-1 and onto H1. Therefore,
SU (2) ~ H1.

In the next section, you will see (in Theorem 4) that there exists a
homomorphism from SU (2) to SO(3). For now, why don’t you try some
exercises about SU (2) ?

E17) Let P, Q be elements of SU (2) represented by the real vectors

( x1 , x 2 , x 3 , x 4 ), ( y1 , y 2 , y 3 , y 4 ), respectively. Obtain the real vector
representing PQ .

E18) Prove that SO(2) is conjugate to the subgroup D of diagonal matrices in

GL2 (C) by SU (2).

E19) Show that SU (2) acts by conjugation on the group (G , + ) of trace zero
 0 1 
Hermitian matrices. Also find Stab     w.r.t. this action.
 1 0 
E20) Let P ∈ SO3 (C).

i) Show that 1 is an eigenvalue of P.

ii) Let X1 , X 2 be eigenvectors of P corresponding to its eigenvalues

λ1 and λ 2 . Show that X1t X 2 = 0 unless λ1λ 2 = 1.

iii) Prove that if X is an eigenvector for the eigenvalue 1, and P ≠ I,

then X t X ≠ 0.

The groups SO(2) and SO(3) comprise the set of rotations of 2-dimensional
space and 3-dimensional space, respectively. They have several applications in
the sciences and engineering.
15
Special Groups and You have seen how convenient it is to do calculations with matrices. So, if we
Semigroups can represent abstract groups as matrix groups, will this lead to simplifying
proofs? You can get a glimpse of the answer to this in the following section.

4.4 LINEAR REPRESENTATIONS

In this section you will see how groups can be represented by matrix groups.
The theory around this is called representation theory. Interestingly, some
results about abstract groups can be proved only by representation theory, and
there are no known purely group theoretic proofs in these cases. An important
example of this is the famous theorem of Dirichlet, which states that ‘There are
infinitely many primes in any arithmetic progression an + b , where a and b are
coprime’. There are other examples, like that of the quantum mechanical model
of the hydrogen atom, which can be explained via the representation theory of
its symmetry group, SO(4). Some results, like Frobenius’s theorem, which
states that ‘In any finite group G , the number of elements satisfying x n = e for
any divisor n of o(G ) is a multiple of n’, were discovered and proved using
representation theory.

So, let us look at what a linear representation is.

Definition: Given a group G and a field K (think of K = R or C, for

concreteness), a linear representation of dimension n is a group
homomorphism from G to GL n (K ). If K = R (resp., K = C ), the
representation is called a real (resp., a complex) representation.

An example of a representation of any group G is the trivial representation,

which sends every element of G to the identity matrix in GL n (K ).

As a non-example of a representation, consider the map

ρ : GLn (R) → GL n (R) : ρ (A ) = At . Since ρ(A B) ≠ ρ(A) ρ(B) for general
A, B, ρ is not a homomorphism. Hence it is not a linear representation.

Remark 3: If V is an n-dimensional vector space over K, we can pick one

ordered basis of V, say {v1 , v 2 , K , v n }. Then we can identify the group
GL (V ), of invertible linear transformations from V to itself, with
GL n (K ). For example, if V is the real vector space with basis {(1, 1), (−1, 1)},
then GL (V ) ~
− GL 2 (R ).

Let us consider some non-trivial examples of representations now.

Example 5: Give an example each, of a 1-dimensional complex representation

and a 2-dimensional real representation of the cyclic group Z nZ , where
n ∈ N.
Solution: For the first example, consider ρ : Z nZ → GL1 (C) = C* , defined by
ρ ( r ) = e 2ir π n .
Note that r = s ⇒ (r − s ) = nt for some t ∈ Z. Hence e 2irπ / n = e 2isπ / n . Thus, ρ is
well-defined.
16 Next, ρ ( r + s ) = ρ (r + s) = e 2i ( r +s ) π / n = e 2ir π / n . e 2is π / n = ρ (r ).ρ (s ) .
Hence, ρ is a group homomorphism, and so it is a 1-dimensional complex Matrix Groups
representation of Z nZ.

For the second example, consider

 cos(2r π n ) sin (2r π n ) 
ρ′ : Z nZ → GL 2 (R ) : ρ′( r ) =   .
 − sin (2r π n ) cos(2r π n )
You should check that ρ is well-defined, and ρ′( r1 + r2 ) = ρ′(r1 ) ρ′( r2 ) . Thus,
ρ′ is a 2-dimensional real representation of Z nZ.
***

Example 6: Check whether or not the map θ : Sn → GL n (R) : θ(σ) = P(σ) ,

where the i-th row of P(σ) is the σ(i) -th row of the identity matrix, is a
representation of Sn .
Solution: To help you understand θ, consider an example when n = 3.

0 1 0 0 0 1
   
θ ((1 2)) =  1 0 0  , θ ((3 2 1)) =  1 0 0  and (1, 2)(3, 2,1) = (2, 3) .
0 0 1 0 1 0
   
 1 0 0  0 1 0   0 0 1 
    
So θ ((2, 3)) =  0 0 1  =  1 0 0   1 0 0  = θ(1 2) θ(3 2 1) .
 0 1 0  0 0 1   0 1 0
    
In general, you can see that θ is well-defined, and
σ1σ 2 (1 0 K 0)
σ σ (0 1 K 0)
P(σ1σ 2 ) =  
1 2

 M 
 
σ1σ 2 (0 0 K 1)
= P(σ1 ) P(σ 2 ) .
Thus, θ is a group homomorphism, and hence a representation of Sn .
***

Example 7: Check whether or not θ : A n → R ∗ : θ(ρ) = ρ(n ) is a representation

of A n .

Solution: Though θ is well-defined, it need not be a homomorphism.

For example, if n = 5, ρ1 = (1 2 3), ρ 2 = (1 2 5), then ρ1 ρ 2 = (1 5) (2 3). So
θ(ρ1 ρ2 ) = 1. But θ(ρ1 )θ(ρ 2 ) = 5. Thus, θ is not a representation of A n .
***

Example 8: For any finite group G = {g1 , ..., g n }, consider the complex vector
space V of dimension n with basis {eg i i = 1, K , n}. Show that
ρ : G → GL(V ) : ρ(g ) = φg , where φg (eg i ) = egg i ∀ i = 1, K , n , is a representation
of G. [This is called the left regular representation of G. ]
17
Special Groups and  
Semigroups Solution: For each g ∈ G , φg : V → V : φg  ∑ z i e gi  = ∑ z i e gg i , z i ∈ C, you
 i  i
should verify that φg is a well-defined linear transformation.
Also, φgh = φg o φh for g, h ∈ G.
Hence ρ : G → GL(V) : ρ(g) = φ g is an n-dimensional representation of G.
***

We now use representations to prove a result, in continuation of what is done in

Theorem 3.

Theorem 4: There is a homomorphism from SU(2) to SO(3), with kernel {± I} .

Proof: You know that H is a real vector space of dimension 4, with basis
{1, i, j, k}. Consider its real subspace V generated by {i, j, k}. We can think of
SU (2) as acting on this space, via θ (in Theorem 3). So, we have a
homomorphism ρ from SU (2) to GL(V).
To explicitly write ρ : SU(2) → GL(V), we use the isomorphism θ to view
 a + ib c + id 
SU (2) as H1. Then, for any A =   ∈ SU(2), we write
 − c + id a − ib 
q = θ(A) = a + bi + cj + dk.
Also note that q −1 = a − b i − cj − dk , since q ∈ H1.
Then ρ (A ) : V → V : ρ (A ) (v) = qvq −1.
Thus, writing q i q −1, q j q −1 and qkq −1 in terms of the ordered basis {i, j, k}, we
get the following matrix:
 a 2 + b 2 − c2 − d 2 2(bc − ad) 2(ac + bd ) 
 
ρ (A ) =  2(ad + bc ) 2 2
a −b +c −d 2 2
2(cd − ab) 
 2(bd − ac) 2(ab + cd) a 2 − b2 − c 2 + d 2 


Now, since A −1 = A t is obtained by changing b, c, d to their negatives, you can

check that ρ(A ) −1 = ρ(A) t , that is, ρ(A ) ∈ O3 (R ).
Note that if A ∈ Ker ρ, then ρ(A ) v = v ∀ v ∈ V. Therefore, qiq −1 = i, that is,
qi = iq. Similarly, q commutes with j and k also. Hence, q commutes with
the whole of H. Thus, q ∈ Z(H ) = R. Now, the centre of H1 is
R ∩ H1 = {± 1}. Thus, q = ± 1.
∴ A = ± I.
Thus, A = ± I belongs to Ker ρ.
The final assertion left is to show that the determinant of ρ(A) is always 1,
which you can show by a direct (but messy) calculation (see E21 below).
Hence ρ : SU(2) → SO(3) is a homomorphism with kernel {± I} .

Try the following exercises now.

E21) i) Regarding Theorem 4, by direct computation, verify that

18
  a 2 + b2 − c2 − d 2 2(bc − ad ) 2(ac + bd )  Matrix Groups
 
 2(ad + bc ) a 2 − b2 + c2 − d 2 2(cd − ab) 
 2(bd − ac) 2(ab + cd ) a 2 − b 2 − c 2 + d 2 

has determinant 1, when a , b, c, d are real numbers satisfying
a 2 + b 2 + c 2 + d 2 = 1.
ii) Prove that the image of det o ρ is the constant function 1.

a − b
E22) i) Show that C*→ GL2 (R ) : a + ib a   defines a 2- A group G can have
b a  linear representations of
different dimensions.
dimensional real representation of C* .
ii) Does C∗ have a 3-dimensional real representation? Why, or why
not?
iii) Give a 1-dimensional real representation of C∗ .

With this we come to the end of our discussion on linear groups and
representations. Let us look at what you have studied in this unit.

4.5 SUMMARY
In this unit, you have studied the following points.

1) The definition, and examples, of a linear group.

2) The proof, and some applications of, the statement, ‘ A ∈ O(n ) (resp.,
U (n ) ) iff {Ae1 ,K Ae n } is an orthonormal basis of R n (resp., C n ).’

3) SU (2) ~
− H1 , the group of quaternions of norm 1. Hence, SU (2) can be
thought of as the sphere S3 .

4) The definition, and examples, of a linear representation of a group.

5) Using linear representations to prove that there is a homomorphism from

SU (2) to SO(3), with kernel {± I}.

4.6 SOLUTIONS / ANSWERS

E1) Define ψ : GL n (C) → C* : ψ (A) = det(A). Then you can check that ψ is
a well-defined group homomorphism, which is surjective.
Further, A ∈ Ker ψ iff det (A) = 1 iff A ∈ SL n (C).
Hence, using FTH, you get the result.

E2) There are several actions. Consider, for example,

φ : GLn (R) × M n (R ) → M n (R) : φ (g, A ) = g A.
Then verify that φ (I, A) = A, and
φ (g, φ (h, A )) = φ (gh , A) ∀g, h ∈ GL n (R ) and A ∈ M n (R ).
The orbits of I and 0 are GL n (R ) and {0}, respectively. 19
Special Groups and The stabilisers of I and 0 are {I} and GL n (R ), respectively.
Semigroups
E3) g ∈ GL n (F) iff g is invertible iff the column rank of g is n iff the
columns of g form an F-basis of Fn .

E4) You can check that (G , ⋅) is a group. However, G is not a linear group,
since no element of G is in GL 2 (R ).

E5) i) Check that

 x y
  a x + iy , where x , y ∈ R and x 2 + y 2 ≠ 0, defines an
− y x
isomorphism between GL2 (R ) and C∗ .

ii) Let z ij = x ij + iy ij . Check that

 x11 y11 L x1n y1n 
 
 z11 L z1n   − y11 x11 − y1n x1n 
 
 M M M → M M M M 
 
z 
 n1 L z nn   x n1 y n1 L x nn y nn 
− y 
 n1 x n1 L − y nn x nn 
is an injective group homomorphism from GL n (C) to GL 2n (R).

E6) i) O(n ) = {g ∈ GL n (R) g t = g −1} .

So g ∈ O(n ) ⇒ gg t = I ⇒ | g |2 = 1 ⇒ | g | = ±1.
Also, | g1g 2 | = | g1 | | g 2 | .
Thus, det : O(n ) → {±1} is an onto homomorphism, with kernel
SO(n ).
By FTH, O(n ) ~
− {±1}.
SO(n )
Thus, | O(n ) : SO(n ) | = 2.

ii) Q(v) = v t v, v = ( x1 ,K, x n ) t .

Now T ∈ O(n )
⇔ [T]t [T] = I, where [T] denotes the matrix of T w.r.t. the
standard basis of R n .
⇔ [T( v)]t [T(v)] = v t v ∀ v ∈ R n
⇔ Q(T( v)) = Q( v), i.e., T leaves Q invariant.

E7) U (1) = {α ∈ C* αα = 1}
= {α ∈ C* | α | = 1}
Thus, U (1) is the set of points on the circle of radius 1 and centre the
origin, in R 2 .

a b 2 2 2 2
E8) i)  c d  ∈ SO(2) iff a + b = 1 = c + d , ad − bc = 1.
 
20
 Then (a − d ) 2 + (b + c) 2 = 2 − 2 = 0 . Thus, a = d, b = −c . Hence the Matrix Groups
result.

  a b 
ii) Define φ : SO(2) → U(1) : φ     = a + ib .
 − b a  
Then φ is well-defined.
  a b  c d    ac − bd ad + bc  
Also, φ       = φ 
  − (ad + bc) ac − bd  

 − b a  − d c   
= (ac − bd ) + i (ad + bc )
= (a + ib ) (c + id )
  a b    c d  
= φ     φ  − d c   .
  − b a   
Thus, φ is a group homomorphism.
Further, for any a + ib ∈ U (1), | a + ib | = 1, i.e., a 2 + b 2 = 1.
  a b 
So a + ib = φ     , that is, φ is surjective.
  − b a 
 a b   1 0 
Finally, Ker φ =   a + ib = 1  =   .
− b a   0 1 
Thus φ is 1-1.
Hence SO(2) ~− U (1).

E9) i) g ∈ Z (GL n (F)) ⇔ gA = Ag ∀ A ∈ GL n (F).

⇔ g E ij (1) = E ij (1) g∀ i, j = 1, K , n, i ≠ j , where E ij (1) is the identity
matrix with one change, that is, 1 at the (i, j) th place also.
Now, gE ij (1) is the matrix obtained from g by adding the ith
column of g to its jth column. Also E ij (1) g is the matrix obtained
by adding the jth row of g to the ith row of g. On running through
all such E ij (1) , you will find that g = λI, for some λ ∈ F*.

*
ii) Z (SL n (C)) = {λI λ ∈ C and | λI | = 1}
*
= { λI λ ∈ C and λn = 1}
Now define φ : Z(SL n (C)) → G : φ(λI) = λ, where G is the group
of nth roots of unity. Then you should check that φ is an
isomorphism.

E10) Stab (I) = {A ∈ GLn (R ) At A = I} = O(n ).

E11) Stab (J) = {A ∈ SL 2 n (R) At JA = J} = SP2 n (R).

E12) Firstly, O(1, 3) ≠ «, since I ∈ O(1, 3).

Next, you can check that if A ∈ O(1, 3), then so does A −1.
Finally, check that for A, B in O(1, 3), AB ∈ O(1, 3).
21
Special Groups and Hence, O(1, 3) is a linear group.
Semigroups
A B
E13) Let P =   , where A, B, C, D ∈ GLn (R). Then
 C D
 At C t 
P t =  t .
t
B D 
0 − I  0 I
In the 1st case, P =  . Then P t =  . So,
I 0   − I 0
 0 I   0 I  0 − I
P t JP =      
 − I 0   − I 0  I 0 
 − I 0  0 − I  0 I 
=     =   = J.
 0 − I  I 0   − I 0
Hence P is symplectic.

0 I 
In the 2nd case, P =  . You can check that
 I 0
0 I   0 I  0 I   0 I 
 I 0 − I 0  I 0 ≠ − I 0.
     
Hence, P is not symplectic.

 At 0  A 0 
In the 3rd case, P =  
−1 
. Then, P t
= 
 0 (A −1 ) t . Therefore,
 0 A   
A 0   0 I   At 0 
P t JP =  
−1 t  
   = J.
−1 
 0 (A )   − I 0   0 A 
Hence P is symplectic.

 I B  I 0   I 0
Finally, let P =  . Then P t =  t  =  . We have
0 I   B I  B I 
 I B  0 I   I 0  0 I 
P t JP =       =   = J.
0 I   − I 0  B I   − I 0
Hence P is symplectic.

1 b
E14) Any element of T2 (F) is  , b ∈ F.
0 1 
1 b 1 c  1 b + c 1 c 1 b
Now   = =
1  0 1 0 1  ∀ b, c ∈ F.
0 1  0 1 0  
Thus, T2 (F) is abelian.
1 0 2 1
1 1
Now, consider x = 0 1 1 , y = 0
  1 1 in T3 (Q) .
0 0 1  0
0 1
1 1 3 1 1 4
Then xy = 0 1 2 and yx = 0 1 2
 
0 0 1 0 0 1
22
 So xy ≠ yx. Thus, T3 (Q) is not abelian. Matrix Groups

E15) i) Firstly, Perm F (n ) ≠ « as Sn ≠ «.

Next, for σ, τ ∈ Sn , P (σ o τ) = [R σ τ(1) , K , R σ τ ( n ) ]t
= P (σ) [R τ(1) , K , R τ( n ) ]t
= P (σ) P(τ)
Finally, P(I) = I , and hence P(σ −1 ) = P (σ) −1 ∀ σ∈ Sn .
Thus, Perm F (n ) ≤ GL n F).

ii) If σ is a transposition, then P (σ) is obtained from I by

interchanging two rows.
∴ | P(σ) | = −1 = sign (σ).
Further, since P(σ1σ 2 ) = P(σ1 ) P(σ 2 ), and every permutation is a
product of transpositions, P(σ) = sign (σ) ∀ σ ∈ Sn .

iii) For each σ ∈ Sn , the (i, j) th entry of P(σ) t is the ( j, i) th entry of

P(σ), which is δσ ( j) i .
Also, since σ is a bijection, δ σ( j) i = δ jσ−1 (i ) , the (i, j) th entry of
P(σ −1 ) .
∴P(σ) t = P(σ −1 ) = P(σ) −1.
So, P(σ) ∈ O(n ).

E16) Starting with the basis {v1 , v 2 }, with v1 = (a , b), v 2 = (c , d ), you should
check that the Gram-Schmidt process gives you the orthonormal basis
{w 1 , w 2 }.
 a b  1
Here w 1 =  , , w 2 = (− b , a ).
2 2 2 2 
 a + b a +b  a + b2
2

1 a − b 
So Q =  .
a 2 + b 2 b a 
 2 2 ac + bd 
 a +b 
Then C = Q t A =  a 2 + b 2 .
 ad − bc 
0
 a 2 + b 2 
So A = QC.

 a b  c d
E17) Let P =   and Q =   . Write
− b a  − d c
a = x 1 + ix 2 , b = x 3 + ix 4 , c = y1 + iy 2 and d = y 3 + iy 4 ,
where x1 , x 2 , x 3 , x 4 and y1 , y 2 , y 3 , y 4 are real numbers satisfying
x12 + x 22 + x 32 + x 24 = 1 and y12 + y 22 + y 32 + y 24 = 1 .
 ac − bd ad + bc   e f
Now PQ =   =   , say.
 − bc − a d − bd + ac   − f e 
So 23
Special Groups and e = (ac − b d ) = ( x1y1 − x 2 y 2 − x 3 y3 − x 4 y 4 ) + i( x1y 2 + x 2 y1 + x 3 y 4 − x 4 y 3 ),
Semigroups
f = (ad + bc ) = ( x1 y 3 + x 3 y1 − x 2 y 4 + x 4 y 2 ) + i( x1y 4 + x 4 y1 + x 2 y 3 − x 3 y 2 ) .
Now, PQ corresponds to the vector (Re(e), Im(e), Re(f ), Im(f )) .
You should check that
Re(e) 2 + Im(e) 2 + Re(f ) 2 + Im(f ) 2
= ( x 1 y 1 − x 2 y 2 − x 3 y 3 − x 4 y 4 ) 2 + ( x 1 y 2 + x 2 y1 + x 3 y 4 − x 4 y 3 ) 2
+ ( x 1 y 3 + x 3 y1 − x 2 y 4 + x 4 y 2 ) 2 + ( x 1 y 4 + x 4 y1 + x 2 y 3 − x 3 y 2 ) 2
= (x 12 + x 22 + x 32 + x 24 ) ( y12 + y 22 + y 32 + y 24 ) = 1 .

cos θ − sin θ
E18) Any element of SO(2) is of the form B =   , θ ∈ R , and
 sin θ cos θ 
 z w
any element of SU (2) is of the form A =   , z, w ∈ C* ,
− w z 
2 2  z − w
z + w = 1 . Also, then A −1 =  .
w z 
If SO(2) is conjugate to D, then for some z, w ,
 z w  cos θ − sin θ  z − w  λ1 0 
 − w z   sin θ cos θ   w = , for some
   z   0 λ 2 
λ1 , λ 2 ∈ C * .
On solving this, we get
− w (z cos θ + w sin θ) + z (−z sin θ + w cos θ) = 0 , and
z (− w cos θ + z sin θ) + w ( w sin θ + z cos θ) = 0 .
Simplifying, we get
(z 2 + w 2 ) sin θ = 0 = ( z 2 + w 2 ) sin θ .
2 2
Let us pick z, w so that z 2 + w 2 = 0, z + w = 1 .
1 1
[e.g., take z = i, w = .
2 2
 i 1 
2  is such that ABA −1 = e 0
−iθ
Then A =  2
  ∈ D. ]
− 1 −i   0 e iθ 
 2 2 
λ 0
Then, for A, B generally as above, ABA −1 =  1  , λ1 , λ 2 ∈ C∗.
 0 λ2 
Thus, SO(2) is conjugate to D by SU (2).

E19) For A ∈ G, P ∈ SU (2) , define P. A = PAP −1 .

Note that P −1 = P* , and trace (PAP −1 ) = trace A.
Also PAP −1 is Hermitian since A is so.
So P. A ∈ G .
Also, P. I = I and (P1.(P2 . A)) = (P1P2 ). A, for A ∈ G, P1 , P2 ∈ SU (2).
Hence, SU (2) acts by conjugation on G.
 0 1   0 1 * 0 1 
Now Stab     = P ∈ SU(2) P 
  P = 1 0 
 1 0   1 0   
24
  z w 2 2 2 2
 Matrix Groups
=   z + w = 1, w z + zw = 0, z − w = 1, w , z ∈ C .
− w z  

E20) i) We have
det(P − xI) = det((P − xI) t ) = det((P t − xI))
= det (P −1− xI) since P t = P −1 for P ∈ SO3 (C).
So, P and P −1 have the same characteristic polynomials. However,
in general, if λ is an eigenvalue of P, λ−1 is an eigenvalue of P −1.
So, since P and P −1 have the same characterstic polynomials,
whenever λ is an eigenvalue of P, λ−1 is also an eigenvalue of P.
Further, λ = λ−1 if and only if λ = ±1. Now, we know that
det(P) = 1, det(P) is the product of the roots of the characteristic
polynomial of P taken with correct multiplicity, and the degree of
the characteristic polynomial of P is odd.
Use these facts and show that 1 is an eigenvalue of P.

ii) Let X1 and X 2 be eigenvectors of P corresponding to eigenvalues

λ1 and λ 2 , respectively. Then, X1t P t X 2 = (PX1 ) t X 2 = λ1X1t X 2 .
But, X1t P t X 2 = X1t P −1X 2 = λ−21X1t X 2 . So, (λ1 − λ−21 )X1t X 2 = 0. The
result follows.

iii) Using (i), we see that its eigenvalues are − 1, − 1, 1. So, putting
λ1 = λ 2 = 1 in (ii), we get the result.

E21) i) It requires determination, but you will find that the determinant is
1!

ii) det o ρ : SU(2) → GL3 (R) : det o ρ (A) = | ρ (A ) | = 1 .

 a − b
E22) i) ρ : C* → GL 2 (R ) : ρ (a + ib ) =   is well-defined, since
b a 
a 2 + b 2 ≠ 0.
ρ [(a + ib ) (c + id )] = ρ [(ac − bd ) + i (ad + bc)]
a − b   c − d 
=  
b a  d c 
= ρ (a + ib ) ρ (c + id ).
Hence ρ is a group homomorphism.
Also, since ρ (C* ) ⊆ GL 2 (R), it is a 2-dimensional real linear
representation.

 a − b 0
ii) Define θ : C∗ → GL3 (R ) : θ(a + ib ) =  b a 0. Then you can
 0 0 1 
check that θ is a well-defined group homomorphism, and hence is
a 3-dimensional real representation of C*.
25
Special Groups and iii) Define α : C* → R∗ : α(z ) = | z | .
Semigroups
Then α is a well-defined group homomorphism of C∗ , and hence
the required representation.

26
 Abelian Groups
UNIT 5 ABELIAN GROUPS
Structure Page No.
5.1 Introduction 27
Objectives
5.2 Finite Abelian Groups 28
5.3 Finitely Generated Abelian Groups 40
Finitely Generated Groups
Free Abelian Groups
5.4 Structure Theorems 47
5.5 Summary 50
5.6 Solutions / Answers 50

5.1 INTRODUCTION
Cyclic groups were among the first examples of groups which you have
studied. Amazingly, it turns out that an arbitrary finite abelian group is
isomorphic to a direct product of cyclic groups of prime power order. Not only
this, these prime power orders are uniquely determined, forming a complete
system of invariants. This result is known as the Structure Theorem for Finite
Abelian Groups. It was first developed in the 1879 paper of the mathematicians
Georg Frobenius and Ludwig Stickelberger. Later it was both simplified and
generalised to finitely generated abelian groups.

In this unit, we will first discuss the structure of finite abelian groups, in
Sec.5.2. Then, in Sec.5.3, we will focus on finitely generated abelian groups.
Here you will also see what a free abelian group is.

In the next section, Sec.5.4, we put together what you have studied in the
previous two sections. The aim is to understand what any finitely generated
abelian group looks like.

Thus, studying this unit will give you a way of obtaining any finite, or finitely
generated, abelian group, up to isomorphism.

We now list the particular objectives of this unit.

Objectives
After studying this unit, you should be able to:
• state, prove and apply, the Structure Theorem for Finite Abelian Groups;
• obtain all abelian groups (upto isomorphism) of a given order;
• describe, and give examples of, free abelian groups;
• state, prove and apply, the Structure Theorem for Finitely Generated
Abelian Groups;
• give the rank, invariant factors and elementary divisors of any given
finitely generated abelian group;
• obtain all finitely generated abelian groups (up to isomorphism) of a given
rank and with torsion subgroup of a given order.
27
Special Groups and
Semigroups 5.2 FINITE ABELIAN GROUPS
In Unit 3 you studied what a direct product of groups, or of subgroups, is. You
have also seen that any finite cyclic group of order n is isomorphic to Z n .
Here we will use this knowledge to classify finite abelian groups. In fact, the
focus of this section is the following very fundamental theorem.

Structure Theorem of Finite Abelian Groups: Every non-trivial finite

abelian group G is isomorphic to a direct product of cyclic groups of prime
power order:
G ~ Z q e1 × Z q e2 × ⋅ ⋅ ⋅ × Z q es ,
1 2 s

where q1, q 2 , ⋅ ⋅ ⋅, q s are primes (not necessarily distinct) and ei ≥ 1 for all i.
Moreover, the prime powers q1e1 , q e22 , K, q se s are uniquely determined by G.

Let us try and understand the amazing power of this theorem. It says that given
any finite abelian group, of any order whatsoever, it can be written as a direct
product of cyclic groups of a certain order.
So, for example, an abelian group of order 23 × 52 × 7 can basically have the
structure Z 23 × Z 52 × Z 7 , or Z 7 × Z 23 × Z5 × Z5 , or another such break up of the
prime powers.

Let us, now, try and prove the Structure Theorem. For this, we first need to
prove certain results that will be used in the main proof.

Theorem 1: Let G be an abelian group of order n > 1. For each prime p

dividing the order of G , define G (p) = {a ∈ G o(a ) is a power of p}. Then
G (p) ≤ G. Moreover, G (p) is the unique Sylow p-subgroup of G.

Proof: From Unit 3, you know that for each prime p dividing o (G ), G has an
element of order p. So G (p) ≠ «.
m n
Let a , b ∈ G (p). Then a p = e and b p = e for some m, n ∈ N.
m +n m n n m
Therefore, (ab −1 ) p = (a p )p ((b p ) p )−1 = e. Thus, ab −1 ∈ G (p), that is, G (p)
is a subgroup of G.

We will now prove that the order of G (p) is a power of p, by contradiction.

So, suppose q is a prime different from p dividing o (G (p)). Then you know,
by Cauchy’s theorem, there is an element b ∈ G (p) of order q, which
contradicts the definition of G (p). Hence, we reach a contradiction. Thus, our
assumption must be wrong. Hence, o (G (p)) is a power of p.

Now we will show that any Sylow p-subgroup of G must be G (p). So, let S
be a Sylow p-subgroup of G. As the order of any element of S is a power of
p, it follows that S ⊆ G (p). Also, from Unit 3, you know that any p-subgroup
of G cannot contain a Sylow p-subgroup properly. Consequently, S = G (p).
This proves the result.

Theorem 1 tells us what the Sylow subgroups of a finite abelian group look
28
like. What happens if G is not abelian? Consider the following remark.
Remark 1: Note that if G is not abelian, G (p) need not be a subgroup of G. Abelian Groups

For instance, take G (2) = {e, (1 2), (2 3), (1 3)} in S3 . Since

(1 2) (1 3) ∉ G (2), G (2) ≤| S3 .
Hence, Theorem 1 doesn’t hold if G is not abelian.

The next result tells us that a finite abelian group is a direct product of its
Sylow p-subgroups.

Theorem 2: Let G be an abelian group of order n = p1n1 p n2 2 K p nk k , where the

pis are distinct primes and n i ≥ 1 for i = 1, K, k. Then
G ~ G (p1 ) × G (p 2 ) × ⋅ ⋅ ⋅ × G (p k ).

Proof: We will prove this in two steps.

Step 1: To show that G = G (p1 )G (p 2 )KG (p k ) :

First, we note that since G is abelian, G (p1 )G (p 2 )KG (p k ) ≤ G.
Next, suppose a ∈ G. By Lagrange’s Theorem, a n = 1.
n
Set mi = n pi i , 1 ≤ i ≤ k .
As g.c.d (m1 ,K , m k ) = 1, we can find integers α1,K, α k such that
α1m1 + ⋅ ⋅ ⋅ + α k m k = 1.
Hence a = a α1 m1 +⋅⋅⋅ + α k m k = a1a 2 ⋅ ⋅ ⋅ a k , where a i = a α i m i . …(1)
ni
p
As a i i = (a in )α i = e, we see that a i ∈ G (pi ).
Consequently, it follows from Equation (1), that
G = G (p1 )G (p 2 )K G (p k ). …(2)

Step 2: To show that G (pi ) ∩ G (p1 )K G (pi −1 )G (pi +1 )K G (p k ) = {e} ∀ i :

Suppose x ∈ G (pi ) ∩ G (p1 )KG (pi −1 )G (p i +1 )KG (p k ). Then
x = x1 ⋅ ⋅ ⋅ x i −1x i +1 ⋅ ⋅ ⋅ x k , where x j ∈ G (p j ).
n p jn j n1
⋅⋅⋅ p
n i −1 ni +1
⋅⋅⋅ p k
nk
Since o (G (p j )) = p j j , x j = e, and hence x p1 i −1 p i +1
= e. …(3)
ni
Also x ∈ G (pi ), so that x p i = e. …(4)
ni n1 n i −1 n i +1 nk
Since g.c.d(pi , p1 K pi −1 pi +1 K p k ) = 1, (3) and (4) give us x = e, which
proves that G (p i ) ∩ G (p1 ) L G (p i−1 ) G (p i+1 ) L G (p k ) = {e} . …(5)

Now, from Steps 1 and 2, and noting that G (p i ) G ∀ i = 1, K, k (as G is

abelian), we get
G ~ G (p1 ) × G (p 2 ) × ⋅ ⋅ ⋅ × G (p k ).

From this theorem, we know that to study a finite abelian group, we need to
look at the structure of each of its Sylow p-subgroups. So, let us temporarily
restrict our attention to studying the structure of an abelian p-group, that is, an
abelian group G of order p n, n ≥ 1. Firstly, for such a G , the order of its
elements cannot exceed p n . So, there exists a ∈ G of maximal order in G ,
i.e., ∃ a ∈ G such that o( x ) ≤ o(a ) ∀ x ∈ G. Also, note that in this case
o(x ) o(a ) ∀ x ∈ G. We will be using such an element in the following result.

29
Special Groups and Theorem 3: Let G be a finite abelian p-group, G ≠ {e}, and let a ∈ G be of
Semigroups
maximal order in G. Then G is cyclic or there is a subgroup H of G , such
that G ~ < a > ×H.

Proof: Let o (a ) = p k . If G = < a > , then G is cyclic.

Suppose G ≠ < a > . Consider the set A = {K ≤ G < a > ∩K = {e}}.
A ≠ « , since {e} ∈ A.
Let H be maximal in A , that is, H belongs to A , and if K is any element of
A , then K cannot properly contain H. We will prove that G ~ < a > × H.

Since G is abelian, all its subgroups are normal. Moreover, by definition,

< a > ∩ H = {e}. Therefore, in order to prove that G ~ < a > ×H, we only need
to show that G = < a > H. We will prove this by contradiction.

So, suppose that G ≠ < a > H. Then G (< a > H) is a p-group, and hence
contains an element of order p. In other words, there exists x ∈ G (< a > H)
such that x p = e, that is, ∃ x ∈ G such that x ∉< a > H but x p ∈< a > H. So,
x p = a q b, for some q ∈ Z and b ∈ H.
Now, since the order of every element of G divides p k ,
k k −1 k −1 k −1
e = x p = (x p ) p = a qp b p .
k −1
⇒ a qp ∈ < a > ∩ H = {e}
⇒ p k qp k −1 , since o (a ) = p k
⇒p q
⇒ q = ps, for some s ∈ Z.
Recall that x ∉< a > H, so xa −s ∉ H. However,
(xa −s ) p = x pa − ps = x pa − q = b ∈ H. …(6)

Now, take K = xa − s H. Note that H ⊆ K. Moreover xa −s ∈ K , but xa −s ∉ H,

so H ≠ K.
Therefore, by the maximality of H in A , < a > ∩K ≠ {e}.
Let α ∈< a > ∩ K, where α ≠ e.
Then there exist t , u ∈ Z, h ∈ H such that α = a t and α = ( xa − s ) u h.

Now, could p divide u ? Suppose it does. Then u = pv for some v ∈ Z.

So α = ( xa − s ) u h = ((xa − s ) p ) v h ∈ H, by (6), i.e., α ∈ H.
But α ∈< a > as well, and < a > ∩ H = {e}. We reach a contradiction, since
α ≠ e. Therefore, p does not divide u.

Next, since p is prime, g.c.d (p, u ) = 1. So there exist integers w and d such
that 1 = pw + ud. Therefore, x = (x p ) w ( x u ) d .
Now, you know that x p ∈< a > H.
Also α = a t = ( xa − s ) u h ⇒ x u = a t a su h −1 ∈< a > H. Therefore, x ∈< a > H. This
is a contradiction to how x was chosen.
30
Therefore, our assumption that G ≠ < a > H must be wrong.
Thus, G = < a > H. Abelian Groups

Therefore, G ~ < a > × H.

This result has an immediate corollary about the structure of a finite abelian
p-group.

Corollary 1: Any finite abelian p-group G can be expressed as an internal

direct product of cyclic subgroups. (Note that the order of each of these
subgroups is a power of p.)

Proof: From Theorem 3, ∃ a ∈ G such that G ~ < a > × H.

If H ≠ {e}, we can repeat this process on H to get H ~ < b > × K , where b ∈ H
is of maximal order in H, and K is a proper subgroup of H, so that
G ~ < a > × < b > ×K.
Since G is finite, eventually this process will end. Consequently, we have G
as a direct product of cyclic groups, each of order some power of p.

With Theorem 2 and Corollary 1 put together, you may have got some idea of
the structure of finite abelian groups. This is the fundamental result we had
mentioned at the beginning of this section.

Theorem 4 (Structure Theorem for Finite Abelian Groups): Every

non-trivial finite abelian group G is isomorphic to a direct product of cyclic
groups of prime power order, that is,
G ~ Z e1 × Z e2 × ⋅ ⋅ ⋅ × Z es ,
q1 q2 qs

where q1, q 2 , ⋅ ⋅ ⋅, q s are primes (not necessarily distinct) and ei ≥ 1 for all i.
Moreover, the prime powers q1e1 , q e22 , K, q se s are uniquely determined by G.

Proof: The proof is in two steps – first we write G as a direct product of its
Sylow p-subgroups, and then we show that each of these Sylow p-subgroups is
expressible as a direct product of cyclic groups (of course of prime power
order).
Let o(G ) = p1n1 p n2 2 K p nk k , where the pis are distinct primes.
By Theorem 2, you know that G ~ G (p1 ) × G (p 2 ) × ⋅ ⋅ ⋅ × G (p k ).
Further, by Corollary 1, G (pi ) can be decomposed further as a direct product
of cyclic groups of order some power of pi , i = 1, K , k. Therefore, we see that
G is isomorphic to a direct product of cyclic groups each of prime power order.

The proof of this theorem will be complete once you prove the uniqueness of
the decomposition (see E1 and E2 below).

The uniqueness of the decomposition in the Structure Theorem leads us to the

following definition.

Definition: The orders q1e1 , q e22 , K, q es s of the cyclic subgroups in the structural
decomposition of a finite abelian group G are called the elementary divisors
of G. Further, the representation of G , as the direct product of cyclic
p-subgroups is called the elementary divisor decomposition of G.
31
Special Groups and
Semigroups For example, if G ~ Z 2 × Z3 × Z 9 , then 2, 3 and 9 are the elementary divisors of
G. Also, G ′ ~ Z 2 × Z 3 × Z 3 × Z3 has the same order as G , but different
elementary divisors, namely 2, 3, 3, 3.

We shall come back to these divisors a little later in this section. For now, try
some related exercises.

E1) Let G1 and G 2 be abelian groups of order p1n1 p n22 K p nk k , where p i ≠ p j

for i ≠ j . Prove that G1 ~ G 2 if and only if G1 (p i ) ~ G 2 (p i ) for all
i = 1, 2, K, k.

E2) Let G be an abelian group such that G = p r , where p is a prime. If

G ~ H1 × H 2 × K × H m and G ~ K1 × K 2 × K × K n , where the His and K j s
are non-trivial cyclic subgroups of G , with H1 ≥ H 2 ≥ K ≥ H m and
K1 ≥ K 2 ≥ K ≥ K n , then m = n and H i = K i for all i = 1, K, m.

E3) Obtain the elementary divisors of Z 5 × Z 5 2 × Z112 . Are these the same as
the elementary divisors of Z 55 × Z 55 × Z 5 ? Why, or why not?

Now, you may wonder how the Structure Theorem can be applied to
specific groups in practice. To answer this, consider G, a finite abelian
group of order n = p1n1 p n2 2 K p nk k , where the pis are distinct primes, n i ≥ 1 for
all i = 1, K , k. Now, you know that the first step is to decompose G as a
product of its Sylow subgroups, G (pi ), 1 ≤ i ≤ k. Each of these Sylow
subgroups have order p1n1 , p n2 2 , K, p nk k , respectively. You also know that each
of these subgroups can be decomposed into a direct product of cyclic groups of
prime power orders. Let us consider G (pi ). Suppose we have the following
decomposition:
G (pi ) ~ Z e1 × Z e2 × K × Z et .
p i p i pi

Here, we may assume e1 ≥ e 2 ≥ K ≥ e t ≥ 1 (this is because for direct

products, H × K ~ K × H). Now,
p ini = o (G (p i ))
= o (Z pe1 × Z pe 2 × L × Z pe t )
i i i

= Z pe1 Z p e2 L Z p et
i i i
e1 + e 2 +K+ e t
=p i
So n i = e1 + e 2 + L + e t . Hence the possibilities for the cyclic decomposition of
each Sylow pi-subgroup comes from looking at all possible partitions
e1 + e2 + L + e t of n i , with e1 ≥ e 2 ≥ K ≥ e t ≥ 1.
This gives us a method to apply the Structure Theorem of Finite Abelian
Groups to find all the abelian groups, up to isomorphism, of a given order. You
can see how the procedure works through an example of a p-group. Then we
will move on to examples in which there is more than one prime involved.
32
Example 1: Determine all the possible abelian groups, up to isomorphism, of Abelian Groups
order 16.
Solution: As o(G ) = 16 = 2 4 , we need to consider all the ways of partitioning
4. These are
4=4
4 = 3 +1
4= 2+ 2
4 = 2 +1+1
4 = 1 + 1 + 1 + 1.

Therefore, G must be isomorphic to one of the following groups:

Z 24 = Z16
Z 23 × Z 21 = Z 8 × Z 2
Z 22 × Z 22 = Z 4 × Z 4
Z 22 × Z 21 × Z 21 = Z 4 × Z 2 × Z 2
Z 21 × Z 21 × Z 21 × Z 21 = Z 2 × Z 2 × Z 2 × Z 2
Conversely, all five groups listed above are abelian groups of order 16, and no
two of them are isomorphic. (For instance, Z8 × Z 2 ~| Z 2 × Z 2 × Z 2 × Z 2 , since
Z 8 × Z 2 has an element of order 8, while all the non-zero elements of
Z 2 × Z 2 × Z 2 × Z 2 have order 2.)
***

Example 2: Determine all the possible abelian groups, up to isomorphism, of

order 56.
Solution: o(G ) = 56 = 237. We know that G ~ G (2) × G (7), where G (2) = 23
and G (7) = 7. To obtain the possible exponents for elementary divisors of
G (2) and G (7), we look at all possible ways of partitioning 3 (the exponent of
23 ) and 1 (the exponent of 71 )
G ( 2) G (7 )
3 1
2 +1
1+1+1
Thus, G must be isomorphic to one of the following groups:
Z 2 3 × Z 71 = Z 8 × Z 7
Z 2 2 × Z 21 × Z 71 = Z 4 × Z 2 × Z 7
Z 21 × Z 21 × Z 21 × Z 71 = Z 2 × Z 2 × Z 2 × Z 7
Conversely, all three groups listed above are abelian groups of order 56, and no
two of them are isomorphic.
***

Example 3: Determine all the possible abelian groups, up to isomorphism, of

order 223453.
Solution: G ~ G (2) × G (3) × G (5), where G (2) = 22 , G (3) = 34 and
33
Special Groups and
G (5) = 53 . The possible exponents for the elementary divisors of
Semigroups
G (2), G (3) and G (5) are as follows:
G (2) G (3) G (5)
2 4 3
1+1 3+1 2 +1
2+2 1+1+1
2 +1+1
1+1+1+1
Hence, the following is the list of all non-isomorphic abelian groups of order
223453 :
Z 4 × Z81 × Z125
Z 4 × Z81 × Z 25 × Z 5
Z 4 × Z81 × Z 5 × Z5 × Z 5

Z 4 × Z 27 × Z 3 × Z125
Z 4 × Z 27 × Z 3 × Z 25 × Z 5
Z 4 × Z 27 × Z 3 × Z 5 × Z5 × Z 5

Z 4 × Z 9 × Z 9 × Z125
Z 4 × Z 9 × Z 9 × Z 25 × Z5
Z 4 × Z 9 × Z 9 × Z5 × Z 5 × Z 5

Z 4 × Z 9 × Z 3 × Z 3 × Z125
Z 4 × Z 9 × Z 3 × Z 3 × Z 25 × Z5
Z 4 × Z 9 × Z 3 × Z 3 × Z5 × Z 5 × Z5

Z 4 × Z 3 × Z 3 × Z 3 × Z 3 × Z125
Z 4 × Z 3 × Z 3 × Z 3 × Z 3 × Z 25 × Z 5
Z 4 × Z3 × Z3 × Z3 × Z3 × Z5 × Z 5 × Z5

Z 2 × Z 2 × Z 81 × Z 125
Z 2 × Z 2 × Z 81 × Z 25 × Z 5
Z 2 × Z 2 × Z 81 × Z 5 × Z 5 × Z 5

Z 2 × Z 2 × Z 27 × Z 3 × Z125
Z 2 × Z 2 × Z 27 × Z 3 × Z 25 × Z 5
Z 2 × Z 2 × Z 27 × Z 3 × Z 5 × Z 5 × Z 5

Z 2 × Z 2 × Z 9 × Z9 × Z125
Z 2 × Z 2 × Z 9 × Z9 × Z 25 × Z 5
Z 2 × Z 2 × Z 9 × Z9 × Z5 × Z5 × Z 5

Z 2 × Z 2 × Z 9 × Z 3 × Z 3 × Z125
Z 2 × Z 2 × Z 9 × Z 3 × Z 3 × Z 25 × Z 5
Z 2 × Z 2 × Z 9 × Z 3 × Z 3 × Z 5 × Z5 × Z 5
34
Z 2 × Z 2 × Z 3 × Z 3 × Z 3 × Z3 × Z125 Abelian Groups

Z 2 × Z 2 × Z 3 × Z 3 × Z 3 × Z3 × Z 25 × Z5
Z 2 × Z 2 × Z 3 × Z 3 × Z 3 × Z3 × Z5 × Z 5 × Z5
Also note that all the groups listed above are abelian, of order 223453 , and non-
isomorphic.
***

Example 4: Let G be an abelian group of order 200, with exactly four

elements of order 5. What are the possible isomorphism classes of G ?
Solution: o(G ) = 200 = 52 × 23 .
So G ~ G (5) × G (2) , with o(G (5)) = 5 2 and o(G (2)) = 2 3.
Now, considering the partitions of 2 and 3, we have
2 3
1+1 2 +1
1+1+1
So, there are 6 possible isomorphism groups.
Any element of order 5 can only be from the direct summands of G (5), that is,
Z 25 or Z 5 × Z 5 , since 5 23. Further, 3 groups are of the form Z 25 × H, up to
isomorphism. (Here H is Z 8 , or Z 4 × Z 2 , or Z 2 × Z 2 × Z 2 . )
Each of these has exactly 4 elements of order 5, namely,
(5, 0), (10, 0), (15, 0), (20, 0) , where 0 is the zero element of H. Note that if
5 ( x, y) = ( 0, 0), then 5x = 0 and 5y = 0, where x ∈ Z 25 , y ∈ H.
The other 3 groups are of the form Z 5 × Z 5 × H , which has 24 elements of
order 5, of the form ( x, y, 0), ∀ x , y ∈ Z5 , x ≠ ( 0, 0 ), y ≠ ( 0 , 0 ).
Thus, the required isomorphism classes are only three, namely,
Z 25 × Z 8 , Z 25 × Z 4 × Z 2 , Z 25 × Z 2 × Z 2 × Z 2 .
***

From the examples above, you may have gauged the following algorithm for
finding all the possible non-isomorphic types of abelian groups of order n :
Step 1: Factor n into distinct primes: n = p1n1 p n2 2 K p nk k .

Step 2: Find the number p(n1 ) of all the partitions of n1 , i.e., p(n1 ) is the
number of ways n1 can be written as a sum of positive integers
n1 = e1 + e 2 + ⋅ ⋅ ⋅ + e t , with e1 ≥ e 2 ≥ K ≥ e t (≥ 1), t ≥ 1 (in other words,
p(n1 ) is the number of ways to write n1 as a sum of positive integers,
in descending order).
n1
Step 3: Find all the abelian groups of order p1 (there will be p(n1 ) of
them).
Step 4: Repeat Steps 2 and 3 for primes n 2 ,K , n k and p 2 , K, p k .

Step 5: Build direct products of these pi -groups in all the ways possible, to
end up with p(n 1 )p(n 2 ) K p(n k ) non-isomorphic abelian groups of
order n.
35
Special Groups and It’s now time for you to check your understanding of what you have studied so
Semigroups far.

E4) Find all the possible abelian groups, up to isomorphism, of order

i) 105, ii) 270, iii) 9801.

E5) What is the smallest positive integer n such that

i) there are exactly two non-isomorphic abelian groups of order n ?
ii) there are exactly three non-isomorphic abelian groups of order n ?

E6) How many abelian groups, up to isomorphism, are there

i) of order pq, where p and q are distinct primes?
ii) of order pqr, where p, q and r are distinct primes?

E7) Suppose G is an abelian group of order 120 with exactly three elements
of order 2. Determine all possible isomorphism classes of G.

Now, let us consider another useful consequence of the fundamental structure

theorem you have studied. This is a theorem you have proved earlier in Section
3.3, Unit 3.

Theorem 5 (Converse of Lagrange’s theorem for abelian groups): Let G

be an abelian group of order n and let m be any positive divisor of n. Then
there exists a subgroup of G of order m.

Before getting to its proof, consider an illustration of this result. You can think
of this as a model for giving another proof of this theorem.
So, let G = Z 23 × Z 23 × Z 2 × Z 32 × Z 32 × Z 32 × Z 5 × Z 73 × Z 7 , a group of order
1120210560.
Let us take a divisor of o(G ), say 6048. How do we produce a subgroup of G
of order 6048? For this, let us first look at the factorisation of 6048, i.e.,
6048 = 25337. Then let us find the prime powers of the cyclic group factors of
G which just exceed or equal 25 , 33 and 7, respectively.
Firstly, the exponent 5 of 2 is greater than all the exponents of 2 in o(G ). So,
we rewrite 5 as 3 + 2. Similarly, the exponent of 3 is rewritten as 2 + 1. Then
we match them to whatever extent possible, as below.

2 3 2 3 2 32 32 32 5 7 3 7 ← − − (Elementary divisors of G )

23 2 2 32 3 7

Now, take a subgroup of the cyclic group in order to match the total exponent
that we need for each prime. In this way, we can see that
Z 23 × 2Z 23 × 0 × Z 32 × 3Z 32 × 0 × 0 × 0 × Z 7 is a subgroup of the desired order.
Note that we have used the fact that every cyclic group has a subgroup of
order any number that divides its order.
36
Now you can try proving Theorem 5 (see E8 below). Abelian Groups

E8) Prove Theorem 5, using Theorem 4. Also recall that the converse of
Lagrange’s theorem is true for cyclic groups.

E9) There are six types of abelian groups, up to isomorphism, of order 108.
Prove that
i) two of them have exactly one subgroup of order 3;
ii) two of them have exactly four subgroups of order 3; and
iii) two of them have exactly 13 subgroups of order 3.

Now, do you think that the elementary divisor decomposition is the only way
of representing an abelian group as a direct product of its subgroups? Think
about this, while considering the following procedure.

Take G = Z 2 4 × Z 2 2 × Z 2 × Z 3 × Z 3 × Z 53 × Z 53 × Z 5 × Z 5 × Z 7
Let us write out these prime powers in the following format, one row for each
prime base, and ordered from the largest exponent to the smallest, from left to
right. So we get,
24 22 2
3 3
…(I)
53 53 5 5
7
Now, the row of powers of 5 in (I) is the longest. To make all the rows of the
same length, put 1 in the blank positions. So we now get the following
arrangement:
24 22 2 1
3 3 1 1
…(II)
53 53 5 5
7 1 1 1
Using the fact that the direct product is associative and commutative, we can
rewrite G as:
G ~ Z 5 × (Z 2 × Z5 ) × (Z 2 2 × Z 3 × Z 53 ) × (Z 2 4 × Z3 × Z53 × Z 7 ) (columnwise, from
right to left in Arrangement I above)

~ Z 5 × Z10 × Z1500 × Z 42000  ∏ Z mi , m i = product of integers in the ith
 i column in Arrangement II above.)
Now, the orders 5, 10, 1500, 42000 of the successive cyclic groups satisfy
5 10,10 1500,1500 42000. So each number divides the succeeding number.
Thus, G is written in two ways as a direct product, one as per the elementary
divisor decomposition, and the other as an alternative form.

Keep this example in mind while considering the following result that gives an
alternative way of presenting the structure of an abelian group.

Theorem 6 (Alternative Structure Theorem): Every finite abelian group

G (≠ {e}) is isomorphic to a direct product of the form Z m1 × Z m 2 × K × Z m t , for
37
Special Groups and
some integers m1 , m 2 , K , m t satisfying mi ≥ 2 for all i = 1, K , t and mi m i +1
Semigroups
for 1 ≤ i ≤ t − 1.
Moreover, the integers m1 , m 2 ,K , m t are uniquely determined by G.

Proof: Suppose G is abelian of order n = p1n1 p n2 2 K p nk k , where the pis are

distinct primes. We can assume that G is already in the form mentioned in
Theorem 4. To express G in the form we now need, we will undertake the
following steps:
Step 1: First we group together all the elementary divisors which are powers
of the same prime. In this way, we obtain k lists of integers (one for
each pi ).

Step 2: In each of these k lists, we arrange the integers row-wise in non-

increasing order, as done in Arrangement (I) in the example above.

Step 3: Among these k rows, suppose the longest consists of t integers.

Make each of these k rows of length t by appending 1 in as many
places as required at the end of each list, as in Arrangement (II) in the
example above.

Step 4: Let m1 be the product of the integers in the t th column of this

arrangement, m 2 be the product of the integers in the (t − 1) th column
in each of these lists, and so on.

The ordering of lists in this way ensures that mi m i +1 for 1 ≤ i ≤ t − 1. Thus,

G ~ Z m1 × Z m 2 × K × Z m t , which is in the form required.

Now, to complete the proof, we need to prove the uniqueness of m1, m2 ,K , m t .

First, note that once G is represented in the form given in the statement, the
elementary divisors of G are the prime power factors of m1 , m 2 ,K , m t . The
divisibility relations on the mis imply that m t is the product of the largest of
the prime powers among the elementary divisors, m t −1 is the product of the
largest of the prime powers among the elementary divisors once the factors of
m t have been removed, and so on. If m1′ , m′2 , K , m′r are another set of integers
that satisfy the statement of the theorem, then we take the prime power factors
of these elements and similarly obtain the elementary divisors of G. But from
Theorem 4, you know that the elementary divisors of G are unique. Therefore,
the uniqueness of the m i in this theorem follows.

The unique representation in Theorem 6 allows us to define the following

terms.

Definition: Let G be a finite abelian group, and G ~ Z m1 × Z m 2 × K × Z m t , with

m i ≥ 2 ∀ i and mi mi +1 ∀ i = 1, K , t − 1. The integers m1 , m 2 , K , m t are called
the invariant factors of G. The representation of G , in this form is called the
invariant factor decomposition of G.

38 Thus, in the detailed example before Theorem 6, you have seen that the group
with invariant factors 5,10,1500, 42000, has elementary divisors Abelian Groups

2 4 , 2 2 , 2, 3, 3, 53 , 53 , 5, 5, 7 .

Let us consider another example.

Example 5: Obtain 3 distinct possible invariant factor decompositions of a

group of order 2 23453.

Solution: In Example 3, you have seen all the possible non-isomorphic abelian
groups of order 2 2 34 53. Take any 3 of these non-isomorphic decompositions.
Let us take the first, fifth and the twelfth listed there.
Consider the elementary divisors in the first one, namely, 2 2 , 34 , 53. Arranging
the distinct prime powers, we get only one column since each row here is of
length 1:
22
34
53
So m = 2 2 × 34 × 53 = 40500 is the only invariant factor, and Z m is the
corresponding invariant factor decomposition.

Now let us consider the fifth decomposition given in Example 3, namely,

Z 4 × Z 27 × Z 3 × Z 25 × Z 5 .
We arrange the distinct prime powers among the elementary divisors as below:
22
33 3
52 5
We re-present this as
22 1
33 3
52 5
Then m1 = 1 × 3 × 5 = 15, m 2 = 22 × 33 × 52 = 2700. So the invariant factor
decomposition is Z15 × Z 2700 .
Similarly, you can see that Z 4 × Z 9 × Z 3 × Z 3 × Z 5 × Z 5 × Z 5 has
invariant decomposition Z15 × Z15 × Z180 .
***

If you have followed the discussion so far, then you should be able to solve the
following problems.

E10) Give the possible elementary divisor decompositions and invariant factor
decompositions of an abelian group of order 56.

E11) Find the elementary divisors, and the invariant factor decomposition, of
the following groups:
i) Z 2 × Z2 × Z5 × Z5
39
Special Groups and ii) Z 9 × Z 25 × Z 35 × Z 4
Semigroups
iii) Z 5 × Z10 × Z 50 .

We have proved the structure theorem of finite abelian groups in two

equivalent forms, as stated in Theorem 4 and Theorem 6. Both these theorems
are a particular case of what you shall study in the next section.

5.3 FINITELY GENERATED ABELIAN GROUPS

In this section we shall consider a more general class of abelian groups than the
one you studied in Sec.5.2. Towards this end, we shall first discuss what a
finitely generated abelian group is and what a free abelian group is. However,
before focussing on abelian groups, we will consider what any group which is
finitely generated looks like.

5.3.1 Finitely Generated Groups

To start with, recall that for an integer n ≥ 1, Z n denotes the direct product
Z × Z × K × Z. By Z0 , we will mean the identity group {0} .

Also, recall what a cyclic subgroup of a group is. For instance, consider S5 ,
and X = {(1 2)} ⊆ S5. Now, look at the intersection of all subgroups of S5 that
contain X . This is the smallest subgroup of S5 that contains X, and you
should check that this is {e, (1 2)}, the subgroup generated by {(1 2)}, denoted
by < (1 2) > .

More generally, let G be a group (not necessarily abelian), and X ⊆ G, X ≠ «.

Then there is at least one subgroup of G containing X, namely, G itself.
Consider all the subgroups of G containing X and take their intersection. This
will be the smallest subgroup of G that contains X, and is denoted by X .

Proposition 1: Let G be a group (not necessarily abelian) and X be a non-

empty subset of G. Then
X = {a1n1 a n2 2 K a nk k a i ∈ X, n i ∈ Z for all i = 1, K, k, k ≥ 1},
where the a i s are not necessarily distinct.

Proof: First of all, you should check that

K = {a1n1 a n2 2 K a nk k a i ∈ X, n i ∈ Z for all i, K , k , k ≥ 1}
is a subgroup of G containing X. Therefore, by definition, X ⊆ K.
Now, let H be a subgroup of G containing X. Then for any a1 ,K, a k ∈ X, and
n1 ,K, n k ∈ Z, a1n1 a n2 2 K a nk k ∈ H. Therefore, K ⊆ H. Hence, by the definition of
X , K⊆ X .
Thus, K = X .

Note that in the proposition above, G is any group (not necessarily an abelian
40
group). Also, note that if G is abelian, then we can take the a i s to be distinct.
The proposition above leads us to the following definition. Abelian Groups

Definition: A subset X of G is said to generate G if G = X . In addition,

if X is finite, then we say that G is finitely generated (f.g., in brief).

So, for example, every cyclic group is finitely generated, as it is generated by a

singleton.

Consider some more examples.

Example 6: Show that every finite group G is finitely generated, but the
converse need not be true.
Solution: For any group G, G = G certainly. So, if G is finite, then G will
be finitely generated.
For the converse, consider Z. It is finitely generated, as Z = {1} .
However, Z is certainly not finite!
***

Example 7: Show that Z × Z is finitely generated, and in fact, Z n is f .g. for

n ≥ 1.

Solution: For any (n , m) ∈ Z × Z, (n , m) = n(1, 0) + m(0 ,1), assuming the

operation as addition. Thus, {(1, 0), (0 ,1)} is a generating set for Z × Z.
In the same way, Z n is finitely generated, as it can be generated by the set of
n-tuples, {(1, 0, K, 0), (0, 1, 0, K, 0), K, (0, 0, K, 1)}.
***

Example 8: Check whether {2} generates Z6 or not.

Solution: Since 1 ≠ n.2 for any n ∈ Z, Z6 is not generated by {2} .

***

Try the following exercises now.

E12) Find the subgroup of Z12 generated by

i) {2, 3}, ii) {4,6}, { }

iii) 8, 6,10 .

E13) Is Z8 generated by {4,6}? Give reasons for your answer.

E14) If a group G is f.g., is the generating set unique? Why, or why not?

E15) If G1 and G 2 are f.g. groups, show that G1 × G 2 is also f.g.

E16) Show that (Q, +) is not finitely generated.

In the next-subsection we focus on particular abelian groups that are generated

‘freely’. 41
Special Groups and
Semigroups
5.3.2 Free Abelian Groups
In this sub-section, we will work only with abelian groups, and we shall
denote the binary operation in an abelian group G by + instead of the
multiplicative notation. So, we will write na instead of a n , if a ∈ G and
n ∈ Z.

Thus, if G = X . Then, by Proposition 1, given any g ∈ G , there exist

k ≥ 1, a 1 , a 2 , ⋅ ⋅ ⋅ , a k ∈ X, n 1 , n 2 , ⋅ ⋅ ⋅ , n k ∈ Z such that
g = n1a 1 + n 2a 2 + ⋅ ⋅ ⋅ + n k a k . …(8)

In other words, each g ∈ G can be written as a Z - linear combination of

finitely many elements of X , as you just saw in Example 7. In case X has the
additional property that the expression of writing any g ∈ G , as a finite
Z -linear combination of the elements of X (as given in Equation 8) is unique,
then we say that X generates G freely. Let’s understand this concept with
some examples.

Example 9: Check whether or not Z is freely generated by {1}.

Solution: You already know that Z = {1} . Now, {1} has the property that each
element n ∈ Z can be uniquely written as n.1, i.e., if n ⋅ 1 = m ⋅1, then n = m.
So, Z is freely generated by {1}.
***

Here we give an important comment related to this example.

Remark 2: Note that the freely generating set need not be unique. e.g., {−1}
also generates Z freely. Thus, Z has two distinct freely generating sets.

Example 10: Show that Z × Z is freely generated by {(1, 0), (0, 1)} .
Solution: Suppose (n , m) is any element of Z × Z. Then
(n , m) = n (1, 0) + m(0 ,1). Suppose (n , m) = n′(1, 0) + m′(0 ,1) also for
n′, m′ ∈ Z. Then (n , m) = (n′ , m′). Hence n = n ′ , m = m′.
Thus, each (n , m) in Z × Z can be uniquely written as
(n, m) = n (1, 0) + m(0,1), i.e., the coefficients n and m in this Z -linear
combination are unique. Hence, Z 2 is freely generated by {(1, 0), (0, 1)}.
***

Example 11: Z 3Z is generated by {1}, but it is not freely generated by {1} .

Solution: Since the elements of Z 3Z are {0 , 1 , 2. 1} ,{1} generates Z 3Z .
Also, as 2 = 2. 1 = 5. 1 and 2 ≠ 5, {1} does not generate it freely.
***

These examples lead us to the following definition.

Definition: An abelian group G is called free abelian if there is a non-empty

subset X of G such that G is freely generated by X. In such a situation, X is
42 called a basis for G.
As you have seen in Example 10, Z × Z is a free abelian group and Abelian Groups

{(1 , 0), (0 ,1)} is a basis. Similarly, Z n is a free abelian group with a basis
{(1, 0, K, 0), (0, 1, K, 0), K, (0, 0, K, 1)}.
Also, note that a free abelian group can have several different bases. For ‘bases’ is the plural
example, Z is free abelian with basis {1}, or with basis {−1}. of ‘basis’.

Why don’t you solve the following exercises now, to help you develop your
understanding of a free abelian group?

E17) Show that if G and G′ are free abelian groups, then G × G′ is a free
abelian group.

E18) If G is a free abelian group with a basis consisting of n elements, then

show that G is isomorphic to Z n .

Let’s try and probe free abelian groups some more. To start with, consider the
following result that you have actually applied in some of the examples above.

Theorem 7: Let X be a subset of an abelian group G. Then the following are

equivalent:
(i) X generates G freely.
(ii) X generates G , and n1x1 + n 2 x 2 + ⋅ ⋅ ⋅ + n k x k = 0 if and only if
n1 = n 2 = K = n k = 0, where x i ∈ X, n i ∈ Z for i = 1, K, k.

Proof: To prove this, we need to prove (i) ⇒ (ii ) and (ii ) ⇒ (i).
(i) ⇒ (ii) : From (i), we know that X generates G. Now, suppose
n1x1 + n 2 x 2 + ⋅ ⋅ ⋅ + n r x r = 0 for some x i ∈ X and n i ∈ Z. Then we have two
ways to write 0 as a Z -linear combination of elements of X, namely,
0 = n1x1 + n 2 x 2 + ⋅ ⋅ ⋅ + n r x r and 0 = 0.x1 + 0.x 2 + ⋅ ⋅ ⋅ + 0.x r .
But, as X generates G freely, any g ∈ G must be uniquely written as a
Z -linear combination of elements of X. Thus, n i = 0 for all i , and hence (i)
implies (ii).

(ii) ⇒ (i) : Let g ∈ G. Since X generates G , we see that g can be written in

the form g = n1x1 + n 2 x 2 + ⋅ ⋅ ⋅ + n r x r for n i ∈ Z, x i ∈ X. Now, suppose g has
another such expression in terms of a Z -linear combination of elements of X,
say g = m1x1′ + m 2 x′2 + L + ms x′s , with mi ∈ Z, x′i ∈ X ∀ i = 1, K , s, and the x′is
may or may not be distinct from the x is. Let us consider the set
{x1 , K, x r , x′1 , K, x′s }. After re-ordering the x is and x ′i s, if necessary, assume
that x 1 = x1′ , x 2 = x ′2 , K , x l = x′l and the rest of the x is and x ′i s are distinct.
Then g = n1 x1 + L + n r x r = m1 x1′ + m 2 x′2 + L + ms x′s
⇒ (n1 − m1 ) x1 + L + (n l − ml ) x l + n l +1x l +1 + L + n r x r − m l +1 x′l +1 − L − ms x′s = 0.
⇒ n i = m i ∀ i = 1,K , l and n j = 0, m k = 0 for j = l + 1,K , r; k = l + 1,K , s (by
our hypothesis (ii)).
⇒ g = n1 x1 + L + n l x l = m1 x ′1 + L + m l x ′l and n i = m i ∀ i = 1, K , l .
Thus, the coefficients are unique, and (i) follows.
43
Special Groups and This theorem helps us check whether a given set is a basis of a given abelian
Semigroups group or not. Consider an example.

Example 12: Check whether or not Z n Z is free abelian, n ≥ 2 .

Solution: You know that {1} generates Z nZ. You also know that n. 1 = 0 ,
with n ≠ 0 . Hence, by Theorem 7,{1} does not generate Z nZ freely.
Along the same lines you can check that no generating set will generate Z nZ
freely.
***

You should do the following exercises now.

E19) Show that a non-trivial finite abelian group cannot be free abelian.

E20) Can a singleton be a basis of Z × Z ? Justify your answer.

As you have seen earlier, a free abelian group can have many bases. For
example, {(1 , 0), (0 , 1)} is a basis of Z × Z.

Another basis is {(1,1), (1, 2)} because each (n , m) ∈ Z × Z can be uniquely

written as (n , m) = (2n − m)(1,1) + (m − n ) (1 , 2).
Note that both these bases have the same number of elements. In fact, any two
bases of a free abelian group must have the same number of elements. We will
now prove this result only in the case that G has a finite basis.

Theorem 8: Let G be a non-trivial free abelian group with a finite basis B.

Then every basis of G is finite, with cardinality B .

Proof: Let B = {x1 , x 2 , ⋅ ⋅ ⋅ , x r } be a basis of G. Then G is isomorphic to Z r ,

as you have shown in E18 .
Let 2G = {2g g ∈ G}. Then 2G is a subgroup of G , and
G 2G ~ Z r 2Z r ~ Z 2 × Z 2 × ⋅ ⋅ ⋅ × Z 2 ( r copies). Thus, o(G 2G ) = 2r.
So, r = log 2 [o(G 2G )].
Similarly, if B′ = {x1′ , K , x ′s } is another basis of G , then
s = log 2 [o(G 2G )] = r.
Hence, any finite basis must have the same number of elements.

Now the question arises: can G have an infinite basis? Suppose it can. Let Y
be an infinite basis for G . Consider a subset of Y consisting of s elements,
say {y1 , y 2 ,K, ys }, where s > r. Let H be the subgroup of G generated by
{y1 , y 2 ,K, y s } , and let K be the subgroup of G generated by the remaining
elements of Y. Then G = < Y > ~ H × K and
G 2G ~ H × K ( 2 H × 2K ) ~ ( H 2 H ) × ( K 2K ) .
Since o(H 2H ) = 2 s , we see that o(G 2G ) ≥ 2s. But o(G 2G ) = 2 r. This is a
contradiction as s > r. Hence our assumption is wrong, and G cannot have an
infinite basis.
44
You have seen why all bases of a free abelian group with a finite basis must Abelian Groups
have the same cardinality. (In fact, this is true even if the group has an infinite
basis, but we shall not be proving this case here.) In view of this, the following
definition makes sense.

Definition: The rank of a finitely generated free abelian group G is defined to

be the number of elements in a basis of G.

For example, Z is of rank one. More generally, Z r is of rank r for r ≥ 1. So,

e.g., the solution of E20 follows immediately from Theorem 8.

Now, consider a subgroup of a free abelian group G. Must it be free abelian? If

so, will its rank have any relationship to the rank of G ? These questions are
addressed in the following theorem.

Theorem 9: Let G be a free abelian group of rank n (≥ 1) and let H be a non-

trivial subgroup of G. Then H is free abelian of rank s ≤ n. Furthermore,
there exists a basis {x 1 , x 2 , ⋅ ⋅ ⋅ , x n } of G , and s positive integers d1 , d 2 , ⋅ ⋅ ⋅ , d s ,
such that d i d i +1 for i = 1, 2, ⋅ ⋅ ⋅ , s − 1 and {d1x1 , d 2 x 2 , ⋅ ⋅ ⋅ , d s x s } is a basis of H.

Proof: We will show that H has a basis of the described form. This will, of
course, show that H is free abelian of rank at most n.

Suppose Y = {y1 , y 2 , ⋅ ⋅ ⋅ , y n } is a basis for G. Then any element h ∈ H can be

expressed in the form k1y1 + k 2 y 2 + ⋅ ⋅ ⋅ + k n y n , where k1 , ⋅ ⋅ ⋅ , k n ∈ Z . Moreover,
if h ≠ 0, then some k i ≠ 0. Among all the bases of G , select a basis Y1 that
yields the non-zero coefficient of least magnitude k i over all the non-zero
elements of H written as Z - linear combinations of elements of Y1 . By
re-numbering the elements of Y1 , if necessary, we can assume that there is
w1 ∈ H such that w 1 = d1y1 + k 2 y 2 + ⋅ ⋅ ⋅ + k n y n , where d1 > 0, and d1 is the
minimal attainable coefficient as just described.
Using the division algorithm, write k j = d1q j + rj , where q j ∈ Z and 0 ≤ rj < d1
for j = 2, ..., n.
Then w 1 = d1 ( y1 + q 2 y 2 + ⋅ ⋅ ⋅ + q n y n ) + r2 y 2 + ⋅ ⋅ ⋅ + rn y n . …(9)
Now let x1 = y1 + q 2 y 2 + ⋅ ⋅ ⋅ + q n y n . Then {x1 , y 2 , ⋅ ⋅ ⋅ , y n } is also a basis for G.
From Equation (9) and our choice of Y1 for minimal coefficient d1, we see that
r1 = r2 = L = rn = 0, otherwise we get a coefficient of lesser value than d1 , a
contradiction. Thus, w 1 = d1x1 , and hence d1x1 ∈ H.

Now consider the basis {x1 , y 2 , ⋅ ⋅ ⋅ , y n } of G. You have seen that any element
of H can be expressed in the form h1x1 + k 2 y 2 + ⋅ ⋅ ⋅ + k n y n , h1 , k 2 , K , k n ∈ Z.
Since d1x1 ∈ H, we can subtract a suitable multiple of d1x1 and then use the
minimality of d1 to see that h1 is a multiple of d1 , along the lines we followed
to reach Equation 9.
Moreover, it follows that k 2 y 2 + ⋅ ⋅ ⋅ + k n y n ∈ H.
Among all such bases {x1 , y 2 , ⋅ ⋅ ⋅ , y n }, we choose Y2 = {y 2 ,K, y n } that leads to
some k i ≠ 0 of minimal magnitude.
45
Special Groups and It is possible that all k i are zero for all bases, in which case, H is generated by
Semigroups
d1x1 and we are done.
Otherwise, re-numbering the elements of Y2 , we can assume that there is
w 2 ∈ H such that w 2 = d 2 y 2 + k 3 y3 + ⋅ ⋅ ⋅ + k n y n ,
where d 2 > 0 and d 2 is minimal as described above.

Exactly as in the procedure done earlier, we can modify our basis from
Y2 = {x1 , y 2 ,K , y n } to a basis {x1, x 2 ,y3 ,K, y n } for G , where d1x1 , d 2 x 2 ∈ H.
Writing d 2 = d1q + r for 0 ≤ r < d1 and q ∈ Z, we see that
{x1 + qx 2 , x 2 , y3 , K , yn } is a basis for G and d1x1 + d 2 x 2 = d1 (x1 + qx 2 ) + rx 2
is in H. By our minimal choice of d1, we have r = 0, so d1 divides d 2 .

We now consider all bases of the form {x1 , x 2 , y3 , K, y n } for G and examine
elements of H of the form k 3 y3 + ⋅ ⋅ ⋅ + k n y n . You must have realised the
pattern by now. The process continues until we obtain a basis
{x1, x 2 , K, x s , ys +1,K, y n }, till the only element of H of the form
k s +1ys +1 + L + k n y n is zero, i.e., all k i are zero. We then let
x s +1 = y s +1,K, x n = y n and obtain a basis for G of the form described in the
statement of the theorem.

What the theorem above says is that every subgroup of a free abelian group of
rank n looks structurally like Z r for some r ≤ n . Let us consider an example.

Example 13: Show, by example, that it is possible for a proper subgroup of a

free abelian group of finite rank r also to have rank r.
Solution: Consider Z. This is free abelian of rank one. Now consider 3Z. This
is also free abelian, generated by {3}, and hence of rank one.
***

Example 14: Show that Pn = {a 0 + a1 + a 2 x 2 + L + a n x n a i ∈ Z} is a f.g. free

abelian group of rank n + 1.
Solution: Consider X = {1, x , K , x n }. You know that X generates Pn . Also,
n n
if ∑ a x = ∑ b x , then a
i =0
i
i

i =0
i
i
i = b i ∀ i = 1, K , n. Hence the result.

***

Let us now look at the order of the elements of an abelian group. You know
that if G is a free abelian group with a basis X, then nx = 0 ⇒ n = 0 ∀ x ∈ X.
However, the abelian group Z 2 × Z has an element (1, 0) of order 2 and an
element (0, 1) of no finite order. This leads us to the following definition.

Definitions: 1) Let G be a group. An element of G with finite order is called

a torsion element of G.
2) The set of torsion elements of an abelian group G is a subgroup of G ,
called the torsion subgroup of G. This is denoted by Tor(G).
3) An abelian group G is called a torsion group if Tor(G ) = G , and G is
called a torsion-free group if Tor(G ) = {0}.
46
 Abelian Groups
For example, Tor(Z 2 × Z) = Z 2 × {0} ~ Z 2 and Tor(Z) = {0}.
Thus, Z is torsion-free.

Example 15: If G is a finite group, find Tor(G ).

Solution: Since every element of G is of finite order, Tor(G ) = G. Hence G
is a torsion group.
***

Again, it is time for you to check your understanding of what you have studied
so far.

E21) Mark each of the following true or false. Give reasons for your choices.
i) These exists a free abelian group of every positive integer rank.
ii) If X is a basis for a free abelian group G and X ⊆ Y ⊆ G , then Y
is a basis for G.
iii) If K is a non-trivial subgroup of a finitely generated free abelian
group, then K is free abelian.
iv) If K is a non-trivial subgroup of a finitely generated free abelian
group, then G K is free abelian.
v) Any two free abelian groups of the same finite rank are isomorphic.

E22) i) Show that Tor (G ) is a subgroup of G , if G is abelian.

ii) If G is not abelian, will Tor(G ) still be a subgroup of G ? Why, or
why not?

E23) Show that the torsion subgroup of a finitely generated free abelian group
is {0}.

E24) Show that Tor (G1 × G 2 ) = Tor (G1 ) × Tor (G 2 ) , where G1 and G 2 are
two abelian groups.

E25) Suppose G is a finite abelian group and F is a finitely generated free

abelian group. Show that G × F is a finitely generated abelian group, and
its torsion subgroup is isomorphic to G.

E26) Find the orders of the torsion subgroups of Z 4 × Z × Z3 and Z12 × Z × Z12 .

We now have all the tools in hand to understand what a f .g. abelian group
looks like, in general.

5.4 STRUCTURE THEOREMS

In Sec.5.2 you studied the structure of finite abelian groups. In this section, you
will study the proof and applications of the following structure theorem for
finitely generated abelian groups, which is a generalisation of the invariant
factor decomposition of finite abelian groups.
47
 Special Groups and Theorem 10 (Structure Theorem for Finitely Generated Abelian Groups):
Semigroups
Let G be a finitely generated abelian group. Then
(i) G ~ Z r × Z m1 × Z m2 × ⋅ ⋅ ⋅ × Z mt , for some integers r, m1, m 2 ,K, m t
satisfying r ≥ 0, m i ≥ 2 for all i, and mi m i +1 for 1 ≤ i ≤ t − 1.
(ii) The integers r, m1 , m 2 ,K , m t , satisfying the expression in (i) above, are
uniquely determined by G.

Proof: Let G be generated by the set {g1, g 2 , K , g n }. Let F = Z n . Consider the

map ψ : F → G given by ψ (a1 , a 2 , ⋅ ⋅ ⋅ , a n ) = a1 g1 + a 2 g 2 + L + a n g n . You can
check that ψ is a well-defined homomorphism and is surjective. Let
H = Ker ψ . By Theorem 9, there is a basis {x1 , x 2 ,K, x n } of F such that
{d1x1 ,K, d s x s } is a basis for H, where d i divides d i +1 for i = 1,K , s − 1, s ≤ n.
Consequently,
Z {0} ~ Z G ~ F H ~ (Z × Z × K × Z ) (d1Z × d 2Z × K × d sZ × {0} × K × {0})
14243
( n − s ) times
Z {1} ~ {0}
~ Zd × Zd × K× Zd × Z
1×4
Z2
4 ×K
4×4
3Z.
1 2 s
( n − s ) times

It is possible that d1 = 1 , in which case Z d1 = {0} and can be dropped (upto

isomorphism) from this product. Similarly, d 2 may be dropped if it is 1, and so
on. If m1 is the first d i > 1, m 2 is the next, and so on, then G is isomorphic to
a direct product of cyclic groups of the form given in the theorem, with
r = n − s. Hence (i) is proved. (Note that if n = s, r = 0. )

For showing the uniqueness, suppose G is in the form given in (i) and
G ~ Z r′ × Z m1′ × Z m′2 × K × Z m′b also, for some integers r′, m1′ , m′2 , K m′b
satisfying r′ ≥ 0, m′i ≥ 2 for all i and m′i m′i +1 for all i = 1, K , b.
Consider the subgroup Tor (G ) of G.
By E25, you know that Tor (G ) ~ Z m1 × Z m 2 × K × Z m t and
Tor (G ) ~ Z m′1 × Z m′2 × K × Z m′b .
Since Tor (G ) is finite abelian, by the uniqueness of its invariant factors we see
that t = b, and mi = m′i for all i = 1, K, t.
Furthermore, as G Tor (G ) ~ Z r and G Tor G ) ~ Z r ′ , it follows by Theorem 8
that r = r′. This proves the assertion (ii) and completes the proof of
Theorem 10.
In view of the uniqueness in Theorem 10, the following definitions make sense.

Definitions: For a finitely generated abelian group G ,

G ~ Z r × Z m1 × Z m2 × L × Z m t , with r ≥ 0, m i ≥ 2, m i m i+1 ∀ i = 1, K , t − 1 . Then,
Enrico Betti (1823-1892) 1) the integer r in this decomposition is called the free rank, or Betti
was an Italian mathematician. number, of G.
2) the integers m1, m 2 ,K, m t are called the invariant factors of G.
3) the description of G in the form given is called the invariant factor
decomposition of G.
48
For instance, the free rank of a free abelian group is the same as its rank. If it is Abelian Groups
of rank n , then its invariant factor decomposition is Z n .

The following theorem is an alternative form in which the structure of a f.g.

abelian group can be given, and it is a generalisation of Theorem 4.

Theorem 11 (Elementary Divisor Decomposition of a Finitely Generated

Abelian Group): Let G be a finitely generated abelian group. Then
G ~ Z r × Z q e1 × Z q e2 × ⋅ ⋅ ⋅ × Z q es , where r ≥ 0 is an integer and q1e1 , q e22 , K , q es s e e e
q1 1 , q 22 , K , q s s in
1 2 s

are positive powers of primes which may not be distinct. Moreover, Theorem 11 are called the
elementary divisors of G.
r, q1e1 , q e22 , K, q es s are uniquely determined by G.

Proof: Let the invariant factor decomposition of G be

G ~ Z r × Z m1 × K × Z m t , r ∈ N, m1 , K , m t ∈ Z.
Now, we can decompose each cyclic group Z m i into a direct product of cyclic
groups of prime power order. This way, we can express G in the form required
in the statement.
The uniqueness of r and the prime powers can be proved by proceeding as in
the proof of part (ii) of Theorem 10. This completes the proof.

Consider an example.

Example 16: Find the Betti number, and the invariant factors of,
G = Z 6 × Z14 × Z15 × Z 7 .
Solution: Here the Betti number is 7.
Since G ~ (Z 2 × Z 3 ) × (Z 2 × Z 7 ) × (Z 3 × Z 5 ) × Z 7 , by arranging the powers of the
primes we get G ~ Z 6 × Z 210 × Z 7. Thus, the invariant factors of G are 6, 210.
***

Try some exercises now.

E27) Find the Betti number, and invariant factors, of the group
Z × Z 6 × Z × Z × Z12 × Z10 .
Also write the elementary divisor decomposition of this group.

E28) What is the Betti number of a finite abelian group?

E29) Is it true that any two finitely generated abelian groups with the same
Betti number are isomorphic? If yes, prove this. If not, write the
necessary and sufficient conditions for two finitely generated abelian
groups to be isomorphic.

E30) Let G be a finitely generated abelian group and H be a subgroup of G.

i) Is G H a finitely generated abelian group?
ii) If we assume that G is a free abelian group, is G H free abelian?
Justify your answers.
49
Special Groups and With this we come to the end of our discussion on the structure of abelian
Semigroups groups. Let us take a brief look at what you have studied in this unit.

5.5 SUMMARY
In this unit, we have discussed the following points.

1. The direct product of groups, or of subgroups, and their properties.

2. The proof of the Structure Theorem for Finite Abelian Groups, namely,
a finite abelian group G can be written in the form
Z p e1 × Z p e2 × K × Z p e r (elementary divisor decomposition), or as
1 2 r

Z m1 × Z m 2 × K × Z m t with mi ≥ 2 and m i m i +1 ∀ i (invariant factor

decomposition).

3. Applying the structure theorem for finite abelian groups to obtain all
possible abelian groups, up to isomorphism, of a given order.

4. The proof of the converse of Lagrange’s theorem for finite abelian

groups.

5. The definition, and examples, of finitely generated groups.

6. What a free abelian group is, its rank and its properties.

7. i) The proof of the Structure Theorem for Finitely Generated

Abelian Groups, namely, any finitely generated abelian group
G ~ Z r × Z m1 × Z m2 × K × Z mt with mi mi +1 , mi ≥ 2 ∀ i and r ≥ 0.
r is the rank, or Betti number, of G, and the mi are the invariant
factors of G.
ii) The proof of the Alternate Structure Theorem, i.e., the Elementary
Divisor Decomposition of a Finitely Generated Abelian Group.
This states that any finitely generated abelian group
G ~ Z r × Z q e1 × L × Z q es , where r ≥ 0 is an integer, q1 , q 2 , K , q s
1 s

are primes which may not be distinct. Moreover, r, q1e1 , q e22 , K , q ess
are uniquely determined by G .

8. Obtaining the rank, invariant factors and elementary divisors of any

given finitely generated abelian group.

5.6 SOLUTIONS / ANSWERS

E1) Let G1 and G 2 be abelian groups of order p1n1 p n2 2 K p nk k and θ : G1 → G 2

be the isomorphism. For 1 ≤ i ≤ r, let θi be the restriction of θ to G1 (p i ).
You should check that θi is a 1-1 homomorphism, and θi (G1 (p i )) is a
subgroup of G 2 . Also, θ being 1-1, θi (G1 (pi )) = G1 (pi ) = pin i , and
hence G 2 (pi ) = θi (G1 (p i )) as the Sylow pi subgroup of G 2 is unique.
Thus, θi is a 1-1 onto mapping from G1 (pi ) to G 2 (pi ), and hence an
isomorphism from G1 (p i ) to G 2 (pi ).
50
 Abelian Groups
Conversely, if G1 (p i ) ~ G 2 (p i ) ∀ i = 1, K , k , then
G1 ~ ∏ G 1 ( p i ) ~ ∏ G 2 ( p i ) ~ G 2 .
i i

E2) We proceed by induction on r. When r = 1 , G = p . Then G ~ H1 and

G ~ K1 , so m = n = 1 and H1 = K1 .
Now suppose that the statement is true for all abelian groups of order less
than p s , for some s ∈ N . For any abelian group L, Lp = {x p x ∈ L} is a
subgroup of L. Further, if L is finite then L Lp = p. Also
G ~ H1 × H 2 × ⋅ ⋅ ⋅ × H m implies that G p ~ H1p × H p2 × K × H pm′ , where m′ is
the largest integer i such that H i > p. Similarly, G ~ K 1 × K 2 × ⋅ ⋅ ⋅ × K n
implies that G p ~ K1p × K p2 × K × K pn′ , where n′ is the largest integer j
such that K j > p. Since G p < G , by induction we have m′ = n′ and
H pi = K ip for i = 1, 2,K, m′. Since H i = p H ip , this proves that
H i = K i for i = 1, 2,K, m′.
All that remains to be proved is that the number of His of order p equals
the number of K is of order p; that is, we must prove that
n − n′ = m − m′. This follows from the fact that
H1 H 2 L H m′ p m−m′ = G = K1 K 2 L K n′ p n−n′ , m′ = n′ and H i = K i
for 1 ≤ i ≤ m′.

E3) The elementary divisors of G ~ Z 5 × Z 52 × Z112 are 5, 52 ,112 .

Since Z 55 ~ Z 5 × Z11 , Z 55 × Z 55 × Z 5 ~ Z 5 × Z11 × Z 5 × Z11 × Z 5 .
Its elementary divisors are 5, 5, 5,11,11. These are not the same as those
of G.

E4) i) 105 = 3.5.7. Therefore, looking at the algorithm given before the
exercise, Z 3 × Z 5 × Z 7 is the only abelian group of order 105. Note
that Z 3 × Z 5 × Z 7 ~ Z105 .

ii) 270 = 21.33.51. Therefore, looking at the partitions of 1, 3, 1, it

follows that the non-isomorphic abelian groups of order 270 are
Z 2 × Z 27 × Z 5 , Z 2 × Z 3 × Z 9 × Z 5 and Z 2 × Z 3 × Z 3 × Z 3 × Z5 .

iii) 9801 = 34.112. Now, the partitions of the exponents are

4 2
1+ 3 1+1
1+ 1 + 2
2+2
1+1+1+1
Therefore, the required non-isomorphic abelian groups are
Z 81 × Z121 ,
Z 3 × Z 27 × Z121 ,
51
Special Groups and Z 3 × Z 3 × Z 9 × Z121 ,
Semigroups
Z 9 × Z 9 × Z121 ,
Z 3 × Z 3 × Z 3 × Z 3 × Z121 ,

Z 81 × Z11 × Z11 ,
Z 3 × Z 27 × Z11 × Z11 ,
Z 3 × Z 3 × Z 9 × Z11 × Z11 ,
Z9 × Z9 × Z11 × Z11 ,
Z3 × Z3 × Z3 × Z3 × Z11 × Z11.

E5) i) The smallest positive integer n such that there are exactly two
non-isomorphic abelian groups of order n is n = 4. This is
because for n = 2, 3, the groups of order n are cyclic, and hence,
unique up to isomorphism. For n = 4, there are two non-abelian
groups of order n , namely Z 4 and Z 2 × Z 2 .
ii) The smallest positive integer n such that there are exactly three
non- isomorphic abelian groups of order n is n = 8. This is
because for n = 2, 3, 5, 7, the groups of order n are cyclic, and
hence, unique up to isomorphism. For n = 4, there are two
non-abelian groups of order n, as shown in (i) above.
For n = 6, there is a unique abelian group of order n , i.e.,
Z 2 × Z3 ~ Z 6 .
For n = 8, there are three non-isomorphic abelian groups, namely,
Z8 , Z 4 × Z 2 , Z 2 × Z 2 × Z 2 .

E6) In both the cases, there is a unique group since the exponents of the
primes are 1.

E7) 120 = 23.3.5. Therefore, the groups of order 120 are

Z8 × Z 3 × Z 5 , Z 2 × Z 4 × Z 3 × Z 5 and Z 2 × Z 2 × Z 2 × Z 3 × Z 5 .
The first group has only one element of order 2, namely, ( 4, 0 , 0 ).
The second group has precisely three elements of order 2, namely,
( 1, 0, 0, 0 ), (1 , 2, 0, 0 ), ( 0, 2, 0, 0 ).
The third group has 7 elements of order 2, namely, ( x , y , z , 0 , 0 ), where
( x , y , z ) ∈ Z 2 × Z 2 × Z 2 \ {( 0 , 0 , 0 )}. Therefore, the required group is
Z 2 × Z 4 × Z 3 × Z 5 . Therefore, along the same lines as in Example 4, you
can check that if G has precisely 3 elements of order 2, then
G ~ Z 2 × Z 4 × Z3 × Z5 .

E8) By Theorem 4, you can assume that G = Z q e1 × Z q e2 × K × Z q es , where

1 2 s

q1 , q 2 , L , q s are primes (not necessarily distinct) and ei ≥ 1 for all i.

Since G = q1e1 q e22 Kq se s , and m divides G , we must have
m = q1f1 q f22 K q fss , where 0 ≤ f i ≤ ei for all i.
Now if a i is a subgroup of Z q ei of order q fii (this is possible since the
i

52
 converse of Lagrange’s theorem is true for cyclic groups), then Abelian Groups
a1 × a 2 × ⋅ ⋅ ⋅ × a s is a subgroup of G of order m.

E9) There are 6 types of abelian groups of order 108 = 22.33 , namely,
i) Z 4 × Z 27
ii) Z 2 × Z 2 × Z 27
iii) Z 4 × Z3 × Z 9
iv) Z 2 × Z2 × Z3 × Z9
v) Z 4 × Z3 × Z3 × Z3
vi) Z 2 × Z 2 × Z3 × Z 3 × Z 3
So, the number of elements of order 3 in the groups (i ) − (vi ) is given as
in the following table:

Group Number of elements of order 3

(i) 2 [i.e., ( 0, 9 ), ( 0, 18)]
(ii) 2 [i.e., ( 0, 0 , 9 ), ( 0, 0, 18)]
(iii) 8 [i.e., ( 0, x , y), x ∈ Z 3 , y ∈ 3Z 9 , both x and y not
zero simultaneously.]
(iv) 8
(v) 26 [i.e., ( 0, x , y, z ), x , y, z ∈ Z 3 , not all zero
simultaneously.]
(vi) 26

Now recall that if H is a subgroup of order 3 in a group G , then H is

cyclic and is generated by an element of order 3. Furthermore, H has
precisely 2 elements of order 3 and both of them generate it.
Consequently, groups (i) and (ii) have unique subgroups of order 3;
groups (iii) and (iv) have four subgroups of order 3; and the groups (v)
and (vi) have 13 subgroups of order 3.

E10) Abelian groups of order 56 have been constructed in Example 2.

Elementary Divisor Decomposition Invariant Factor Decomposition

Z8 × Z 7 Z 56
Z 4 × Z2 × Z 7 Z 2 × Z 28
Z 2 × Z2 × Z 2 × Z7 Z 2 × Z 2 × Z14

E11) We have the following:

G Elementary divisor form Invariant factor form

Z 2 × Z 2 × Z5 × Z 5 already in this form Z10 × Z10
Z 9 × Z 25 × Z 35 × Z 4 Z 9 × Z 25 × Z 7 × Z 5 × Z 4 Z 6300 × Z 5
Z 5 × Z10 × Z 50 Z 5 × Z 5 × Z 25 × Z 2 × Z 2 already in this form
53
Special Groups and
E12) i) Let H be the subgroup of Z12 generated by {2, 3}. Then
Semigroups
1 = 3 − 2 ∈ H. Therefore, 1 ⊆ H. But 1 = Z12 . Therefore,
H = Z12 .
ii) 2 = 6 − 4 ∈< 4, 6 > ⊆ < 2 > .
∴ < 4, 6 > = < 2 > .

iii) Let K be the subgroup of Z12 generated by {6, 8, 10}. Then

2 = 8 − 6 ∈ K. Therefore, < 2 > ⊆ K . But {6, 8, 10} ⊆ < 2 > .
Therefore, K = < 2 > = {0 , 2, 4, 6, 8 , 10}.

E13) No. Because if H is the subgroup of Z8 generated by {4, 6}, then it can
be shown, as in E12, that H = < 2 > = {0, 2, 4, 6}, and so H ≠ Z 8 .

E14) The generating set need not be unique. For example, both {4, 6} and
{6, 8, 10} generate < 2 > in Z12 .
Similarly, both {1} and {−1} generate Z.

E15) Let {a 1 , K , a r } and {b1 ,K , b s } generate G1 and G 2 , respectively.

Any element of G1 × G 2 is of the form (g1 , g 2 ), where g1 ∈ G1 , g 2 ∈ G 2 .
n
Since g1 ∈ G1 , g1 = a 1n1 L a r r , n i ≥ 0. Similarly, g 2 = b1m1 L b sms , m i ≥ 0.
m
Therefore, (g1 , g 2 ) = ∏{(a ini , b j j ), i = 1,K, r, j = 1,K , s}.
m m
Also. (a ini , b j j ) = ∏ [(a i , e 2 ) ni (e1 , b j ) j ], where e1 , e 2 are the identities
of G1 and G 2 , respectively.
Thus, G1 × G 2 has a finite set generating it, viz.,
{(a i , e 2 ), (e1 , b j ) i = 1, L , r, j = 1, K , s}.

a1 a 2 a
E16) Suppose (Q, + ) is finitely generated, say generated by , ,K, n .
b1 b 2 bn
a a a
Then any rational number is expressed as k1 1 + k 2 2 + K + k n n for
b1 b2 bn
some integers k1 , k 2 ,K, k n . Let l = l.c.m (b1 , b 2 ,K , b n ).
1 1 a a
Consider ∈ Q. Suppose = k1 1 + L + k n n . Then
l +1 l +1 b1 bn
b1 L b n = (l + 1) (k1a1 + L k n a n ), which is not possible. Hence our
assumption that (Q, + ) is finitely generated is wrong.

E17) If G is free abelian with basis X and G′ is free abelian with basis X′,
then you can show that G × G′ is free abelian with basis
{( x, 0), (0, x′) x ∈ X, x ′ ∈ X′}.

E18) Suppose that G is free abelian with basis {x1 ,K, x n }. Define
θ : Z n → G : θ(a 1 , K , a n ) = a 1x1 + L + a n x n . You should check that θ is
a well-defined group homomorphism, which is 1-1 and onto.
54
E19) Let G be an abelian group of order n, n ≥ 2. Suppose G is free abelian Abelian Groups
and let X be a basis of G. Consider x ∈ X. Since x ∈ G , nx = 0. This is
not possible if X is a basis, unless n = 0. We reach a contradiction.
Hence G is not free abelian.

E20) Suppose {(a , b)} generates Z × Z. Then each element of Z × Z is of the

form (na , nb), where n ∈ Z. Now consider (a + 1, b) ∈ Z × Z. Then
na = a + 1, nb = b. Thus, n = 1 and a = a + 1, which is absurd. Hence, we
reach a contradiction. Thus, a singleton cannot generate Z × Z.

E21) i) True. For any n ≥ 1, Z n is free abelian of rank n.

ii) False. {1} is a basis of Z. Also {1} ⊆ {1, 2} ⊆ Z, but {1, 2} is not a
basis because, for example, 0 = 0.1 + 0.2 = 2.1 + (−1).2 are two
different ways of writing 0 as a Z -linear combination of 1 and 2.
iii) True. Follows from Theorem 9.
iv) False. 2Z is a subgroup of the free abelian group Z, but Z 2Z ,
being finite, is not free abelian.
v) True. If G and G ′ are free abelian of rank r, then both are
isomorphic to Z r , and hence isomorphic to each other.

E22) i) Firstly, Tor (G ) ≠ « since 0 ∈ Tor (G ). Next, for g, h ∈ Tor(G ), let

the order of g and h be n and m, respectively. Then
nm.(g − h ) = 0 implies that g − h ∈ Tor(G ) (we have written the
binary operation in G additively). Hence Tor G ) ≤ G.
ii) It need not be a subgroup.
For example, let G = GL2 (R).
 0 1 0 1
Take A =   , B= .
 − 1 0  − 1 − 1
Then A4 = I, B3 = I, so that A, B ∈ Tor (G ).
1 2
However, AB =  .
0 1 
n 1 2n 
You can check that (AB) =  , so that AB ∉ Tor (G ).
0 1 
Hence, Tor (G ) <| G.

E23) Let F be a free abelian group. Suppose a ∈ F is an element of finite

order. By Theorem 9, a is free abelian. Also, since a ∈ Tor (F), a is
finite. By E19, this is possible only if a is trivial, i.e., a = {0}.

E24) ( x, y) ∈ Tor (G1 × G 2 )

⇔ (x , y) n = (e1 , e 2 ) for some n ∈ N
⇔ x n = e1 , y n = e 2 for some n ∈ N
⇔ x ∈ Tor (G1 ), y ∈ Tor (G 2 ).
Hence the two sets are equal.
55
Special Groups and E25) G × F is abelian because
Semigroups
(a , b). (a ′, b′) = (a. a ′, b.b′) = (a ′.a , b′.b) = (a ′, b′).(a , b) for all
(a , b), (a′, b′) ∈ G × F.
Also, if F is generated by the finite set X, then G × F is generated by
G × X, which is a finite set. Hence, G × F is also finitely generated.
Next, Tor (G × F) = Tor (G ) × Tor (F) = G × {e}, by E23 and E24.
~ G.

E26) By E25, the torsion subgroup of Z 4 × Z × Z3 is isomorphic to Z 4 × Z 3 ,

which has order 12.
The torsion subgroup of Z12 × Z × Z12 has order 144.

E27) We have
Z × Z 6 × Z × Z × Z12 × Z10 ~ Z 3 × Z 6 × Z12 × Z10
~ Z 3 × Z 2 × Z3 × Z 4 × Z 3 × Z 5 × Z 2
~ Z3 × Z 4 × Z2 × Z 2 × Z3 × Z3 × Z5
This is the elementary divisor decomposition of the given group.
Using the method explained in the Structure Theorem,
Z 4 × Z 2 × Z 2 × Z 3 × Z3 × Z 5 is isomorphic to Z 2 × Z 6 × Z 60 , so that the
invariant factors of the given group are 2, 6, 60. Furthermore, its Betti
number is 3.

E28) The Betti number of a finite abelian group is 0.

E29) No. For example, Z × Z 2 and Z × Z 3 have the same Betti number but are
not isomorphic. This is because, for example, Z × Z 2 has an element of
order 2 but no element of order 3; similarly, Z × Z 3 has an element of
order 3 but no element of order 2.
The necessary and sufficient condition for two finitely generated abelian
groups to be isomorphic is that the two groups should have the same
Betti number and the same invariant factors; or, equivalently, the two
groups should have the same Betti number and the same elementary
divisors. This has been proved in the two Structure Theorems in this
section.

E30) i) The group G H is finitely generated. In fact, if e1, e 2 , K, e n

generate G , then e1 , e2 , K , e n generate G H over Z.

ii) No, the group G H need not be free. For example, Z is a free
group over Z generated by 1. But, the quotient Z 2 = Z 2Z is not a
free abelian group.

56
 Group Presentations
UNIT 6 GROUP PRESENTATIONS
Structure Page No.
6.1 Introduction 57
Objectives
6.2 Free Groups 58
6.3 Generators and Relations 64
6.4 Classifying Groups of Small Order 68
6.5 Summary 71
6.6 Solutions / Answers 72

6.1 INTRODUCTION
In Block 1, you have studied groups like D8 or S3 , which are generated by two
elements satisfying certain properties. In the previous unit, you have also
studied about abelian groups being generated by certain sets. In this unit, we
will look at this idea of generators in a larger context. Here, we will present a
convenient way to define a group with certain prescribed properties. The idea is
to form a group by giving a set of generators for the group and certain
equations (called relations) that we want these generators to satisfy. Further, we
want the group to be the largest possible one which is generated by this set of
generators and subject to these relations. This way of expressing a group is
called a group presentation. One of the earliest presentations of a group by
generators and relations was given by the Irish mathematician, William Rowan
Hamilton, in 1856, in his presentation of the icosahedral group. The first
systematic study of presentations was given by Walther von Dyck, a student of
Felix Klein, in the early 1880s, laying the foundations for combinatorial group
theory. Fig. 1: The German
mathematician
Walther von Dyck
In the previous unit, you studied free abelian groups. In Sec.6.2, you will study (1856-1934)
what a free group is. You will see that this concept is very different from that
of a free abelian group. You will also see that every group is the quotient group
of some free group.

In Sec.6.3, the focus is on generators, relations and presentations of groups. In

the next section, Sec.6.4, you will be able to build on your understanding of
group presentations to classify certain groups of small order, an exercise you
had begun in Unit 3. In fact, at several points in Sec.6.4, you will need to recall
and apply results you have proved in Unit 3.

Let us now look at the precise learning objectives of this unit.

Objectives
After studying this unit, you should be able to:
• define, and give examples of, free groups;
• explain what ‘defining relations’ and ‘presentation of a group’ are;
• describe some finitely presented groups.
57
Special Groups and
Semigroups
6.2 FREE GROUPS
In the previous unit, you studied free abelian groups. You also know that Z r is
a free abelian group of rank r. Here we shall look at the concept of freeness of
non-abelian groups.

To start with, what does the idea of freeness mean? Doesn’t it give a sense of
‘no ties, no links, no relations’ between the elements? In fact, this is what a free
group on a set is. And this is defined in the following way, which is equivalent
to the same idea of freeness.

Definition: Let S be a non-empty set, and F be a group such that there is a

map i : S → F. The ordered pair (F, i) is called a free group on S if whenever
F there is a group G and a map α : S → G , there will be a unique group
~
α homomorphism α ~ : F → G such that α
~ o i = α.
i Diagrammatically we show this as in Fig. 2, and say that the diagram is
α commutative, that is, whether you map an element from S to G via F, or
S G directly, there is no difference.
Fig. 2: (F, i) is a free
group on S.
Now, an important comment about a free group!
Remark 1: This defining property is called the universal mapping property.
It shows us how F is ‘free’ on S . Any mapping from S to a group is
extended to a homomorphism from F to G . So the elements in F have no
relation with each other except that they come from S .

Now, the question is, are there any such groups? There are actually infinitely
many such groups. To see this, let us take any set S = {a , b, c,K}, where
a , b, c, etc. are distinct symbols. Given S, we construct a new set
S −1 = {a −1 , b −1 , c −1 , K}, where a −1 , b −1, c −1, K are distinct symbols,
S ∩ S−1 = «, and there is a one-one correspondence between the elements of S
and S−1 given by x ↔ x −1 , for x ∈ S.
Define the set W (S) to be the collection of all formal finite strings of the form
x1 x 2 ⋅ ⋅ ⋅ x k , where each x i ∈ S ∪ S−1 . The elements of W (S) are called words
from S . We also permit the string with no element to be in W (S). This word
is called the empty word, and is denoted by e.
Define ‘multiplication’ on W (S) by juxtaposition, i.e., if x1 x 2 ⋅ ⋅ ⋅ x k and
y1 y 2 ⋅ ⋅ ⋅ y s belong to W (S), then
( x1 K x k ) ⋅ ( y1y 2 K ys ) = x1x 2 K x k y1y 2 K ys .
Note that this operation is closed on W (S), is associative, and the empty word
e acts as the identity w.r.t. this operation.

Next, if we are wanting to define a group, we need to see if the inverse of an

element can be defined in W (S) . It seems reasonable to take the inverse of
x ∈ S as x −1 . This means that the word xx −1 , where x ∈ S, should be ‘the
same as’ the empty word, e. But first, what does ‘same’ mean? Let’s see.
‘ u ~ v ’ is read as ‘ u is
related to v ’.
‘ u ~/ v ’ is read as ‘ u is We define a relation ~ on W (S) as follows:
not related to v ’. For u, v ∈ W(S), u ~ v iff v can be obtained from u by a finite sequence of
58 insertions or deletions of words of the form xx −1 or x −1x , where x ∈ S.
For instance, if S = {a , b, c}, the word abcc −1b ~ abb and a −1aabb −1a −1 ~ e , but Group Presentations

b −1acb ~/ ac .

You should now check that ~ is an equivalence relation.

E1) Show that the relation ~, defined above, is an equivalence relation on

W(S).

Now, you have seen that we have deleted subwords of the form xx −1 to get an A subword is a word that
equivalent word. This kind of action on a word is called an elementary is a part of another word.
reduction of a word. For example, suppose w = a −1aabb −1a −1 , where a , b ∈ S .
Then abb −1a −1 is an elementary reduction of w ; the word a −1aaa −1 is another
elementary reduction of w. Of course, more elementary reductions of w are
possible. If w 1 is an elementary reduction of w , we write this as w → w1.
Also note that w ~ w 1 .

This discussion leads us to the following definition.

Definition: A word w ∈ W(S) is called reduced if no elementary reduction of

w is possible.

For example, abb is a reduced word if ab ~/ e.

So, to get a reduction of w, we apply a sequence of elementary reductions

starting from w and ending at a reduced word:
w → w1 → ⋅ ⋅ ⋅ → w n , where w n is reduced.
You must have noted that w ~ w n . Such a w n is called a reduced form of
w.

Now, by the reduction process, you can see that each word in W(S) has a
reduced form. There could be different routes for reaching the reduced form.
For example, the following are two different ways of reducing
w = a −1aabb −1a −1 :
a −1aabb −1a −1 → abb −1a −1 → aa −1 → e
and
a −1aabb −1a −1 → a −1aaa −1 → a −1a → e

However, both routes end up with the same reduced form e of w. This is true
in general. To show this, we need the following lemma.

Lemma 1: For any two elementary reductions w → w 1 and w → w 2 of a

word w ∈ W(S) , one of the following holds:
(i) w1 = w 2 ;
(ii) There exists a word w 0 ∈ W(S) with elementary reductions w 1 → w 0
and w 2 → w 0 .
59
Special Groups and Proof: Let us denote the elementary reductions w → w 1 and w → w 2 by λ1
Semigroups
and λ 2 , respectively. There are two possible ways to carry out these reductions.

−1 −1
Case 1 (Disjoint reductions): In this case w = u1 y1 y1 u 2 y 2 y 2 u 3 , where
u1 , u 2 , u 3 ∈ W(S), y1 , y 2 ∈ S ∪ S−1 are distinct, and applying λ i deletes the
−1
subword y i y i , i = 1, 2 . So, we have
λ −1 λ
w →
1
u 1u 2 y 2 y 2 u 3 →
2
u 1u 2 u 3
λ2 −1 λ1
w → u1 y1y1 u 2 u 3 → u 1u 2 u 3 .
Hence, taking w 0 = u1u 2u 3 , (ii) of the statement holds.

Case 2 (Overlapping reductions): In this case, w takes the form

w = u1yy −1yu 2 , where u1 , u 2 ∈ W (S), y ∈ S ∪ S−1 . We may assume that λ1 and
λ 2 delete the subword yy −1 and y −1 y, respectively. If this happens, we have
λ
w = u 1 yy −1 yu 2 →
1
u 1 yu 2
λ2
w = u1 yy −1 yu 2 → u1 yu 2 .
Hence w 1 = u1yu 2 = w 2 , i.e., (i) holds.

Let us now prove what we need for seeing if we can convert the set of
equivalence classes in W (S), corresponding to ~, into a group.

Proposition 1: Let w ∈ W (S) . Then any two reductions of w result in the

same reduced form, i.e., if w → w ′1 → ⋅ ⋅ ⋅ → w ′n and w → w 1′′ → ⋅ ⋅ ⋅ → w ′m′ ,
where w ′n and w ′m′ are reduced words, then w ′n = w ′m′ .

Proof: Let w = x1x 2 ⋅ ⋅ ⋅ x k , where x i ∈ S ∪ S−1 for i = 1, K, k. We prove the

Recall that the length result by the principle of mathematical induction on the length of words in
of a word is the W (S). Let w denote the length of w. If w = 0, w is the empty word, which
number of symbols in
it. is already reduced, and there is nothing to prove.
So, assume that the proposition holds true for all words in W (S) of length less
than k, for some k ∈ N.
Now, let w = x1x 2 K x k , x i ∈ S ∪ S−1, i = 1, K, k , and
w → w 1′ → ⋅ ⋅ ⋅ → w ′n and w → w 1′′ → ⋅ ⋅ ⋅ → w ′m′ be two reductions of w, where
w ′n and w ′m′ are reduced words.
If w 1′ = w1′′ , then as w1′ < w , it follows by induction that w ′n = w ′m′ .
If w 1′ ≠ w ′1′ , then by Lemma 1, there exists w 0 ∈ W (S), and elementary
reductions w 1′ → w 0 and w 1′′ → w 0 .
Consider a reduction process for w 0 , namely, w 0 → w 1 → ⋅ ⋅ ⋅ → w s .
This yields the following two reductions of w 1′ :
w 1′ → w 0 → w1 → ⋅ ⋅ ⋅ → w s and w 1′ → w ′2 → ⋅ ⋅ ⋅ → w ′n .
As w1′ < w , we can apply induction to see that any two reduced forms of the
word w 1′ are the same. Hence w ′n = w s .
Similarly, you can see that w ′m′ = w s .
Therefore, w ′n = w ′m′ . This proves the proposition.
60
From the proposition above, you can see that each equivalence class of ∼ in Group Presentations
W (S) has a unique reduced word. So each equivalence class can be
represented by this word. Let's denote by F(S) the set of all reduced words
in W (S) , which is the same as W(S) ~ , the set of equivalence classes of ~
in W (S) . For a word w ∈ W (S) , denote by [w ] the reduced word in the
equivalence class containing w. Then we have the following theorem, in the
context above.

Theorem 1: F(S) contains S, and is a group with respect to the binary

operation, ‘multiplication’, defined by [u ][ v] = [uv] for [u ],[ v] ∈ F(S).

Proof: Firstly, for x ∈ S , the reduced form of x is x itself, and so [x ] = x.

Therefore, F(S) contain S.
Next, note that the binary operation is well-defined because if u ~ u1 and
v ~ v1 , then uv ~ u 1v1 .
Thirdly, note that this operation is associative. To see this we need to prove
that [[uv]w ] = [u[ vw ]] for given u, v, w in W (S). Observe that both the
reduced words, [[uv]w ] and [u[ vw ]], can be obtained from the word uvw by
a sequence of elementary reductions. Hence, by Proposition 1,
[[uv]w ] = [uvw ] = [u[ vw ]].
Fourthly, you can check that the class of the empty word is the identity in
F (S) .
Finally, to see that the inverse of each element exists, suppose [w ] ∈ F(S). We
can assume that w = x1x 2 ⋅ ⋅ ⋅ x k is reduced, where x i ∈ S ∪ S−1. Then the word
w ′ = x −k1x k−1−1 K x1−1 is reduced, and the reduced form of ww ′ is the empty word.
Hence [w ′] is the inverse of [w ].
Thus, F(S) satisfies all the axioms of a group with respect to the given binary
operation.

Here’s a remark regarding the elements of F(S).

Remark 2: Any element of F(S) is of the form [w ], where w is a reduced

word over S. For convenience, we shall often denote this element of F(S) as
w , rather than [w ].

Now, F(S) is not just a group, it is actually a free group on S, as we shall now
prove.

Theorem 2: F(S) is a free group on S, that is, it satisfies the universal

mapping property.

Proof: From Theorem 1, you know that i : S → F(S) is the inclusion map.
Next, let G be a group and α : S → G be a map. For w = x1ε1 x ε22 K x εkk ∈ F(S),
where x i ∈ S and εi = ±1 , define α ~ : F (S) → G by setting
~ ( w ) = α( x ) ε1 α( x )ε2 K α( x ) εk .
α 1 2 k
Observe that, for w 1 , w 2 ∈ F(S), α ~ (w w ) = α ~ (w ) α ~ ( w ).
1 2 1 2

Also note that for a ∈ S ∪ S−1 , α (a a −1 ) = α (a ) α (a ) −1.

61
 Special Groups and Thus, words in the same equivalence class of W (S) are mapped to the same
Semigroups element of G, so that α ~ is a well-defined group homomorphism.
~ oi = α .
Further, α
Thus, (F (S), i) is a free group on S.

What Theorem 2 tells us is that given any non-empty set S, we can construct a
free group on S. Are all these different? Think about it while doing the
following exercises.

E2) Find the reduced form, and the inverse of the reduced form, of the
following words from {a , b, c} :
i) a 2 b −1b3a 3c −1c 4b −2 , ii) a 2a −3b 3a 4c 4a −1 .

The free group on a set is E3) If (F1 , i1 ) and (F2 , i 2 ) are two free groups on S, show that F1 ~ F2 .
unique up to isomorphism.
E4) Show that the following properties hold for F(S) :
i) If S = {a}, then F(S) is the infinite cyclic group generated by a.
ii) F(S) is non-abelian, if S > 1.
iii) Every element of F(S), except the empty word e, has infinite
order.

While doing the exercises above, did you realise the following important point
that emerges from them?

Remark 3: The properties of F(S) mentioned in E4 also hold true for any free
group on S, as any such group is isomorphic to F(S) (by E3). So, in particular,
Z n is not free, for n > 1.

Let us now look at an example of a free group.

Example 1: Show that (Z, +) is a free group on {1}.

Solution: Consider the group (Z, +) , and the set {1}. Take i to be the natural
embedding of {1} in Z . Now, consider any group G with a
map j : {1} → G : j(1) = g. Then the mapping α : Z → G : n a g n is a group
homomorphism, which satisfies α o i = j. So Z is free on {1}. In fact, as you
will see later, (Z, + ) is the only abelian group which is a free group.
***

Before, we consider some more free groups, it is important that you understand
some of their essential properties.

Theorem 3: If (F, i) is a free group on a set S , then the following hold:

i) i must necessarily be one-one;
ii) (F, i′) is free on S′, where S′ = Image i and i′ : S′ → F is the inclusion
map;
62 iii) S generates F.
Proof: Group Presentations

i) Suppose i : S → F is not one-one. Let x , y ∈ S, x ≠ y , be such that

i( x ) = i( y) . Consider any non-trivial group G. Choose a , b in G, a ≠ b,
and consider the mapping α : S → G which maps x to a and all other
elements of S to b . By the universal mapping property, there is a
homomorphism α ~ : F → G such that α ~ (i(x )) = α( x ) = a and
~ o i = α . So α
~ (i( y)) = α( y) = b. We reach a contradiction as i( x ) = i( y) and a ≠ b .
α
Hence, i must be one-one.

ii) Since F is free on S , and i : S → S′ i′ F , the universal mapping

property will hold for (F, i′) also.

iii) In view of (i) and (ii), we can assume, without loss of generality, that S is F
a subset of F. Consider the subgroup S of F generated by S. From i Id
α
Sec.5.3.1, Unit 5, you know that this is the intersection of all subgroups
of F containing S. i1 i2
Now consider the inclusions i : S → F, i1 : S → S and i 2 : S → F. So, S S F

i 2 o i1 = i . i
The unique extension of i is the identity map F → F (see Fig. 3). Fig. 3
Also, there is a unique α : F → S such that α o i = i1.
Then Id o i = i and (i 2 o α) o i = i 2 o (α o i) = i.
By the uniqueness of the extension, we get i 2 o α is the identity map.
Thus, S generates F.

In view of the properties (i) and (ii) of Theorem 3, we'll always assume that S
is a subset of F and i is the inclusion map. Accordingly, we shall just say
that F, rather than (F, i), is a free group on S.
The statement α ~ o i = α can then be read as ‘ α
~ is an extension of α ’.

You have seen that given a set you can construct a free group on it. So, you
have infinitely many examples of free groups. You may wonder if there are any
groups, other than Z n (n > 1), that are not free! Let us now consider a generic
example of a group which is not free.

Example 2: Show that a finite group is not free on any set.

Solution: Let F be a finite group. Suppose F is free on a subset
S = {s1 , s 2 , K , s n }.
Consider α : S → Z : α(s r ) = r.
Then, by the universal mapping property, there will be a unique group
homomorphism α ~ :F→ Z:α ~ (s ) = r.
r
Note, that α ~ (s s ) = α~ (s ) + α~ (s ) = m + k for m, k = 1, K , n.
m k m k
t
Now, s m ∈ F, so that s m = e, where o(F) = t and m = 1, K, n.
~ (s t ) = α
So, α ~ (e) = 0, that is, tα(s ) = 0 , that is, tm = 0, which is not possible
m m
since t ≠ 0, m ≠ 0.
We reach a contradiction. Hence F is not free.
***
63
Special Groups and Now comes the real strength of a free group, a result that makes free groups so
Semigroups central to group theory.

Theorem 4: Every group is isomorphic to the quotient group of a free group,

that is, given a group G, there is a free group F such that G ~ F for some
N
N F.

Proof: Let G be a group. For each g ∈ G, assign a variable wg , and let

S = {wg g ∈ G}. Define a mapping j : S → G by setting wg a g . By the
universal mapping property, there is a unique group homomorphism
φ : F (S) → G extending j. So, for each g ∈ G, there is a wg ∈ F(S) such that
φ( w g ) = g. So φ is surjective.

∴ F(S) ~ G. This proves the result.

Ker φ

Try the following exercises now.

E5) How many homomorphisms are there from F(S) to Z4 , where

S = {a , b} ?

E6) Let G be an abelian group. Is G ~ F(G ) ? Give reasons for your answer.

Taking the thought in Theorem 4 further, we look at the structure of different

groups whose elements satisfy certain relations.

6.3 GENERATORS AND RELATIONS

In the previous unit, you studied about generating sets. In earlier units you have
also seen how the generators of D 2n and Q 8 satisfy certain properties. We
shall now look at such a situation more generally.

Let G be a group generated by a set X, that is, the elements of X are the
generators of G. By the universal mapping property of free groups, there
exists a surjective homomorphism θ : F(X) → G. Hence, by the Fundamental
Theorem of Homomorphism, G ~ F(X ) . The elements of Ker θ are
Ker θ
called the relations among generators of G. So, the relations are equivalence
classes of those words w from X for which θ (w ) = 1 in G. Of course, if
Ker θ = {e}, then F(X) ~ G, and G will be free on X.

In this setting let us define ‘relations’, and related terms, precisely.

Definitions: Let G = X and θ : F(X) → G be a surjective homomorphism.

1) A set R is called a set of defining relations for G relative to a set X if
R ⊆ Ker θ , and Ker θ is the smallest normal subgroup containing R.
2) The pair X R is called a presentation of G.
64
3) The presentation X R is said to be finite if both the sets, X and R , Group Presentations

are finite.
4) A group is finitely presented if it has at least one finite presentation.

A comment about the notation, before we look at some examples.

Remark 4: If we write G = X R , we mean that G is generated by the

elements of X, with defining relations being all the elements of R. If X and
R are finite, say X = {x1 , K , x m }, R = {r1 , r2 , K , rn }, then we also write
X R as x1, x 2 , K, x m r1 , r2 , K, rn , that is, without the curly brackets.

Group presentations provide a convenient method to describe groups. The

definition of group presentation may seem complicated to you at the moment.
But it really isn't. To help you understand it, let us look at some examples.

Example 3: Show that a , b a 2, b 4, (ab )2 is a presentation of the dihedral

group D8 .
Solution: Recall from Unit 1 that D8 , the group of symmetries of a square, is a
group with 8 elements generated by x and y, where x is the reflection in the
vertical axis and y is the counter-clockwise rotation of the square by π / 2 (see
Fig. 4). So o(x ) = 2 and o( y) = 4.

Fig. 4: x and y generate D8 . Under x, the square is reflected in the y-axis. Under y, the
square rotates about O through π/2 in the counter-clockwise direction.

All the elements of D8 are {e, x , y, y 2 , y 3 , xy, xy 2 , xy 3 }. You also know that
xy = y −1x = y 3 x, i.e., ( xy) 2 = e.
Let F be the free group on X = {a , b}, and let N be the smallest normal
subgroup of F containing R = { a 2 , b 4 , (ab)2 }. We will show that F N is
isomorphic to D8 .
Consider the map θ : X → D8 : θ(a ) = x and θ (b) = y. Then, by the universal
~
mapping property, θ extends to a unique homomorphism θ : F → D 8 . Notice
~ ~
that θ is surjective as D8 is generated by x and y . Then (F Ker θ) ~ D8 . As
~ ~
each of a 2 , b 4 , (ab) 2 map to identity under θ , we have N ≤ Ker θ . So F N has
~ ~
at least 8 elements, as F Ker θ is isomorphic to (F / N) (Ker θ / N) .
On the other hand, you can use the following identities:
a2 N = N, b 4 N = N, abN = b −1aN,
65
Special Groups and Then, it follows that each element of F N is of the type a i b j N , where
Semigroups
i = 0, 1, j = 0, 1, 2, 3. Thus, F N has at most 8 elements.
Hence, F N has exactly 8 elements.
~
Consequently, Ker θ = N, and F N is isomorphic to D8 , i.e.,
a , b a 2 , b 4 , (ab) 2 is a presentation of D8 .

***

Example 4: Find a presentation of the quaternion group, Q8 .

Solution: Recall that Q8 = {1,−1, i,−i, j,− j, k,−k}, with multiplication given
by:
(−1) 2 = 1, − 1 = i 2 = j2 = k 2 , ij = k, jk = i, ki = j, ji = −k, kj = −i, ik = − j.
We'll show that a , b a 4 , b 2 a −2 , (ab )4 is a presentation of Q8 .
So, let F be the free group on {a , b}, and let N be the smallest normal
{ }
subgroup containing a 4 , b 2a − 2 , (ab ) . You can check that
4

N, aN, a 2 N, a 3 N, bN , abN, a 2 bN, a 3bN all belong to F N , and every other

element of F N is one of these. All these may or may not be distinct. So, F N
has at most eight elements.
By the universal mapping property, there exists a homomorphism θ : F → Q 8 ,
defined by θ (a ) = i and θ(b) = j . As i and j generate Q8 , θ is an
epimorphism. So, (F Ker θ) ~ Q8 . The relations i 4 = 1, j−2i 2 = 1, (ij) 4 = 1 in the
group Q8 imply that a 4 , b 2a −2 , (ab) 4 belong to Ker θ . Hence N ≤ Ker θ . Since
F ≤ F N , F N has at least 8 elements.
Ker θ
Consequently, F N has exactly eight elements, and N = Ker θ , which
proves the desired result.
***

Some important points that you may have noted from Examples 3 and 4
are given in the following remarks:

Remark 5: Two groups of the same order, or of the same order and
generated by the same number of elements, need not be isomorphic. Both
Q8 and D8 are generated by two elements, one of order 4 and the other of
order 2. But these groups are not isomorphic because all their properties
pertaining to their algebraic structures are not the same. For instance, D8
has only two elements of order 4, while Q8 has three elements of order 4.

Remark 6: A sufficient condition for X R to be a presentation of a

finite group G is that:
i) X must generate G;

ii) if H is a group that is generated by X satisfying the relations in R ,

then H ≤ G .
66
Try some exercises now. Group Presentations

E7) Show that a an is a presentation of the cyclic group Zn of order

n, n ≥ 2.

E8) Give a presentation of a free group.

E9) Write down a presentation of S3 and of Z 2 .

E10) Is every finite group finitely presented? Why, or why not?

The next example will help you see that different presentations may give
isomorphic groups. In other words, a group need not possess a unique
presentation.

Example 5: Show that Z 3 has two distinct presentations.

Solution: From E7, you know that Z3 ~ a a 3 .

We will show that a , b a 3 , b9 , a −1bab is also isomorphic to Z 3 . For this,
let F be the free group on {a , b}, and let N be the smallest normal
subgroup containing a 3 , b 9 , a −1bab . Note that
a −1bab ∈ N ⇒ a −1babN = N ⇒ bN = a −1b −1aN.
Also, since a 3 ∈ N, a −3 ∈ N. So,
bN = a −3ba 3 N = a −2 ba 2 N = a −1baN = b −1N.
Hence b 2 ∈ N. Also, b 9 ∈ N. Hence b ∈ N.
Consequently, each element of F N is one of N, aN, a 2 N. Thus, F N has
at most three elements. By considering the homomorphism θ : F → Z3
such that θ (a ) is a generator of Z3 and θ (b) = 1, it follows, as in
previous examples, that F N has at least three elements.
Hence F N = 3, and F N ~ Z3 .
***

Here are some more exercises for you now.

E11) Give a presentation of Z4 involving:

i) one generator, ii) two generators, iii) three generators.

E12) Mark each of the following true or false. Give reasons for your choice.
i) Every group has a presentation.
ii) A group can have many different presentations.
iii) Every group with a finite presentation is of finite order.
iv) Two presentations with the same number of generators give
isomorphic groups.
67
Special Groups and Let us now see how group presentations are useful for studying the structure of
Semigroups various groups.

6.4 CLASSIFYING GROUPS OF SMALL ORDER

In this section we will apply what you have just studied to take further the
classification exercise you undertook in Unit 3. Over there we had considered
the possible structures of groups of order n, n = 1, K, 10, n ≠ 8. Here we shall
look at groups of order 8 and 12, in particular.

Example 6: Determine all groups of order 8 up to isomorphism.

Solution: From Unit 5, you know the three abelian groups of order 8, namely,
Z8 , Z 2 × Z 4 , Z 2 × Z 2 × Z 2 .
Using generators and defining relations, we shall give presentations of the
non-abelian groups. So, let G be a non-abelian group of order 8. Since G is
non-abelian, it has no element of order 8. So each non-identity element of G is
of order either 2 or 4.
We first show that G has an element of order 4. Suppose not, that is, suppose
a 2 = e ∀ a ∈ G. Then for a , b ∈ G , we have (ab) 2 = e. So,
ba = a 2 bab 2 = a (ab) 2 b = ab , contrary to our assumption that G is not abelian.
Thus, G has an element of order 4, say x.
If y ∈ G s.t. y ∈/ x , the cosets x and y x exhaust all of G . Hence x and
y are generators for G . Also, since G : x = 2, we have y 2 ∈ x . If y 2 = x
or y 2 = x 3, then y would be of order 8, which is not so. Hence, y 2 = e or
y2 = x 2 .
Next, since | G :< x > | = 2 , x is normal in G . So, yxy −1 ∈ x . The order of
yxy −1 being 4, we have yxy −1 = x or yxy −1 = x 3 . If yxy −1 were equal to x ,
then yx would be equal to xy , which would make G abelian. Hence,
yxy −1 ≠ x.
Hence yxy −1 = x 3 . Remember, we also have x 4 = e, and y 2 = e or y 2 = x 2 .
You can now show, using computations as in previous examples, that:
if y 2 = e , then G ~ a , b a 4 , b 2 , (ab )2 , that is, G ~ D8 ;

if y 2 = x 2 , then G ~ a , b a 4 , b 2 a −2 , (ab )4 , that is, G ~ Q 8 .

Hence, if G = 8, then G is one of the following groups:

i) Z 8 , ii) Z 2 × Z 4 , iii) Z 2 × Z 2 × Z 2 , iv) D 8 , v) Q 8 .

***

Now let us consider groups of order 12. We had only stated the structure in
Theorem 9 of Unit 3. Let us state it again, and prove it now.

Theorem 5: There are five isomorphism classes of groups of order 12. These
are represented by:
i) Z 4Z × Z 3Z ;

68 ii) Z 2Z × Z 2Z × Z 3Z ;
iii) A4 ; Group Presentations

iv) D12 ;
v) the group generated by x , y such that x 4 = e = y3 , xy = y 2 x.

Proof: Let G be a group of order 12. If G is abelian, then from Unit 5, you
Z Z Z
know that G ~− Z 4Z × Z 3Z or G ~ − 2Z × 2Z × 3Z .
These are the cases (i) and (ii) in the statement of this theorem.

Now suppose G is non-abelian. Let T be a Sylow 2-subgroup and Q be a

Sylow 3-subgroup of G.
Q is of order 3, and hence cyclic, say Q = s .
As T is of order 4, it could be either cyclic or the Klein-4 group. In either
case, T ∩ Q is trivial, since T and Q are coprime.
Also, the number of Sylow 3-subgroups is 1(mod 3), and divides 4. Hence, it
must be 1 or 4.

We look at two possibilities now: Q G, Q G.

Case 1 ( Q G) : Since G = TQ , G = TQ. Also observe that Q is generated
by s and by s 2 . So Q has a single non-trivial automorphism
σ : Q → Q : σ(s) = s 2 . Note that σ 2 = I.
Recall that T is either cyclic or it is the Klein-4 group.

First suppose that T is cyclic, say T = t , where t 4 = e. Consider the

conjugation action of t on Q, that is, t ⋅ s = tst −1. Now, tst −1 can be s or s 2 .
But if tst −1 = s, then G will be abelian, a contradiction. So t ⋅ s = tst −1 = s 2 .
Then t 2 acts as identity, and t 3 acts like t.
So, we can describe G as generated by two generators s and t , subject to the
relations s 3 = t 4 = e , and tst −1 = s 2 . This is (v) of the statement of this
theorem.

Now suppose that T is the Klein-4 group. It is generated by two elements t1

2 2
and t 2 subject to the relations t 1 = t 2 = e and t1t 2 = t 2 t1 . At least one of the
elements of T must act non-trivially on Q, as discussed in the case when T
is cyclic, since otherwise G will be abelian. Since the product of any two
non-trivial elements of T is the third non-trivial element, it follows that two
of the three non-trivial elements of T act non-trivially on Q and the third
acts trivially. (No matter which two of the three we choose to act non-trivially,
we end up getting the same group up to isomorphism.) Thus the group G can
be described as follows: it is generated by s, t1 and t 2 subject to the relations
2 2 −1 −1
s 3 = t1 = t 2 = e, t1t 2 = t 2 t 1 , and t1st 1 = s 2 , t 2st 2 = s . Now, put x = t 2s .
Then o(x ) = 6, o( t1 ) = 2 and t1xt 1−1 = t 2s 2 = s 2 t 2 = x −1 , which defines the
group D12 [(iv) of the statement of this theorem].

Case 2 ( Q G ): Here Q is not unique, and by Sylow’s third theorem, there

are exactly four Sylow 3-subgroups, say Q1 , Q 2 , Q 3 and Q 4 . Each of these
69
Special Groups and being simple, they intersect trivially with one another. So their union consists
Semigroups of 9 elements (the identity and 8 other elements, each of order 3). Now any
Sylow 2-subgroup intersects this union trivially (because any such group
interests any Q i trivially). This implies that a Sylow 2-subgroup consists of
the identity and all the three elements in the complement of the union of the
Q i s . It is, thus, unique, and, in particular, normal. So T will be normal.
Write Q = {1, s, s 2 } and consider the conjugation action of s on T . If this is
trivial, that is, st = ts for all t in T, then G will be abelian, which is a
contradiction. So s defines a non-trivial automorphism of the group T of
order 3.
Note that Z 4Z has no such automorphism – its only non-trivial
automorphism sends a generator to the other generator and is of order 2. We
conclude, therefore, that T is the Klein-4 group.
It is generated by t 1 and t 2 , subject to the relations t 12 = t 22 = e and
t 1t 2 = t 2 t 1.
The map ϕ : T → T : ϕ(t 1 ) = t 2 and ϕ(t 2 ) = t 1t 2 gives an automorphism of T of
order 3.
Suppose that the conjugation action of s on T equals this automorphism. (The
only other option is that s acts as the inverse of this automorphism, but the
group that we get in that case will be isomorphic to what we obtain now.) So,
G is generated by s, t1 and t 2 subject to the relations s 3 = t12 = t 22 = e,
t 1 t 2 = t 2 t 1 , st 1s −1 = t 2 , and st 2s −1 = t 1t 2 . In this case G ~ A 4 [(iii) of this
theorem’s statement].

Thus, any group of order 12 must be isomorphic to one of the 5 groups given
in the statement of the theorem.

From Theorem 5, you may have realised how we need to go step-by-step, case
by case, to analyse the structure of a group. Try some exercises now.

E13) Determine which one of the five classes in Theorem 5, (Z 2Z) × S3

belongs to.

E14) Let G be a group of order 30. Let S, T and U be, respectively, a Sylow
2-, a Sylow 3- and a Sylow 5-subgroup.
i) Show that either T or U is normal in G.
ii) Show that TU = {tu t ∈ T, u ∈ U} is a subgroup of order 15. Note
that, as TU has index 2 in G, this subgroup is normal in G.
iii) Show that TU is cyclic.
iv) Let S = {1, s}. Consider the conjugation action of s on TU.
Letting r be a generator of TU, show that srs −1 is one of four
possibilities: r, r 4 , r11 (= r − 4 ) or r14 (= r −1 ).
v) Show that there are four possible isomorphism classes of G,
corresponding to the four possible values of srs −1 (in (iv)):
• G is abelian in case srs −1 = r.
• ~ D10 × Z 3Z in case srs −1 = r 4 .
G−
70
 • ~ S5 × Z 5Z in case srs −1 = r11.
G− Group Presentations

• G− ~ D 30 in case srs −1 = r14 .

vi) Show that these cases are distinct.
[Hint: Find Z(G ) in each case, and look at their orders.]

E15) Give a presentation of all possible groups of order 10.

Now, from Unit 2, you know that a group of order p 2 is abelian, where p is a
prime. What about groups of order 2p 2 , for an odd prime p ? We give the
result in this case, without proof.

Theorem 6: Let G be a group of order 2p 2 , for an odd prime p. Then there

are 5 isomorphism classes of G :
i) G is cyclic;

ii) G ~ Z 2Z × Z pZ × Z pZ ;
iii) G is the dihedral group D 2 p2 ;

iv) ~ Z pZ × D 2 p ;
G−

v) G = s, r1 , r2 s 2 , r1p , r2p ,r1r2 r1−1r2−1 , sr1s −1r1 , sr2s −1r2 .

Theorem 6 tells us, for example, that there are 3 non-abelian groups of order
50, upto isomorphism.

Why don’t you try an exercise now?

E16) What are the possible presentations of groups of order 242?

With this we come to the end of our discussion on group presentations. We

now summarise what you have studied in this unit.

6.5 SUMMARY
In this unit, you have studied the following points.

1) A group F is a free group on a set S if ∃ i : S → F s.t. whenever there is

a group G and a map α : S → G , there is a unique group homomorphism
~ : F → G that extends α. Here S generates F.
α

2) Given any set S, a method for constructing a free group F(S) on it.

3) A finite group is not free on any set.

4) Every group is isomorphic to the quotient group of a free group.

71
Special Groups and 5) G has a presentation X R if G is generated by the elements of X,
Semigroups
with defining relations being the elements of R.

6) There are 5 groups of order 8, up to isomorphism.

7) There are 5 groups of order 12, up to isomorphism.

8) There are 4 groups of order 30, up to isomorphism.

9) There are 5 groups of order 2p 2 , up to isomorphism, where p is an odd

prime.

6.6 SOLUTIONS / ANSWERS

E1) For u ∈ W (S), u ~ u, trivially. So ~ is reflexive.
Next, let u, v ∈ W (S) such that u ~ v. Suppose v is obtained from u by
deleting x 1x1−1 ,K , x k x −k1 and adding y1y1−1 , K , y r y r−1 for x i , y j ∈ S ∪ S−1.
Then u is obtained from v by adding x i x i−1 , i = 1, K , k , and deleting
y i y i−1 , i = 1,K, r, in the same places they were deleted/added from.
Thus, v ~ u. So, ~ is symmetric.
Finally, if u ~ v and v ~ w , u, v, w ∈ W (S), then u ~ w by combining
both sets of additions and deletions. Hence, ~ is transitive.

E2) i) The reduced form is a 2 b 2 a 3c 3b −2 , and its inverse is b 2 c −3a −3 b −2 a −2 .

ii) a −1b 3a 4c 4a −1 and ac −4a −4 b −3a , respectively.

E3) You should check that this follows from the universal mapping property.

E4) i) If S = {a}, then any reduced word is just an integral power of a.

Looking at the multiplication in F(S), you can see that this group is
the cyclic group generated by a. Further, [a ],[a 2 ],L are all
distinct. Hence F(S) is infinite.

ii) Consider x , y ∈ S. Then the word x −1y −1xy is reduced and is

different from the empty word. Hence x −1y −1xy is not identity, i.e.,
the words x and y do not commute.

iii) Let w be a non-empty reduced word. Consider all reduced

subwords t of w such that w = tmt −1 , where m is a reduced
word. Let u be one such subword whose length is maximal among
all such subwords t. Then w = uvu −1 for some reduced word v ( u
could be e also!).
Since w is reduced, v is non-empty, and by maximality of u ,
there is no cancellation in the product vv, i.e., the reduced form of
vv is vv. So, for any n ≥ 1, w n = u v n u −1 is a non-empty reduced
72 word. Hence w can’t be of order n.
E5) By the universal mapping property of free groups, the number of Group Presentations
homomorphisms from F(S) to Z 4 equals the number of distinct maps
from {a , b} to Z 4 , and this number is 2 4 = 16.

E6) If G = {e}, then F(G ) = {e} = G.

Let G > 1. Then F(G ) will be non-abelian, as you have shown in E4.
Hence F(G ) ~/ G.

E7) Let F = F (S) , where S = {a} . By E4(i), F is just the cyclic group a .
Now the smallest normal subgroup of F containing a n is a n . You
should now check that F N , i.e., a a n is isomorphic to Z n .

E8) Let F be a free group generated by a set X. Since F is free, F ~

− F(X).
Hence, none of its generators satisfy any relations. So F = X « is a
presentation of F.

E9) We will show that S3 ~

− a , b a 3 , b 2 , b −1aba . First of all recall that S3
is generated by α = (1, 2, 3) and β = (1, 2) . Moreover,
α 3 = 1, β 2 = 1, β −1αβ = α −1. …(1)
Let S = {a , b} and F = F (S). Then there is a homomorphism θ : F → S3
such that a → α and b → β. θ is onto as S3 is generated by α and β.
In view of Eqn 1, the normal subgroup N of F generated by
a 3 , b 2 , b −1aba is contained in Ker θ. This gives a surjective
homomorphism θ from F N to S3 such that aN a α and bN a β. In
particular, it tells us that F N has at least 6 elements.
However, each element of F N is one of N, aN, a 2 N, bN , abN , a 2 bN ,
as a 3 , b 2 , b −1aba lie in N. So, F N has at most 6 elements.
Consequently, F N has precisely 6 elements and θ is an isomorphism.

You know Z2 is abelian, and generated by (1, 0) and (0 ,1), with

αβ = βα ∀ α , β ∈ Z 2 . Let S = {a , b} and F = F(S). Then ∃ a
homomorphism θ : F → Z 2 : θ(a ) = (1, 0), θ(b) = (0 ,1). As above, θ is
onto. Consider the smallest normal subgroup N of F(S) containing
{aba −1b −1}. Then N ⊆ Ker θ. Take
θ : F N → Z 2 : θ (a ) = (1, 0), θ( b ) = (0 ,1). Then, for any
(n , m) ∈ Z 2 , θ (a n b m ) = (n , m). Hence θ is onto.
Now, let θ (x ) = (0 , 0), where x ∈ F. Since a b = b a in F N, x = a n b m
for some n , m ∈ N.
So θ( x ) = (0 , 0) ⇒ (n , m) = (0 , 0) ⇒ x = e.
Thus, θ is also 1-1, and hence θ is an isomorphism. So
Z 2 ~ a , b aba −1 b −1 .

73
Special Groups and E10) Let G = {g1 ,K, g n} be a finite group. Take X = G. Let
Semigroups
R = {g i g jg −k1 i, j = 1, K , n, where g i g j = g k in G}.
Then θ : F(X ) → G , extending I : G → G, is s.t. R ⊆ Ker θ.
So, the smallest normal subgroup N containing R is in Ker θ.
So there is a surjection θ : F(X ) → G : g i N a g i
N
∴ F(X) ≥ G = n.
N
Also F(X) = { g i N i = 1, K , n}.
N
So F(X ) ≤ n.
N
Hence F(X ) = n, and θ is an isomorphism.
N
Thus, G = X R is a presentation of G.

E11) a a 4 , a , b a 4 , b 2 , b −1 and a , b, c a 8 , a 12 , b, c , respectively.

Explicitly, in terms of elements of Z 4 , you can see these as
1 , 1 , 0 , 3 , 0 , 0 , respectively.

E12) i) True, as has been described in Sec.6.3.

ii) True. For example, you have seen it in E11.

iii) False. For example, a e is a finite presentation of the infinite

cyclic group Z.

iv) False. For example, a a 4 and a a 5 are presentations with

one generator but they do not give isomorphic groups; the former is
a presentation of Z 4 and the latter is that of Z5 .

E13) Z × S = 12. From E17 of Unit 3, you know that it has 3 Sylow
2Z 3
2-subgroups, each isomorphic to the Klein 4-group. It has a unique
Sylow 3-subgroup. So it is the case (iv) of Theorem 5.
Thus Z × S3 ~ D12 .
2Z

E14) i) Suppose neither T nor U is normal in G. Then, by Sylow’s third

theorem, there are 10 Sylow 3-subgroups and 6 Sylow 5-
subgroups. The intersection of any two of these subgroups is the
trivial subgroup. The union of all the Sylow 3-subgroups has
cardinality 21 (each of the groups contains, in addition to the
identity, two elements, neither of which is contained in any other
subgroup). By a similar reasoning, the union of all Sylow 5-
subgroups is 25. The only thing that is common to these two unions
is the identity element. Therefore, the union of the Sylow 3- and
Sylow 5-subgroups has cardinality 45. This is not possible because
74
 G has order only 30. Thus, we reach a contradiction. So at least Group Presentations
one of T or U is normal in G.

ii) Since at least one of T and U is normal, and since T ∩ U is

trivial, the result follows from Proposition 2, Unit 3.

iii) See Example 13, Unit 3.

iv) Suppose that srs −1 = r a .

2
Then (srs −1 ) a = (r a ) a = r a .
Also sr a s −1 = s (srs −1 ) s −1 = s 2 rs −2 = r (since s 2 = e ).
2
∴ r a = r , that is, a 2 ≡ 1(mod 15).
You should check that there are four solutions modulo 15 to this,
namely, 1, 4, 11 , and 14.

v) • In case a = 1 , then sr = rs , so G is abelian.

• In case a = 4 , sr 3s −1 = r12 = r −3 , and sr 5s −1 = r 5 . The elements
s and r 3 together generate a normal subgroup isomorphic to
the dihedral group D10 . This subgroup intersects trivially the
subgroup {1, r 5 , r10 } which is central. By Proposition 2 of Unit
3, we conclude that G is isomorphic to the direct product
D10 × Z 3Z.
• The analysis in case a = 11 is similar to that in the case of
a = 4. The elements s and r 5 together generate a normal
subgroup isomorphic to the symmetric group S3. This
subgroup trivially intersects the subgroup {1, r 3 , r 6 , r 9 , r12 },
which is central. We conclude that G − ~ S3 × Z 5Z.

• In case a = 14 , G is generated by r and s, subject to the

relations s 2 = r15 = e and srs −1 = r −1 . Thus G is the dihedral
group D 30 .

vi) In case a = 1, G = Z(G ).

( )
In case a = 4, Z(G ) ~ Z(D10 ) × Z Z
3Z
= {e} × Z .
3Z
In case a = 11, Z(G ) ~Z(S ) × Z(Z ) = {e} × Z .
5Z
3 5Z
In case a = 14, Z(G ) = Z(D 30 ) = {e} .
Thus, the orders of Z(G ) in these cases are 30, 3, 5, 1,
respectively. Hence these cases are all distinct.

E15) If G is of order 10, then by Theorem 8 of Unit 3, you know that

G~ − Z10 , or G ~
− D10 .
If G ~
− Z10 , then a a 10 is a presentation of G.
If G ~
− D10 , let G = {1, x , x 2 , x 3 , x 4 , y, xy, x 2 y, x 3 y, x 4 y}, where
x 5 = e = y 2 and yxy −1 = x 4 = x −1. We will show that
75
Special Groups and G~
− a , b a 5 , b 2 , bab −1a −1 .
Semigroups
For this, let F be the free group on {a , b}, and N be the smallest
normal subgroup of F containing a 5 , b 2 , bab −1a −1 . The surjective
homomorphism θ : F → G which maps a a x and b a y, carries N
to identity, because x 5 = e, y 2 = e and yxy −1x −1 = e. So F N has at
least 10 elements. But every element of F N is one of a i b j N, 0 ≤ i ≤ 4
and j = 0,1. Thus, F N has precisely 10 elements, and N = Ker θ.
Consequently F N ~ − G, the desired result.

E16) 242 = 2(11) 2 . Thus, by Theorem 6, we know there are 5 possible

structures for a group of order 242. Accordingly, their presentations are
i) a a 242 ,

ii) a , b, c aba −1b −1 , aca −1c −1 , bcb −1c −1 , a 2 , b11 , c11

iii) a , b a 121 , b 2 , bab −1a −120

iv) a , b, c a 11 , b11 , c 2 , cbc −1b −10

v) s, r1 , r2 s 2 , r111 , r211 , r1r2 r1−1r2−1 , sr1s −1r1 , sr2s −1r2 .

76
 Applications of
UNIT 7 APPLICATIONS OF SEMIGROUPS Semigroups

Structure Page No.

7.1 Introduction 77
Objectives
7.2 Semigroups − Some Basics 78
7.3 Free Semigroups 81
7.4 Connections with (Semi)automata 84
7.5 Application to Formal Languages 87
7.6 Summary 91
7.7 Solutions / Answers 92

7.1 INTRODUCTION
So far you have studied several aspects of groups. Now we look at simpler
algebraic structures, i.e., semigroups and monoids. In your undergraduate
studies, you would have come across these algebraic objects in passing.

The algebraic theory of semigroups came into its own during the 20th century.
For a historical overview you must look at
https://www.researchgate.net/publication/226480216_The_Early_Development
_of_the_Algebraic_Theory_of_Semigroups. In this unit you will find brief
historical remarks, as you go along.

To start with, in Sec.7.2, we recall the definition and some properties, of

semigroups. In the next section, Sec.7.3, you will study the semigroup
analogue of a free group.

The importance of semigroups also lies in the applications of its theory to

genetics, sociology, psychology, engineering, etc. To give you a feel of the
applications, in Sec.7.4 and Sec.7.5, we focus on the applications of
semigroups in two linked areas, namely, the study of automata and formal
languages.

If you are interested in studying more about the ideas discussed in this unit, you
can refer to
1) ‘Applied Abstract Algebra’, by Lidl and Pilz, UTM, Springer-Verlag;
2) ‘Algebra’, by PM Cohn, Wiley.

Objectives
After studying this unit, you should be able to:
• define, and give examples of, a semigroup and a monoid;
• explain what a finitely generated semigroup/monoid is;
• define, and give examples of, a free semigroup;
• prove that different bases of a free semigroup must have the same
cardinality;
• explain what a semiautomaton/automaton is, and its relationship with a
semigroup/monoid; 77
Special Groups and • explain what a formal language and a grammar is, and how semigroups
Semigroups and monoids are useful for studying them.

7.2 SEMIGROUPS – SOME BASICS

Let us begin with a quick review of what a semigroup is. We will also present
a few of its properties that we would be using in the later sections.

Definitions: 1) A semigroup is an ordered pair (S, ∗), where S is a non-empty

set and ∗ is an associative binary operation on S.

2) A monoid is a semigroup (S, ∗) with an identity element w.r.t. ∗ , i.e.,

∃ e ∈ S such that e ∗ x = x ∗ e = x ∀ x ∈ S.

If asked for examples of semigroups, the following would definitely come to

your mind:
(N, +), (N, ) (Z, + ), (Z, ) and (R, ) .
• • •

Further, (N, ) is a monoid, while (N, +) is not. However, (N ∪ {0}, +) is a

•

monoid, with identity 0.

Let us look, in some detail, at a few other examples.

Example 1: Let S ≠ «. Show that the set of all mappings from S to S,

Map(S, S), is a monoid w.r.t. the composition of mappings.
Solution: Firstly, Map(S, S) ≠ « since S ≠ «.
Next, if f , g ∈ Map(S, S), then f o g ∈ Map(S, S).
Thirdly, the composition of mappings is associative, in general.
Finally, the identity map, I : S → S : I(s) = s, is the identity w.r.t. o .
Therefore, (Map(S, S), o) is a monoid.
***

Example 2: Show that every non-empty set can be turned into a semigroup.
Solution: Let S ≠ «. Define ∗ : S × S → S : s1 ∗ s 2 = s1.
Then, you should check that (S, ∗) is a semigroup.
***

Here is a brief remark about notation.

Remark 1: We will sometimes denote the semigroup/monoid (S, ∗) by only

S, if the underlying operation is understood.

Try some related exercises now.

E1) Check whether or not (M n (R ), +), (R[ x ], ) and (Z, −) are semigroups.
•

E2) Let S be a non-empty set, and Re l (S) the set of all relations on S, i.e.,
subsets of S × S. Define
78
 Applications of
∗ : Re l (S) × Re l (S) → Re l (S) : (R1 , R 2 ) a R 1 ∗ R 2 , defined by Semigroups
‘ x (R1 ∗ R 2 ) y iff ∃ z ∈ S s.t. x R 1 z and z R 2 y ’,
i.e., ‘(x , y) ∈ R 1 ∗ R 2 iff ∃ z ∈ S s.t. ( x , z ) ∈ R1 and (z , y) ∈ R 2 ’.
Show that (Re l (S), ∗) is a semigroup.
[This is called the relation semigroup of S. ]

E3) If (X, ∗) is a semigroup, then show that (℘(X), ⊗) is a semigroup,

where ℘(X) is the power set of X and
A ⊗ B = {a ∗ b a ∈ A, b ∈ B} ∀A, B ∈ ℘(X).
[This is called the power semigroup of X.]

Now, you know that a semigroup (S, ∗) is a group if (S, ∗) is a monoid and
every element in S is invertible w.r.t. ∗ . Also, given a monoid, there is a very
natural group lying within it. Can you guess what it is?

Definition: Let (S, ∗) be a monoid. Define G S = {x ∈ S | x is invertible}.

(G S , ∗) is a group, called the unit group of S.

You can check that (G S , ∗) is a group, and hence the name ‘unit group’ is
appropriate. Let us consider some examples.

Example 3: Find the unit groups of (M n (R ), ), (Map(S, S), o) and (G, ∗),
•

where G is a group and S is a non-empty set.

Solution: The unit group of (M n (R), ) is {A ∈ M n (R) A is invertible}
•

= GL n (R ).
The unit group of (Map(S, S), o) is the group of bijective functions from S to
S. The unit group of (G , ∗) is the whole of G , since every element of G is
invertible.
***

Now, in the case of groups you studied subgroups and group homomorphisms.
We can define analogous objects for semigroups too.

Definition: Let (S, ∗) be a semigroup. A non-empty subset T, of S, is called

a subsemigroup of S if t1 ∗ t 2 ∈ T ∀ t1 , t 2 ∈ T.
We denote this fact by T ≤ S.

The next lot of definitions should not surprise you either.

Definitions: 1) Let (S1 , ∗1 ) and (S2 , ∗2 ) be two semigroups. A function

f : S1 → S2 is a semigroup homomorphism if
f (a ∗1 b) = f (a ) ∗2 f (b) ∀a , b ∈ S1.
2) A semigroup homomorphism is a monomorphism (respectively,
epimorphism) if it is 1-1 (respectively, onto).
3) If a semigroup homomorphism is both 1-1 and onto, we call it an
isomorphism of semigroups. 79
Special Groups and As an example, consider f : (Z, ) → (N ∪ {0}, ) : f (x ) = x . As you can check,
• •

Semigroups
f is an epimorphism, but not a monomorphism.

Here are some exercises now.

E4) Show that (N, ) ≤ (Z, ).

• •

E5) Find the unit groups of (N ∪ {0}, +), (Z, ), (℘(S), ∩) and (Map(S, S), o)
•

where S ≠ «.

E6) Check whether f : (Z, ) → (N ∪ {0}, +) : f ( x ) = 0 is a semigroup

•

homomorphism.

E7) Prove that (℘ ({1, 2, 3}), ∩) and (℘ ({a , b, c}), ∩) are isomorphic
semigroups, where a , b, c are distinct symbols.

Subsemigroups have several properties analogous to those of subgroups. Let us

consider some of them.

Theorem 1: A non-empty intersection of any number of subsemigroups of a

semigroup (S, ∗) is a subsemigroup of (S, ∗).

Proof: We leave the proof to you (see E8).

This theorem allows us to give the following definition, analogous to that in

Unit 5.

Definition: Let (S, ∗) be a semigroup, and let T be a non-empty subset of S.

Then the subsemigroup of S generated by T is the intersection of all the
subsemigroups of S containing T. It is denoted by < T > .

You can check that

i) < T > is the smallest subsemigroup of S containing T.
ii) < T > = {t1t 2 K t n t i ∈ T, n ∈ N}.

Can you think of some examples of generating sets? For instance, given any
semigroup (S, ∗), is S = < S > ? In fact, it is, since S is the smallest
subsemigroup of S containing every element of S!
So, every semigroup has a generating set, but the fewer the generators, the
easier it is for us to ‘see’ the elements of the semigroup. For instance,
(N, +) = < N > . But (N, +) = < 1 > also, since any element of N is a finite sum
1 + 1 + L + 1. In fact, (N, + ) is an example of a finitely generated semigroup,
as you will just see.

Definition: A semigroup (S, ∗) is called finitely generated if S = < T >,

where T is a finite subset of S. If T = 1, then (S, ∗) is called cyclic.

80 For example, (N, +) is cyclic.

Let us consider some more examples. Applications of
Semigroups

Example 4: Which of the following statements are true? Give reasons for you
answers.
i) (N ∪ {0}, +) is cyclic.
ii) (N, ) is not finitely generated.
•

Solution: i) This is false. If it were cyclic, then the only generator possible
would be 1, as N = < 1 >. However, since 0 ∉< 1 >,
(N ∪ {0}, +) = < {0, 1} >, and hence it is finitely generated but not cyclic.

ii) This is true. By the unique factorisation theorem, every natural number,
except 1, is a product of prime numbers. Also, the set of primes, P, is
infinite. So (N, ) = < P ∪ {1} > . Further, no finite subset of P ∪ {1} can
•

generate (N, ). Therefore, it is not finitely generated.

•

***

Here are some exercises now.

E8) Prove Theorem 1. (Note that an analogous statement is true for

monoids.)

E9) Give an example of a semigroup S and two subsemigroups S1 , S2 of S The union of

subsemigroups need
such that S1 ∪ S2 is not a subsemigroup of S. not be a semigroup.

E10) Show that every subsemigroup of a finite group G is a subgroup of G.

Is the same true for an infinite group? Give reasons for your answers.

E11) Under what conditions on a set S, will (℘(S), ∩) be finitely generated?

Let us now look at a particular kind of semigroup which has extensive

applications in computer science and other areas.

7.3 FREE SEMIGROUPS

In the previous unit, you studied about free groups. A free semigroup can be
defined along the same lines, as you will see. It is, in fact, this semigroup
which is the basic object in applications that you will study in the later sections
of this unit.

So, let us define it using the universal mapping property.

Definition: Let B be a non-empty set. A semigroup (F, ∗) is called a free

semigroup on B if
i) F ⊇ B; and
ii) any mapping f from B into a semigroup (S, ∗′) can be extended to a
unique semigroup homomorphism from F to S.
81
 Special Groups and This is diagrammatically shown in Fig. 1. In this situation, B is called a basis
Semigroups of F, and F is also called the word semigroup over B. (The reason for this
F
name would be clear to you from Unit 6.)
h
You may well ask if given B ≠ «, does there always exist a free semigroup on
U f B ? The following theorem tells us about this.
B S
Fig. 1: F is free on B if Theorem 2 (Existence): For any set B ≠ «, there exists a semigroup F which
the diagram is
commutative. is free on B.

Proof: The proof is along the same lines as for Theorem 1 of Unit 6. Let
F = {b1b 2 K b n b i ∈ B, n ∈ N}, the set of all formal products (or strings) of
elements of B. Here, we define
b1b 2 K b n = c1c 2 K c m iff n = m and bi = c i∀ i = 1, K , n.
If x ∈ F, then x = b1 b 2 K b n Further, for x , y ∈ F, if x = b1b 2 K b r and y = c1c 2 K c s , for some bi and c j in
for some b i ∈ B. The length B, we define x ∗ y = b1b 2 K b r c1c 2 K c s , i.e., the binary operation ∗ on F is
of x, denoted by x or l (x), defined to be the concatenation (or juxtaposition).
is n. Then, as you can see, (F, ∗) is a semigroup containing B.
Now, let f : B → S be any map, where S is a semigroup.
Define h : F → S : h (b1 K b r ) = f (b1 ) f (b 2 ) K f (b r ).
You can check that h is a homomorphism, and h extends f .

Suppose h′ is any other homomorphism from F to S that extends f . Then, for

any c1c 2 K c s ∈ F,
h ′(c1c 2 K c s ) = h ′(c1 ) h ′(c 2 ) K h ′(c s )
= f (c1 ) f (c 2 ) K f (c s )
= h (c1c 2 K c s ).
Therefore, h′ = h.
This shows that h is unique, and F is free on B.

Theorem 2 tells us that given a set, we can always define a free semigroup on
it. From the construction in Theorem 2, you also see that every element of the
free semigroup F is built up from elements of B. This is why B is called a
basis of F.

Let us consider an example.

Example 5: If B = {b}, then show that the free semigroup on B is

(N, +) is a free semigroup. FB = {b, b ∗ b = b 2, b 3, K}, which is isomorphic to (N, +).
Solution: Firstly, (FB , ∗) is a semigroup containing B.
For the second condition, for any map f : {b} → S, where S is a semigroup,
define h : FB → S by h (b n ) = [f (b)]n ∀ n ≥ 1.
Then h is a homomorphism.
Also, if h′ : FB → S is any other homomorphism that extends f , then
h′(b r ) = [h ′(b)]r = [f (b)]r = h (b r )∀ r ≥ 1, so that h′ = h. Thus, h is unique.
This shows that h satisfies (ii) of the definition.
Thirdly, define ψ : FB → N : ψ (b r ) = r.
82
Then, you can check that ψ is a semigroup isomorphism. Applications of
Semigroups
***
Try some exercises now.

E12) Are (N, ), (N ∪ {0}, +) and (R, +) free semigroups? Give reasons for
•

your answers.

E13) Define a submonoid and a free monoid on a set B, along the same lines
as the definitions related to semigroups.

The next question that arises is: can a free semigroup have more than one
basis? If so, are these bases related? In the case of groups you have seen that a
free group with a finite basis can have any number of distinct bases, but the
cardinality of all these bases must be the same. This is also true for
semigroups, as we now prove.

Theorem 3: Let F be free on B and on B′, where B is finite. Then B′ is

finite also, and B = B′ .

To prove this theorem, let us first prove a lemma.

Lemma 1: Let F and F′ be free semigroups on B and B′, respectively. Then

F−~ F′ ⇔ B = B′ .

Proof of lemma: First, let us assume F ~ F′. The situation here is as in Fig. 2,
where ψ is an isomorphism from F to F′, B its in F and B′ sits in F′.
ψ
F ~ F′
ψ B
is read as ‘ ψ
ψ restricted to B’. Here
B
ψ B ( b) = ψ ( b), for
U U
B B′ b ∈ B.

Fig. 2: ψ ~ B′
:B →
B

For b ∈ B, ψ (b) ∈ F′. Let ψ (b) = b′1 K b′n , b′i ∈ B′.

Then b = ψ −1 (b′1 K b′n ) = ψ −1 (b1′ ) ψ −1 (b′2 ) K ψ −1 (b′n ).
As ψ −1 (b′i ) ∈ F, let’s say its length is l i .
Since the string lengths have to be the same, and l(b) = 1,
1 = l 1 + L + l n , l i ≥ 1∀ i.
This is possible only if n = 1 and l 1 = 1, i.e., ψ(b) = b1′ ∈ B′.
Thus, ψ is a bijection from B onto B′.
Thus, B = B′ .
Conversely, let B = B′ , and f : B → B′ be a bijection. Then, from Fig. 3, and
using an argument similar to the one above, you can see that there is a
homomorphism h : F → F′ which extends i 2 o f : B → F′.
83
Special Groups and
F h F′
Semigroups

i1 i2

U U
f B′
B

Fig. 3: h extends i 2 o f : B → F′

Since f is a bijection, and F′ is free on B′, you can check that h is an

isomorphism. Hence, F − ~ F′.

Proof of Theorem 3: Take F′ = F in Lemma 1, to get the result.

From Lemma 1 we also get another useful result.

Theorem 4: Let F and F′ be two free semigroups on a finite set B. Then they
must be isomorphic.

Proof: Take B = B′ in Lemma 1, to get the result.

Though we have proved Theorems 3 and 4 for finite bases, the results hold true
even if B is infinite. However, we shall not prove these cases here.

Try some exercises now.

E14) Can a finite semigroup be free? Why, or why not?

E15) Given Z n , find a free semigroup F such that there is a homomorphism

from F onto (Z n , ).
•

E16) Check whether or not ψ : (Z, +) → (Z n , +) : ψ (i) = i(mod n ) is a

semigroup homomorphism. Is it a monomorphism? Why, or why not?

As we have said earlier, one reason for discussing semigroups in this course is
that they have several applications. For instance, in biology they are being
used for classifying organisms vis-à-vis the hereditary laws. They are also
useful for studying the DNA protein-coding problem. Interestingly, semigroups
are also being used in some of the social sciences to study various aspects of
social and financial networks. In the next section we shall consider the close
relationship that semigroups and monoids have with applications pertaining to
automata and to formal languages.

7.4 CONNECTIONS WITH (SEMI)AUTOMATA

‘Automata’ is the An automaton is a machine through which input data transforms into some
plural of ‘automaton’. output. Examples are a telephone switch board, a computer, etc. You may
wonder what connection this has with semigroups and monoids. In this section
we will first define automata in the abstract, and then indicate the connection
with semigroups and monoids.
84
Definition: A semiautomaton is a triple, S = (S, A, δ), where S and A are Applications of
Semigroups
non-empty sets and δ : S × A → S . S is called the set of states, A is the input
alphabet and δ is the “next-state function” of S, or the transition function.

So, as you can see, a semiautomaton doesn’t have an output function. For this,
we extend this object to an automaton.

Definition: An automaton is a 5-tuple A = (S, A1 , A 2 , δ, λ), where

(S, A1 , δ) is a semiautomaton, A 2 is a non-empty set (called the output
alphabet) and λ : S × A1 → A 2 is called the output function. George H. Mealy (1927-
2010) was an American
Further, an automaton is called finite (or Mealy) if all the sets involved are computer scientist who
finite. invented the automaton
named after him.
Relating this definition to the use of an input-output device, for s ∈ S, a ∈ A1 ,
δ(s, a ) ∈ S is the next state into which s is transformed by the input a.
Further, λ(s, a ) ∈ A 2 is the output of s resulting from the input a.

Finite automata are important in different branches of science and technology,

e.g., for modelling circuits. In practical examples, there are usually a collection
of only two switching states – on and off. In such a situation, S will be
Z 2 × Z 2 × K × Z 2 ; and A1 and A 2 will look similar too.

Let us consider some examples of Mealy automatons.

Example 6 (Marriage Automaton): Define the semiautomaton and automaton
in the following situation:
Hari and Wasima are a married couple. Wasima is always in one of three
moods – angry, or bored, or pleased. Hari does one of the three actions: he
argues calmly, or shouts, or cooks their favourite dishes. When Hari argues
calmly, it doesn’t change Wasima’s mood. When he shouts, she gets angry.
When he cooks, she is pleased. Also, Wasima only shouts when she is angry
and Hari shouts. Otherwise she is quiet.
Solution: Let us take
s1 : Wasima is angry a1 : Hari argues calmly
s 2 : Wasima is bored a 2 : Hari shouts
s3 : Wasima is pleased a 3 : Hari cooks their favourite dishes
b1 : Wasima shouts
b 2 : Wasima is quiet.
Then take S = {s1 , s 2 , s3 ), A1 = {a1 , a 2 , a 3} and A 2 = {b1 , b 2}. Define the
functions δ and λ by the following tables.

δ a1 a2 a3 λ a1 a2 a3
s1 s1 s1 s3 s1 b2 b1 b2
s2 s2 s1 s3 s2 b2 b2 b2
s3 s3 s1 s3 s3 b2 b2 b2

Then (S, A1 , δ) is a semiautomaton, and (S, A1 , A 2 , δ, λ) is a finite

automaton.
*** 85
 Special Groups and Example 7: Let S = {s0 , s1}, A1 = A 2 = {0, 1}, and let δ and λ be given by
Semigroups
δ 0 1 λ 0 1
s0 s0 s1 s0 0 1
s1 s1 s0 s1 0 1

Give a situation that could be described by the Mealy automaton

(S, A1 , A 2 , δ, λ).
Fig. 4: A Mealy automaton
state transition Solution: One situation could be the following:
diagram for
Example 7.
Take s0 : Machine stores 0, s1 : Machine stores 1.
The input i operates on S by taking the state si to the state s i+1 , addition being
modulo 2. The output is the same as the input.
***

Now, are you wondering what the connection is between semiautomata and
semigroups/monoids? Here it is!

Theorem 5: i) Given a semiautomaton S = (S, A, δ), there is a monoid

corresponding to it (denoted by M S ).
ii) Given an automaton (S, A1 , A 2 , δ, λ), there is a monoid corresponding
to it.

Proof:
i) Given a semiautomaton S = (S, A, δ), let FA be the free monoid on A.
Define δ : S × FA → S recursively by δ (s, e) = s,
δ (s, a ) = δ(s, a ) ∀ a ∈ A,
δ (s, a 1a 2 ) = δ( δ (s, a 1 ), a 2 ) for a1 , a 2 ∈ A,
M
δ (s, a 1a 2 K a r ) = δ( δ(s, a 1 K a r −1 ), a r ), a i ∈ A.

Now, for x ∈ FA , define f x : S → S : f x (s) = δ(s, x ).

Then f x o f y (s) = f x ( δ(s, y)) = δ( δ(s, y), x ) = δ(s, yx ) = f yx for x , y ∈ FA
and ∀ s ∈ S.
∴f x o f y = f yx ∀ x , y ∈ FA .

Now consider M S = ({f x x ∈ FA }, o).

The composition of maps is associative and f e is the identity in M S .
Thus, M S is a monoid.
So, given S , we have obtained M S .

ii) Given the automaton (S, A1, A 2 , δ, λ), we use (i) above to get the monoid
corresponding to it as M S′ , where S ′ = (S, A1 , δ).

Theorem 5 leads us to the following definition.

Definition: Let S = (S, A, δ) be a semi-automaton. The monoid of S is the

86 monoid M S (obtained in Theorem 5).
Let us now consider the converse of Theorem 5. Applications of
Semigroups

Proposition 1: Given a semigroup (S, ∗), (S, S, ∗) is a semiautomaton

corresponding to it.

Proof: Since ∗ : S × S → S, (S, S, ∗) is a semiautomaton.

In fact, we will now state a result, without proof, which tells us how closely the
study of (semi)automata is linked with the study of monoids.

Theorem 6: Given a monoid (S, o), there exists a (semi)automaton whose

monoid is isomorphic to (S, o).

Try some exercises now.

E17) i) A stamp automaton s has a capacity of ten stamps. Define this as a

semiautomaton such that the state si means there are i stamps in
s ; the inputs are ‘no coin is inserted’, ‘a correct coin is inserted’
and ‘a wrong coin is inserted’. Describe this semiautomaton by a
table.
ii) Extend (i) to an automaton, taking the outputs as ‘no output’, ‘a
stamp’, ‘a coin’. Describe the automaton by a table.

E18) Let S = 4 Z10 , A1 = {0, 1, 2, 3, 4} ≤ Z10 , A 2 = Z10 ,

δ : S × A1 → S : δ(s, a ) = sa ,
λ : S × A1 → A 2 : λ(s, a ) = s.
Give the tables for δ and λ for this automaton.
Further, find the monoid of this automaton.

Let us now move to another application of semigroups, closely linked to

automata.

7.5 APPLICATION TO FORMAL LANGUAGES

You may be familiar with two or three languages that are spoken around you,
like English, Hindi, etc. These are examples of ‘natural’ languages. Apart
from such languages, mathematicians and computer scientists have defined
‘formal’ languages. These languages also have alphabets and words, but the
words may not mean anything to a listener or reader. Such languages focus on
the structure of the statements or elements, that is, the syntax. Thus, they are
useful for studying linguistic patterns as well as the syntax of programming
languages.
Let us define such a language formally now.

Definition: Let A be a non-empty set. Let A* be the free monoid on A, i.e.,

A∗ is FA ∪ {Λ}, where Λ is the empty word. So A* is the set of all words
over A, i.e., A∗ = {a 1a 2 K a n a i ∈ A, n ∈ N ∪ {0}}, together with the operation
of concatenation (or juxtaposition). A formal language L over the set A is a
87
Special Groups and subset of A*. Here A is called the alphabet over which L is defined, and
Semigroups elements of A* are called words.

For example, L can be all of A*. This is called the universal language.

As another example, take A = {a , b}. Then L can be A, or L can be

{aaaba , bab, a−1}, or any other finite or infinite subset of A*.

Another example is L = «, which is called the empty language.

So, as you can see from the above, a formal language is about the form (i.e.,
the syntax) and not about meaning. Further, the mathematical theory of formal
Fig. 5: Noam Chomsky
(born: 1928)
languages doesn’t study individual languages, but the classes of language, and
the mechanisms that describe these classes. These are closely linked with
automata. Noam Chomsky, American linguist and cognitive scientist, has
presented an hierarchy of these classes, viz., L1 ⊆ L 2 ⊆ L3 ⊆ L 4 , where
L1 : Regular languages, characterised by finite state automata;
L2 : Context-free languages, characterised by pushdown automata;
L3 : Context-sensitive languages, characterised by linear bounded automata;
L4 : Computable languages, characterised by Turing machines.

The semigroups/monoids that characterise these classes of languages are the

monoids corresponding to the automaton concerned.

Let us now consider Chomsky’s approach to formal languages. This is

based on the use of grammar, which we now define.

Definitions: A phase-structure grammar is a 4-tuple G = (A, G, →, g 0 ),

where A and G are non-empty disjoint finite sets, g 0 ∈ G and → is a finite
relation from FV , the free semigroup on V, into V∗, i.e., a finite subset of
FV × V ∗, where V = A ∪ G. This 4-tuple is often called ‘grammar’, in short.
Here A is called the alphabet of G ; G is the set of grammar symbols; V is the
complete vocabulary; the elements of → are called rewriting rules; and g 0
is the initial symbol.

The relation → is the heart of the grammar. It tells us how one string
transforms into another. For x ∈ FV , y ∈ V ∗, we will write ( x , y) ∈→ also as
x → y. For instance, if w 1 = uxv ∈ FV , then x → y applied to w 1 gives us
w 2 = uyv. This is also indicated by saying that w 1 derives w 2 , or that w 2 is
derived from w1 , and is denoted by w 1 ⇒ w 2 .

So, a succession of strings can be obtained by applying the rewriting rules.

If w 1 ⇒ w 2 ⇒ K ⇒ w n , then we say that w 1 derives w n and denote this
∗
string of derivations by w 1 ⇒ w n.
∗
So, ⇒ could be zero, one or more applications of the rewriting rules. For
∗
example, w ⇒ w is always true.

88 Now, we are ready to define a language based on a grammar.

 Applications of
Definition: Let G = (A, G , →, g 0 ) be a phase-structure grammar. Then Semigroups
L(G ) = {w ∈ A∗ g 0 ⇒
∗ w } is called the language generated by G .

∗
Caution: L(G ) ⊆ A∗, while W = {w g 0 ⇒ w} ⊆ V ∗. So L(G ) ⊆ W.

Let us consider some examples.

Example 8: If G = ({a}, {g 0}, {g 0 → a}, g 0 ) , find L(G ) .

Solution: Firstly, g 0 ≠ a , by definition of a grammar. Now, any element of
∗
L(G ) is of the form w ∈ {a}∗ such that g 0 ⇒ w. Since w ∈ {a}∗ , w = a n , where
n ∈ N, or w = Λ.
If w 1 is derived from g 0 by applying g 0 → a , then w 1 = a. Also, w 1 ⇒ w 2 by
applying g 0 → a gives us w 2 = a , since there is no presence of g 0 in the string
w 1.
Thus, L(G ) = {a}.
***

Example 9: Let G = ({a}, {g 0}, {g 0 → a , g 0 → ag 0 }, g 0 ). Find L(G ).

Solution: As in the previous example, g 0 ≠ a. Here g 0 ⇒ z means z = a or
z = ag 0 . Applying any rewriting rule to z gives us z1 = a or z1 = aa or
z1 = aag 0 .
Thus, the strings of A∗ that can be derived from g 0 by applying → are
a , aa , aaa , K.
So L(G ) = {a n n ∈ N} = FA , where A = {a}.

***

Example 10: Find a grammar that generates the language {a i b i i ≥ 1}.

Solution: Consider G = ({a , b}, {g 0 } , {g 0 → ab, g 0 → ag 0 b} , g 0 ).

∗ i i
Then g 0 ⇒ ab, g 0 ⇒ a b ∀ i ≥ 2.
Hence L(G ) = {a i bi i ≥ 1}.
***

Here is an important remark.

Remark 2: Given a language, we may or may not be able to find a grammar

that generates it.

Why don’t you try some exercises now?

E19) Let A = {a , b}, G = {g 0 }, where g 0 ∉ A. Determine L(G ) if the set of

rewriting rules is given by
i) {g 0 → a , g 0 → b}
ii) {g 0 → Λ , g 0 → a , g 0 → aba}
89
Special Groups and iii) {g 0 → g 0 }
Semigroups
E20) Find a grammar that generates {b, aba , aabaa , aaabaaa , K}.

E21) Find a grammar with the alphabet set A that generates A∗ , i.e., the
universal language.

Now, let us look at what kind of grammars make up the classes L1 to L 4 in

Chomsky’s hierarchy, mentioned earlier.

Definitions: 1) A language L ⊆ A∗ is regular if it can be generated by a

grammar with rewriting rules of the form x → ay, x → a for a ∈ A∗ and
x , y ∈ G. (For those of you familiar with deterministic finite accepters
(dfa), a language L is regular iff L = L(M) for some dfa M. )

2) A grammar G is called context-free if all its rewriting rules are of the

form x → y, where x ∈ G and y ∈ A∗.
A language L is called context-free if L = L(G ) for some context-free
grammar G.

3) A grammar G is called context-sensitive if for every rewriting rule

x → y in G , we have l ( x ) ≤ l ( y), where l ( x ) is the length of the string
x ∈ A∗ . A language L is called context-sensitive if L = L(G ) for some
context sensitive grammar G.

4) A language L is called a computable language if L = L(G ) for some

grammar G .

Here is a remark about this.

Remark 3: As you can see, every regular language is context-free, every

context-free language is context-sensitive, and all these types of languages are
computable languages.

Let us look at some examples.

Example 11: Show that every finite language is regular and context-free.
Solution: Let L = {x1, x 2 , K , x n } ⊆ A∗ for some A. Each of these elements
can be obtained from a finite set of elements S of A by applying the rules of
the form g 0 → g 0a , and g 0 → Λ, where g 0 ∈ G, a ∈ S. For instance, if
x i = s1 K s n , then g 0 → g 0s n → g 0s n −1s n → K → g 0 x i → x i , applying
g 0 → g 0a first, and finally g 0 → Λ. Therefore, L is regular.

Note that, over here the rewriting rules have only g 0 in the LHS. Hence L is
context-free.
***
Example 12: Show that L = {xy n n ≥ 0} is a regular language, and context-
90 free.
 Applications of
Solution: Here A = {x , y}, G = {g 0 }, g 0 ∉ A, and the rules are Semigroups
g 0 → x , g 0 → g 0 y.
Then L = L(G ), and hence L is regular.
Here too, the rewriting rules only have g 0 in the LHS. Hence L is context-
free.
***

We will now state, without proof, a result here to help us get an example of a
language which is not regular.

Theorem 7: Let A = {a} and L ⊆ A∗ . L is regular if and only if A set {p n n ∈ N} is

L = {a n | n ∈ P}, where P is a periodic subset of N ∪ {0}. called periodic if
∃ k , n 0 ∈ N such that
2
p n + k − p n is constant
Using this result, we can immediately say that {a n n ∈ N ∪ {0}} is not regular ∀ n ≥ n0.
2
since {n n ∈ N ∪ {0}} is not a periodic set.

Try some exercises now.

E22) Show that L(G 1 ) = L(G 2 ), where

G 1 = ({a , b}, {g 0}, {g 0 → g 0g 0 , g 0 → aa}, g 0 ) and Different grammars
G 2 = ({a , b}, {g 0}, {g 0 → ag 0a , g 0 → aa}, g 0 ). can generate the
same language.

E23) Check whether or not {a n n ≡ 3(mod 4)} is regular.

E24) Give an example, with justification, of a computable language.

With this we come to the end of our discussion on semigroups, monoids and
their applications. Let us now take a look at the points covered by us in this
unit.

7.5 SUMMARY
In this unit we have discussed the following points.

1) The definition, and some examples, of a semigroup/monoid.

2) What the unit group of a monoid is.

3) The definition of a subsemigroup and of a semigroup

homomorphism/isomorphism.

4) Any non-empty intersection of subsemigroups of a semigroup S is a

subsemigroup of S. This is not true if ‘intersection’ is replaced by
‘union’.

5) The subsemigroup of S generated by T ⊆ S is the smallest

subsemigroup of S containing T, which is ∩{Si Si ≤ S, T ⊆ Si }. This is
i
denoted by < T > . 91
Special Groups and 6) The definition, and examples, of a free semigroup.
Semigroups
7) A free semigroup is infinite, even if its basis is finite.

8) For any set A ≠ «, there exists a semigroup FA which is free on A. In

fact, FA = {a 1a 2 K a n a i ∈ A}, the set of all finite formal products of
elements of A.

9) Let a semigroup F be free on a finite set A and on a set A′. Then A′ is

finite, and A = A′ .

10) If F and F′ are both free semigroups on A, then F ~ F′.

11) The definition, and examples, of (semi)automata.

12) Any semigroup/monoid gives rise to a (semi)automaton.

13) Given a (semi)automaton, there is a monoid corresponding to it.

14) For A ≠ «, A∗ = FA ∪ {Λ} is a monoid with respect to concatenation,

where Λ is the empty word. A formal language L over the set A is a
subset of A∗ .

15) A grammar is a 4-tuple (A, G , →, g 0 ) where A is its alphabet, G is the

set of grammar symbols, → is the set of rewriting rules, and g 0 ∈ G is
the initial symbol. Here A ∩ G = «, and V = A ∪ G is called the
complete vocabulary.

7.6 SOLUTIONS/ANSWERS
E1) All three sets are non-empty, and closed w.r.t. the operations given.
However, the first two are semigroups, and (Z, −) is not, since ‘–’ is not
an associative operation.

E2) Since S ≠ «, S × S = «. Therefore, Re1(S) ≠ «.

For R 1 , R 2 ⊆ S × S, R 1 ∗ R 2 ⊆ S × S.
Therefore, ∗ is a binary operation.
Now, let R 1 , R 2 , R 3 ∈ Rel (S).
Then (α, β) ∈ (R 1 ∗ R 2 ) ∗ R 3
⇔ ∃ s ∈ S s.t. (α, s) ∈ R 1 ∗ R 2 and (s, β) ∈ R 3
⇔ ∃ s ∈ S, t ∈ S s.t. (α, t ) ∈ R 1 , ( t, s) ∈ R 2 and (s, β) ∈ R 3
⇔ ∃ t ∈ S s.t. (α, t ) ∈ R 1 and ( t, β) ∈ R 2 ∗ R 3
⇔ (α, β ) ∈ R 1 ∗ ( R 2 ∗ R 3 )
Therefore, ∗ is associative.
Thus, (Rel (S), ∗) is a semigroup.

E3) ℘(X) ≠ « since X ≠ «.

Next, ⊗ is a binary operation on ℘(X).
92
 Applications of
Finally, (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C) ∀ A, B, C ∈ ℘(X) since ∗ is Semigroups
associative on S.

E4) Since n1 n 2 ∈ N ∀ n1, n 2 ∈ N it follows that (N, ) ≤ (Z, ).

• • •

E5) i) As noted earlier, the unit group for this is {0}.

ii) In this case the identity is 1. Hence the unit group is {± 1}.
iii) Here the identity is S. Therefore, the only subset of S which has an
inverse is S.
iv) Id : S → S is the identity map.
Thus, Bij(S, S), the set of all bijective mappings from S onto S, is
the unit group of Map(S, S).

E6) f ( x.y) = 0 = 0 + 0 = f ( x ) + f ( y) ∀ x , y ∈ Z .
∴ f is a homomorphism.

E7) Define
φ :℘({1, 2, 3}) → ℘({a , b, c}) : φ(«) = «, φ({1}) = {a}, φ({2}) = {b}, φ({3}) = {c},
and extend φ elementwise.
This means that we consider the subsets of {1, 2, 3}, namely,
«,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
Then, under φ , the images of these are
«, {a}, {b}, {c}, {a , b}, {a , c}, {b, c}, {a , b, c}, respectively.
You can check that φ (S1 ∩ S2 ) = φ (S1 ) ∩ φ (S2 ) ∀ subsets S1 , S2 of
{1, 2, 3}.
Also, from the definition of φ, it is clear that φ is a monomorphism and
an epimorphism. Hence, φ is an isomorphism.

E8) Consider T = ∩ Si , where Si ≤ S ∀ i ∈ I, the indexing set. (Note that I

i∈I
may be finite or infinite.)
For x , y ∈ T, x , y ∈ Si ∀ i ∈ I.
⇒ x ∗ y ∈ Si ∀ i ∈ I
⇒ x ∗ y ∈T
∴ T ≤ S.

E9) Consider S = (Z, + ), and take S1 = (N, + ), S2 = (Z − , +), where Z − is the

set of negative integers.
Then S1 ∪ S2 = Z \ {0}, which is not a semigroup w.r.t. addition (e.g.,
1 + (−1) ∉ Z \ {0}).

E10) Let (S = {s1, K , s n }, ⋅) be a subsemigroup of (G, ⋅).

Consider s ∈ S, and take S′ = {ss1 , ss 2 , K , ss n }. Then S′ ⊆ S.
Also, ss i = ss j ⇒ s i = s j , since ss i , ss j ∈ G. So, S′ = S.
∴ S′ = S.
∴ ∃ i s.t. ss i = s in S, and in G.
∴ s i = e. 93
Special Groups and Thus, e ∈ S.
Semigroups Using a similar argument, you can show that s −1 ∈ S ∀ s ∈ S.
Thus, S is a subgroup of G.
However, if G is infinite, this need not hold. E.g., (N, ) is a •

subsemigroup of the group (R∗ , ), but (N, ) is not a group.

• •

E11) In general, ℘(S) is generated by itself. Thus, if ℘(S) is finite, i.e., if S is

finite, then ℘(S) will be finitely generated.
Now, take the case when S is infinite. Then ℘(S) is infinite. Suppose it
is finitely generated, say, by S1 , K, Sr . Then
{
S1 , K , Sr = Si1 ∩ K ∩ Sin 1 ≤ i1 < i 2 < K < i n ≤ r is also a finite }
collection of subsets of S, and hence this is not infinite. Therefore, it
cannot be ℘(S). Thus, ℘(S) is f.g. iff S is finite.

( N, )
•
E12) (N, ) is not free. To prove this, suppose (N, ) is free. Then we have the
• •

commutative diagram in Fig. 6, where i(n ) = Id(n ) = n ∀ n ∈ N. So f

f will be an isomorphism. But (N, + ) has no identity element, while (N, ) •

i
does. So, we reach a contradiction. Hence (N, ) is not free. •

Id ( N, + )
N
On the same lines you can show that (N ∪ {0}, + ) and (R, +) are not
Fig. 6: Why ( N, ) is not
•

free semigroups.
a free semigroup.
E13) i) A non-empty subset A, of a monoid (M, ∗), is called a submonoid
• if A contains the identity of M, and
• A is closed w.r.t. ∗ .

ii) A monoid (M, ∗) is called free (on a non-empty set B ) if

• M ⊇ B ; and
• any mapping f from B into a monoid (M′, ∗′) can be extended
to a unique monoid homomorphism from M to M′.

E14) Let s ∈ S. If S is free, then {s n n ∈ N} ⊆ S, where s n ≠ s m for n = m.

∴ S can’t be finite.

E15) Let {a1 , a 2 , K, a r } generate (Z n , ), where a i ∈ N. Take F to be the free

•

semigroup on {a1 , a 2 , K, a r } ⊆ Z. Define

ψ : F → Z n : ψ( x1x 2 K x k ) = ( x1 x 2 K x k )(mod n ), where x1x 2 K x k is a
• • •

string in F.
Then ψ is surjective, and ψ (xy ) = ψ (x ) ψ ( y) ∀ x , y ∈ F. •

E16) Since ψ (x + y) = ψ ( x ) + ψ ( y), ψ is a homomorphism. It is not 1 − 1,

since, e.g., ψ (0) = ψ (n ) and 0 ≠ n in Z.

E17) i) S = {s 0 , s1 , s 2 , K , s10 }, A = {a1 , a 2 , a 3}, where

a1 : No coin is inserted
94
 Applications of
a 2 : A correct coin is inserted Semigroups
a 3 : A wrong coin is inserted
δ : S × A → S is defined by the following table.

δ a1 a2 a3
s0 s0 s0 s0
s1 s1 s0 s1
s2 s2 s1 s2
M M M M
s10 s10 s9 s10

ii) Let A 2 = {b1 , b 2 , b 3}, where

b1 : No output
b 2 : A stamp
b3 : A coin
Then λ : S × A1 → A 2 is defined by the following table:

λ a1 a2 a3
s0 b1 b3 b3
s1 b1 b2 b3
s2 b1 b2 b3
M M M M
s10 b1 b2 b3

E18) Here S = {0, 2, 4, 6, 8}.

δ 0 1 2 3 4 λ 0 1 2 3 4
0 0 0 0 0 0 0 0 0 0 0 0
2 0 2 4 6 8 2 2 2 2 2 2
4 0 4 8 2 6 4 4 4 4 4 4
6 0 6 2 8 4 6 6 6 6 6 6
8 0 8 6 4 2 8 8 8 8 8 8

The monoid corresponding to (S, A1 , δ) is ({f x x ∈ FA1 }, o), where FA1 is

the free monoid on 5 symbols.

E19) i) Starting with g 0 , any derivation will lead to a or b and to no other

string. So, L(G ) = {a , b}.

ii) Here, any string can be Λ, a , aba.

So, L(G ) = {Λ, a , aba}.

iii) Here, there is no string in A∗ derived from g 0 . So, L(G ) = «.

E20) Take G = ({a , b}, {g 0 }, {g 0 → b, g 0 → ag 0a}, g 0 ), where g 0 ∉ {a , b}.

Then the strings would be b, aba , aabaa , K.
95
Special Groups and E21) G = (A, {g 0}, {g 0 → Λ, g 0 → g 0a a ∈ A}, g 0 ), where g 0 ∉ A.
Semigroups
Then L(G ) = A∗.

E22) In both cases L = {(aa ) n n ∈ N}.

E23) Since {n n ≡ 3(mod 4)} is a periodic set, {a n n ≡ 3(mod 4)} is regular.

E24) For instance, L in E22 is computable since it is L(G 1 ).

96