ńņš. 1 |

Robert B. Ash

PREFACE

This is a text for the basic graduate sequence in abstract algebra, oļ¬ered by most

universities. We study fundamental algebraic structures, namely groups, rings, ļ¬elds and

modules, and maps between these structures. The techniques are used in many areas of

mathematics, and there are applications to physics, engineering and computer science as

well. In addition, I have attempted to communicate the intrinsic beauty of the subject.

Ideally, the reasoning underlying each step of a proof should be completely clear, but the

overall argument should be as brief as possible, allowing a sharp overview of the result.

These two requirements are in opposition, and it is my job as expositor to try to resolve

the conļ¬‚ict.

My primary goal is to help the reader learn the subject, and there are times when

informal or intuitive reasoning leads to greater understanding than a formal proof. In the

text, there are three types of informal arguments:

1. The concrete or numerical example with all features of the general case. Here, the

example indicates how the proof should go, and the formalization amounts to substi-

tuting Greek letters for numbers. There is no essential loss of rigor in the informal

version.

2. Brief informal surveys of large areas. There are two of these, p-adic numbers and

group representation theory. References are given to books accessible to the beginning

graduate student.

3. Intuitive arguments that replace lengthy formal proofs which do not reveal why a

result is true. In this case, explicit references to a precise formalization are given. I am

not saying that the formal proof should be avoided, just that the basic graduate year,

where there are many pressing matters to cope with, may not be the appropriate place,

especially when the result rather than the proof technique is used in applications.

I would estimate that about 90 percent of the text is written in conventional style,

and I hope that the book will be used as a classroom text as well as a supplementary

reference.

Solutions to all problems are included in the text; in my experience, most students

ļ¬nd this to be a valuable feature. The writing style for the solutions is similar to that

of the main text, and this allows for wider coverage as well as reinforcement of the basic

ideas.

Chapters 1ā“4 cover basic properties of groups, rings, ļ¬elds and modules. The typi-

cal student will have seen some but not all of this material in an undergraduate algebra

course. [It should be possible to base an undergraduate course on Chapters 1ā“4, traversed

at a suitable pace with detailed coverage of the exercises.] In Chapter 4, the fundamental

structure theorems for ļ¬nitely generated modules over a principal ideal domain are de-

veloped concretely with the aid of the Smith normal form. Students will undoubtedly be

comfortable with elementary row and column operations, and this will signiļ¬cantly aid

the learning process.

In Chapter 5, the theme of groups acting on sets leads to a nice application to com-

binatorics as well as the fundamental Sylow theorems and some results on simple groups.

Analysis of normal and subnormal series leads to the Jordan-HĀØlder theorem and to solv-

o

able and nilpotent groups. The ļ¬nal section, on deļ¬ning a group by generators and

relations, concentrates on practical cases where the structure of a group can be deduced

from its presentation. Simplicity of the alternating groups and semidirect products are

covered in the exercises.

Chapter 6 goes quickly to the fundamental theorem of Galois theory; this is possible

because the necessary background has been covered in Chapter 3. After some examples

of direct calculation of a Galois group, we proceed to ļ¬nite ļ¬elds, which are of great

importance in applications, and cyclotomic ļ¬elds, which are fundamental in algebraic

number theory. The Galois group of a cubic is treated in detail, and the quartic is

covered in an appendix. Sections on cyclic and Kummer extensions are followed by Galoisā™

fundamental theorem on solvability by radicals. The last section of the chapter deals with

transcendental extensions and transcendence bases.

In the remaining chapters, we begin to apply the results and methods of abstract

algebra to related areas. The title of each chapter begins with āIntroducing . . . ā, and the

areas to be introduced are algebraic number theory, algebraic geometry, noncommutative

algebra and homological algebra (including categories and functors).

Algebraic number theory and algebraic geometry are the two major areas that use the

tools of commutative algebra (the theory of commutative rings). In Chapter 7, after an

example showing how algebra can be applied in number theory, we assemble some algebraic

equipment: integral extensions, norms, traces, discriminants, Noetherian and Artinian

modules and rings. We then prove the fundamental theorem on unique factorization of

ideals in a Dedekind domain. The chapter concludes with an informal introduction to

p-adic numbers and some ideas from valuation theory.

Chapter 8 begins geometrically with varieties in aļ¬ne space. This provides moti-

vation for Hilbertā™s fundamental theorems, the basis theorem and the Nullstellensatz.

Several equivalent versions of the Nullstellensatz are given, as well as some corollaries

with geometric signiļ¬cance. Further geometric considerations lead to the useful algebraic

techniques of localization and primary decomposition. The remainder of the chapter is

concerned with the tensor product and its basic properties.

Chapter 9 begins the study of noncommutative rings and their modules. The basic

theory of simple and semisimple rings and modules, along with Schurā™s lemma and Ja-

cobsonā™s theorem, combine to yield Wedderburnā™s theorem on the structure of semisimple

rings. We indicate the precise connection between the two popular deļ¬nitions of simple

ring in the literature. After an informal introduction to group representations, Maschkeā™s

theorem on semisimplicity of modules over the group algebra is proved. The introduction

of the Jacobson radical gives more insight into the structure of rings and modules. The

chapter ends with the Hopkins-Levitzki theorem that an Artinian ring is Noetherian, and

the useful lemma of Nakayama.

In Chapter 10, we introduce some of the tools of homological algebra. Waiting until

the last chapter for this is a deliberate decision. Students need as much exposure as

possible to speciļ¬c algebraic systems before they can appreciate the broad viewpoint of

category theory. Even experienced students may have diļ¬culty absorbing the abstract

deļ¬nitions of kernel, cokernel, product, coproduct, direct and inverse limit. To aid the

reader, functors are introduced via the familiar examples of hom and tensor. No attempt

is made to work with general abelian categories. Instead, we stay within the category of

modules and study projective, injective and ļ¬‚at modules.

In a supplement, we go much farther into homological algebra than is usual in the basic

algebra sequence. We do this to help students cope with the massive formal machinery

that makes it so diļ¬cult to gain a working knowledge of this area. We concentrate on

the results that are most useful in applications: the long exact homology sequence and

the properties of the derived functors Tor and Ext. There is a complete proof of the

snake lemma, a rarity in the literature. In this case, going through a long formal proof is

entirely appropriate, because doing so will help improve algebraic skills. The point is not

to avoid diļ¬culties, but to make most eļ¬cient use of the ļ¬nite amount of time available.

Robert B. Ash

October 2000

Further Remarks

Many mathematicians believe that formalism aids understanding, but I believe that

when one is learning a subject, formalism often prevents understanding. The most im-

portant skill is the ability to think intuitively. This is true even in a highly abstract ļ¬eld

such as homological algebra. My writing style reļ¬‚ects this view.

Classroom lectures are inherently ineļ¬cient. If the pace is slow enough to allow

comprehension as the lecture is delivered, then very little can be covered. If the pace

is fast enough to allow decent coverage, there will unavoidably be large gaps. Thus

the student must depend on the textbook, and the current trend in algebra is to produce

massive encyclopedias, which are likely to be quite discouraging to the beginning graduate

student. Instead, I have attempted to write a text of manageable size, which can be read

by students, including those working independently.

Another goal is to help the student reach an advanced level as quickly and eļ¬ciently as

possible. When I omit a lengthy formal argument, it is because I judge that the increase

in algebraic skills is insuļ¬cient to justify the time and eļ¬ort involved in going through

the formal proof. In all cases, I give explicit references where the details can be found.

One can argue that learning to write formal proofs is an essential part of the studentā™s

mathematical training. I agree, but the ability to think intuitively is fundamental and

must come ļ¬rst. I would add that the way things are today, there is absolutely no danger

that the student will be insuļ¬ciently exposed to formalism and abstraction. In fact there

is quite a bit of it in this book, although not 100 percent.

I oļ¬er this text in the hope that it will make the studentā™s trip through algebra more

enjoyable. I have done my best to avoid gaps in the reasoning. I never use the phrase

āit is easy to seeā under any circumstances. I welcome comments and suggestions for

improvement.

Copyright c 2000, by Robert B. Ash

Paper or electronic copies for noncommercial use may be made freely without explicit

permission of the author. All other rights are reserved.

ABSTRACT ALGEBRA: THE BASIC GRADUATE YEAR

TABLE OF CONTENTS

CHAPTER 0 PREREQUISITES

0.1 Elementary Number Theory

0.2 Set Theory

0.3 Linear Algebra

CHAPTER 1 GROUP FUNDAMENTALS

1.1 Groups and Subgroups

1.2 Permutation Groups

1.3 Cosets, Normal Subgroups and Homomorphisms

1.4 The Isomorphism Theorems

1.5 Direct Products

CHAPTER 2 RING FUNDAMENTALS

2.1 Basic Deļ¬nitions and Properties

2.2 Ideals, Homomorphisms and Quotient Rings

2.3 The Isomorphism Theorems For Rings

2.4 Maximal and Prime Ideals

2.5 Polynomial Rings

2.6 Unique Factorization

2.7 Principal Ideal Domains and Euclidean Domains

2.8 Rings of Fractions

2.9 Irreducible Polynomials

CHAPTER 3 FIELD FUNDAMENTALS

3.1 Field Extensions

3.2 Splitting Fields

3.3 Algebraic Closures

3.4 Separability

3.5 Normal Extensions

CHAPTER 4 MODULE FUNDAMENTALS

4.1 Modules and Algebras

4.2 The Isomorphism Theorems For Modules

4.3 Direct Sums and Free Modules

4.4 Homomorphisms and Matrices

4.5 Smith Normal Form

4.6 Fundamental Structure Theorems

4.7 Exact Sequences and Diagram Chasing

CHAPTER 5 SOME BASIC TECHNIQUES OF GROUP THEORY

5.1 Groups Acting on Sets

5.2 The Orbit-Stabilizer Theorem

5.3 Applications to Combinatorics

5.4 The Sylow Theorems

5.5 Applications of the Sylow Theorems

5.6 Composition Series

5.7 Solvable and Nilpotent Groups

5.8 Generators and Relations

CHAPTER 6 GALOIS THEORY

6.1 Fixed Fields and Galois Groups

6.2 The Fundamental Theorem

6.3 Computing a Galois Group Directly

6.4 Finite Fields

6.5 Cyclotomic Fields

6.6 The Galois Group of a Cubic

6.7 Cyclic and Kummer Extensions

6.8 Solvability by Radicals

6.9 Transcendental Extensions

Appendix to Chapter 6

CHAPTER 7 INTRODUCING ALGEBRAIC NUMBER THEORY

7.1 Integral Extensions

7.2 Quadratic Extensions of the Rationals

7.3 Norms and Traces

7.4 The Discriminant

7.5 Noetherian and Artinian Modules and Rings

7.6 Fractional Ideals

7.7 Unique Factorization of Ideals in a Dedekind Domain

7.8 Some Arithmetic in Dedekind Domains

7.9 p-adic Numbers

CHAPTER 8 INTRODUCING ALGEBRAIC GEOMETRY

8.1 Varieties

8.2 The Hilbert Basis Theorem

8.3 The Nullstellensatz: Preliminaries

8.4 The Nullstellensatz: Equivalent Versions and Proof

8.5 Localization

8.6 Primary Decomposition

8.7 Tensor Product of Modules Over a Commutative Ring

8.8 General Tensor Products

CHAPTER 9 INTRODUCING NONCOMMUTATIVE ALGEBRA

9.1 Semisimple Modules

9.2 Two Key Theorems

9.3 Simple and Semisimple Rings

9.4 Further Properties of Simple Rings, Matrix Rings, and Endomorphisms

9.5 The Structure of Semisimple Rings

9.6 Maschkeā™s Theorem

9.7 The Jacobson Radical

9.8 Theorems of Hopkins-Levitzki and Nakayama

CHAPTER 10 INTRODUCING HOMOLOGICAL ALGEBRA

10.1 Categories

10.2 Products and Coproducts

10.3 Functors

10.4 Exact Functors

10.5 Projective Modules

10.6 Injective Modules

10.7 Embedding into an Injective Module

10.8 Flat Modules

10.9 Direct and Inverse Limits

Appendix to Chapter 10

SUPPLEMENT

S1 Chain Complexes

S2 The Snake Lemma

S3 The Long Exact Homology Sequence

S4 Projective and Injective Resolutions

S5 Derived Functors

S6 Some Properties of Ext and Tor

S7 Base Change in the Tensor Product

SOLUTIONS TO PROBLEMS

Chapter 0

Prerequisites

All topics listed in this chapter are covered in A Primer of Abstract Mathematics by

Robert B. Ash, MAA 1998.

0.1 Elementary Number Theory

The greatest common divisor of two integers can be found by the Euclidean algorithm,

which is reviewed in the exercises in Section 2.5. Among the important consequences of

the algorithm are the following three results.

0.1.1

If d is the greatest common divisor of a and b, then there are integers s and t such that

sa + tb = d. In particular, if a and b are relatively prime, there are integers s and t such

that sa + tb = 1.

0.1.2

If a prime p divides a product a1 Ā· Ā· Ā· an of integers, then p divides at least one ai

0.1.3 Unique Factorization Theorem

If a is an integer, not 0 or Ā±1, then

(1) a can be written as a product p1 Ā· Ā· Ā· pn of primes.

(2) If a = p1 Ā· Ā· Ā· pn = q1 Ā· Ā· Ā· qm , where the pi and qj are prime, then n = m and, after

renumbering, pi = Ā±qi for all i.

[We allow negative primes, so that, for example, ā’17 is prime. This is consistent with the

general deļ¬nition of prime element in an integral domain; see Section 2.6.]

1

2 CHAPTER 0. PREREQUISITES

0.1.4 The Integers Modulo m

If a and b are integers and m is a positive integer ā„ 2, we write a ā” b mod m, and say

that a is congruent to b modulo m, if a ā’ b is divisible by m. Congruence modulo m

is an equivalence relation, and the resulting equivalence classes are called residue classes

mod m. Residue classes can be added, subtracted and multiplied consistently by choosing

a representative from each class, performing the appropriate operation, and calculating

the residue class of the result. The collection Zm of residue classes mod m forms a

commutative ring under addition and multiplication. Zm is a ļ¬eld if and only if m is

prime. (The general deļ¬nitions of ring, integral domain and ļ¬eld are given in Section 2.1.)

0.1.5

(1) The integer a is relatively prime to m if and only if a is a unit mod m, that is, a has

a multiplicative inverse mod m.

(2) If c divides ab and a and c are relatively prime, then c divides b.

(3) If a and b are relatively prime to m, then ab is relatively prime to m.

(4) If ax ā” ay mod m and a is relatively prime to m, then x ā” y mod m.

(5) If d = gcd(a, b), the greatest common divisor of a and b, then a/d and b/d are relatively

prime.

(6) If ax ā” ay mod m and d = gcd(a, m), then x ā” y mod m/d.

(7) If ai divides b for i = 1, . . . , r, and ai and aj are relatively prime whenever i = j, then

the product a1 Ā· Ā· Ā· ar divides b.

(8) The product of two integers is their greatest common divisor times their least common

multiple.

0.1.6 Chinese Remainder Theorem

If m1 , . . . , mr are relatively prime in pairs, then the system of simultaneous equations

x ā” bj mod mj , j = 1, . . . , r, has a solution for arbitrary integers bj . The set of solutions

forms a single residue class mod m=m1 Ā· Ā· Ā· mr , so that there is a unique solution mod m.

This result can be derived from the abstract form of the Chinese remainder theorem;

see Section 2.3.

0.1.7 Eulerā™s Theorem

The Euler phi function is deļ¬ned by Ļ•(n) = the number of integers in {1, . . . , n} that

are relatively prime to n. For an explicit formula for Ļ•(n), see Section 1.1, Problem 13.

Eulerā™s theorem states that if n ā„ 2 and a is relatively prime to n, then aĻ•(n) ā” 1 mod n.

0.1.8 Fermatā™s Little Theorem

If a is any integer and p is a prime not dividing a, then apā’1 ā” 1 mod p. Thus for any

integer a and prime p, whether or not p divides a, we have ap ā” a mod p.

For proofs of (0.1.7) and (0.1.8), see (1.3.4).

0.2. SET THEORY 3

0.2 Set Theory

0.2.1

A partial ordering on a set S is a relation on S that is reļ¬‚exive (x ā¤ x for all x ā S),

antisymmetric (x ā¤ y and y ā¤ x implies x = y), and transitive (x ā¤ y and y ā¤ z implies

x ā¤ z). If for all x, y ā S, either x ā¤ y or y ā¤ x, the ordering is total.

0.2.2

A well-ordering on S is a partial ordering such that every nonempty subset A of S has a

smallest element a. (Thus a ā¤ b for every b ā A).

0.2.3 Well-Ordering Principle

Every set can be well-ordered.

0.2.4 Maximum Principle

If T is any chain (totally ordered subset) of a partially ordered set S, then T is contained

in a maximal chain M . (Maximal means that M is not properly contained in a larger

chain.)

0.2.5 Zornā™s Lemma

If S is a nonempty partially ordered set such that every chain of S has an upper bound

in S, then S has a maximal element.

(The element x is an upper bound of the set A if a ā¤ x for every a ā A. Note that

x need not belong to A, but in the statement of Zornā™s lemma, we require that if A is a

chain of S, then A has an upper bound that actually belongs to S.)

0.2.6 Axiom of Choice

Given any family of nonempty sets Si , i ā I, we can choose an element of each Si .

Formally, there is a function f whose domain is I such that f (i) ā Si for all i ā I.

The well-ordering principle, the maximum principle, Zornā™s lemma, and the axiom of

choice are equivalent in the sense that if any one of these statements is added to the basic

axioms of set theory, all the others can be proved. The statements themselves cannot be

proved from the basic axioms. Constructivist mathematics rejects the axiom of choice

and its equivalents. In this philosophy, an assertion that we can choose an element from

each Si must be accompanied by an explicit algorithm. The idea is appealing, but its

acceptance results in large areas of interesting and useful mathematics being tossed onto

the scrap heap. So at present, the mathematical mainstream embraces the axiom of

choice, Zornā™s lemma et al.

4 CHAPTER 0. PREREQUISITES

0.2.7 Proof by Transļ¬nite Induction

To prove that statement Pi holds for all i in the well-ordered set I, we do the following:

1. Prove the basis step P0 , where 0 is the smallest element of I.

2. If i > 0 and we assume that Pj holds for all j < i (the transļ¬nite induction

hypothesis), prove Pi .

It follows that Pi is true for all i.

0.2.8

We say that the size of the set A is less than or equal to the size of B (notation A ā¤s B) if

there is an injective map from A to B. We say that A and B have the same size (A =s B)

if there is a bijection between A and B.

0.2.9 SchrĀØder-Bernstein Theorem

o

If A ā¤s B and B ā¤s A, then A =s B. (This can be proved without the axiom of choice.)

0.2.10

Using (0.2.9), one can show that if sets of the same size are called equivalent, then ā¤s

on equivalence classes is a partial ordering. It follows with the aid of Zornā™s lemma that

the ordering is total. The equivalence class of a set A, written |A|, is called the cardinal

number or cardinality of A. In practice, we usually identify |A| with any convenient

member of the equivalence class, such as A itself.

0.2.11

For any set A, we can always produce a set of greater cardinality, namely the power set 2A ,

that is, the collection of all subsets of A.

0.2.12

Deļ¬ne addition and multiplication of cardinal numbers by |A|+|B| = |AāŖB| and |A||B| =

|A Ć— B|. In deļ¬ning addition, we assume that A and B are disjoint. (They can always be

disjointized by replacing a ā A by (a, 0) and b ā B by (b, 1).)

0.2.13

If ā„µ0 is the cardinal number of a countably inļ¬nite set, then ā„µ0 + ā„µ0 = ā„µ0 ā„µ0 = ā„µ0 . More

generally,

(a) If Ī± and Ī² are cardinals, with Ī± ā¤ Ī² and Ī² inļ¬nite, then Ī± + Ī² = Ī².

(b) If Ī± = 0 (i.e., Ī± is nonempty), Ī± ā¤ Ī² and Ī² is inļ¬nite, then Ī±Ī² = Ī².

0.2.14

If A is an inļ¬nite set, then A and the set of all ļ¬nite subsets of A have the same cardinality.

0.3. LINEAR ALGEBRA 5

0.3 Linear Algebra

It is not feasible to list all results presented in an undergraduate course in linear algebra.

Instead, here is a list of topics that are covered in a typical course.

1. Sums, products, transposes, inverses of matrices; symmetric matrices.

2. Elementary row and column operations; reduction to echelon form.

3. Determinants: evaluation by Laplace expansion and Cramerā™s rule.

4. Vector spaces over a ļ¬eld; subspaces, linear independence and bases.

5. Rank of a matrix; homogeneous and nonhomogeneous linear equations.

6. Null space and range of a matrix; the dimension theorem.

7. Linear transformations and their representation by matrices.

8. Coordinates and matrices under change of basis.

9. Inner product spaces and the projection theorem.

10. Eigenvalues and eigenvectors; diagonalization of matrices with distinct eigenvalues,

symmetric and Hermitian matrices.

11. Quadratic forms.

A more advanced course might cover the following topics:

12. Generalized eigenvectors and the Jordan canonical form.

13. The minimal and characteristic polynomials of a matrix; Cayley-Hamilton theorem.

14. The adjoint of a linear operator.

15. Projection operators.

16. Normal operators and the spectral theorem.

Chapter 1

Group Fundamentals

1.1 Groups and Subgroups

1.1.1 Deļ¬nition

A group is a nonempty set G on which there is deļ¬ned a binary operation (a, b) ā’ ab

satisfying the following properties.

Closure: If a and b belong to G, then ab is also in G;

Associativity : a(bc) = (ab)c for all a, b, c ā G;

Identity : There is an element 1 ā G such that a1 = 1a = a for all a in G;

Inverse: If a is in G, then there is an element aā’1 in G such that aaā’1 = aā’1 a = 1.

A group G is abelian if the binary operation is commutative, i.e., ab = ba for all a, b

in G. In this case the binary operation is often written additively ((a, b) ā’ a + b), with

the identity written as 0 rather than 1.

There are some very familiar examples of abelian groups under addition, namely the

integers Z, the rationals Q, the real numbers R, the complex numers C, and the integers

Zm modulo m. Nonabelian groups will begin to appear in the next section.

The associative law generalizes to products of any ļ¬nite number of elements, for exam-

ple, (ab)(cde) = a(bcd)e. A formal proof can be given by induction. If two people A and

B form a1 Ā· Ā· Ā· an in diļ¬erent ways, the last multiplication performed by A might look like

(a1 Ā· Ā· Ā· ai )(ai+1 Ā· Ā· Ā· an ), and the last multiplication by B might be (a1 Ā· Ā· Ā· aj )(aj+1 Ā· Ā· Ā· an ).

But if (without loss of generality) i < j, then (induction hypothesis)

(a1 Ā· Ā· Ā· aj ) = (a1 Ā· Ā· Ā· ai )(ai+1 Ā· Ā· Ā· aj )

and

(ai+1 Ā· Ā· Ā· an ) = (ai+1 Ā· Ā· Ā· aj )(aj+1 Ā· Ā· Ā· an ).

By the n = 3 case, i.e., the associative law as stated in the deļ¬nition of a group, the

products computed by A and B are the same.

1

2 CHAPTER 1. GROUP FUNDAMENTALS

The identity is unique (1 = 1 1 = 1), as is the inverse of any given element (if b and b

are inverses of a, then b = 1b = (b a)b = b (ab) = b 1 = b ). Exactly the same argument

shows that if b is a right inverse, and a a left inverse, of a, then b = b .

1.1.2 Deļ¬nitions and Comments

A subgroup H of a group G is a nonempty subset of G that forms a group under the

binary operation of G. Equivalently, H is a nonempty subset of G such that if a and b

belong to H, so does abā’1 . (Note that 1 = aaā’1 ā H; also, ab = a((bā’1 )ā’1 ) ā H.)

If A is any subset of a group G, the subgroup generated by A is the smallest subgroup

containing A, often denoted by A . Formally, A is the intersection of all subgroups

containing A. More explicitly, A consists of all ļ¬nite products a1 Ā· Ā· Ā· an , n = 1, 2, . . . ,

where for each i, either ai or aā’1 belongs to A. To see this, note that all such products

i

belong to any subgroup containing A, and the collection of all such products forms a

subgroup. In checking that the inverse of an element of A also belongs to A , we use

the fact that

(a1 Ā· Ā· Ā· an )ā’1 = aā’1 Ā· Ā· Ā· aā’1

n 1

which is veriļ¬ed directly: (a1 Ā· Ā· Ā· an )(aā’1 Ā· Ā· Ā· aā’1 ) = 1.

n 1

1.1.3 Deļ¬nitions and Comments

The groups G1 and G2 are said to be isomorphic if there is a bijection f : G1 ā’ G2 that

preserves the group operation, in other words, f (ab) = f (a)f (b). Isomorphic groups are

essentially the same; they diļ¬er only notationally. Here is a simple example. A group G

is cyclic if G is generated by a single element: G = a . A ļ¬nite cyclic group generated

by a is necessarily abelian, and can be written as {1, a, a2 , . . . , anā’1 } where an = 1, or in

additive notation, {0, a, 2a, . . . , (n ā’ 1)a}, with na = 0. Thus a ļ¬nite cyclic group with

n elements is isomorphic to the additive group Zn of integers modulo n. Similarly, if G

is an inļ¬nite cyclic group generated by a, then G must be abelian and can be written as

{1, aĀ±1 , aĀ±2 , . . . }, or in additive notation as {0, Ā±a, Ā±2a, . . . }. In this case, G is isomorphic

to the additive group Z of all integers.

The order of an element a in a group G (denoted |a|) is the least positive integer n such

that an = 1; if no such integer exists, the order of a is inļ¬nite. Thus if |a| = n, then the

cyclic subgroup a generated by a has exactly n elements, and ak = 1 iļ¬ k is a multiple

of n. (Concrete examples are more illuminating than formal proofs here. Start with 0 in

the integers modulo 4, and continually add 1; the result is 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, . . . .)

The order of the group G, denoted by |G|, is simply the number of elements in G.

1.1.4 Proposition

If G is a ļ¬nite cyclic group of order n, then G has exactly one (necessarily cyclic) subgroup

of order n/d for each positive divisor d of n, and G has no other subgroups. If G is an inļ¬-

nite cyclic group, the (necessarily cyclic) subgroups of G are of the form {1, bĀ±1 , bĀ±2 , . . . },

where b is an arbitrary element of G, or, in additive notation, {0, Ā±b, Ā±2b, . . . }.

1.1. GROUPS AND SUBGROUPS 3

Proof. Again, an informal argument is helpful. Suppose that H is a subgroup of Z20 (the

integers with addition modulo 20). If the smallest positive integer in H is 6 (a non-divisor

of 20) then H contains 6, 12, 18, 4 (oops, a contradiction, 6 is supposed to be the smallest

positive integer). On the other hand, if the smallest positive integer in H is 4, then H =

{4,8,12,16,0}. Similarly, if the smallest positive integer in a subgroup H of the additive

group of integers Z is 5, then H = {0, Ā±5, Ā±10, Ā±15, Ā±20, . . . }. ā™£

If G = {1, a, . . . , anā’1 } is a cyclic group of order n, when will an element ar also have

order n? To discover the answer, letā™s work in Z12 . Does 8 have order 12? We compute

8, 16, 24 (= 0), so the order of 8 is 3. But if we try 7, we get 7, 14, 21, . . . , 77, 84 = 7 Ć— 12,

so 7 does have order 12. The point is that the least common multiple of 7 and 12 is

simply the product, while the lcm of 8 and 12 is smaller than the product. Equivalently,

the greatest common divisor of 7 and 12 is 1, while the gcd of 8 and 12 is 4 > 1. We have

the following result.

1.1.5 Proposition

If G is a cyclic group of order n generated by a, the following conditions are equivalent:

(a) |ar | = n.

(b) r and n are relatively prime.

(c) r is a unit mod n, in other words, r has an inverse mod n (an integer s such that

rs ā” 1 mod n).

Furthermore, the set Un of units mod n forms a group under multiplication. The order

of this group is Ļ•(n) = the number of positive integers less than or equal to n that are

relatively prime to n; Ļ• is the familiar Euler Ļ• function.

Proof. The equivalence of (a) and (b) follows from the discussion before the statement

of the proposition, and the equivalence of (b) and (c) is handled by a similar argument.

For example, since there are 12 distinct multiples of 7 mod 12, one of them must be 1;

speciļ¬cally, 7 Ć— 7 ā” 1 mod 12. But since 8 Ć— 3 is 0 mod 12, no multiple of 8 can be

1 mod 12. (If 8x ā” 1, multiply by 3 to reach a contradiction.) Finally, Un is a group

under multiplication because the product of two integers relatively prime to n is also

relatively prime to n. ā™£

Problems For Section 1.1

1. A semigroup is a nonempty set with a binary operation satisfying closure and asso-

ciativity (we drop the identity and inverse properties from the deļ¬nition of a group).

A monoid is a semigroup with identity (so that only the inverse property is dropped).

Give an example of a monoid that is not a group, and an example of a semigroup

that is not a monoid.

2. In Z6 , the group of integers modulo 6, ļ¬nd the order of each element.

3. List all subgroups of Z6 .

4 CHAPTER 1. GROUP FUNDAMENTALS

4. Let S be the set of all n by n matrices with real entries. Does S form a group under

matrix addition?

5. Let S ā— be the set of all nonzero n by n matrices with real entries. Does S ā— form a

group under matrix multiplication?

6. If H is a subgroup of the integers Z and H = {0}, what does H look like?

7. Give an example of an inļ¬nite group that has a nontrivial ļ¬nite subgroup (trivial

means consisting of the identity alone).

8. Let a and b belong to the group G. If ab = ba and |a| = m, |b| = n, where m and n

are relatively prime, show that |ab| = mn and that a ā© b = {1}.

9. If G is a ļ¬nite abelian group, show that G has an element g such that |g| is the least

common multiple of {|a| : a ā G}.

10. Show that a group G cannot be the union of two proper subgroups, in other words, if

G = H āŖ K where H and K are subgroups of G, then H = G or K = G. Equivalently,

if H and K are subgroups of a group G, then H āŖ K cannot be a subgroup unless

H ā K or K ā H.

11. In an arbitrary group, let a have ļ¬nite order n, and let k be a positive integer. If

(n, k) is the greatest common divisor of n and k, and [n, k] the least common multiple,

show that the order of ak is n/(n, k) = [n, k]/k.

12. Suppose that the prime factorization of the positive integer n is

n = p e1 p e 2 Ā· Ā· Ā· p er

r

12

and let Ai be the set of all positive integers m ā {1, 2, . . . , n} such that pi divides m.

Show that if |S| is the number of elements in the set S, then

n

|Ai | = ,

pi

n

|Ai ā© Aj | = for i = j,

pi pj

n

|Ai ā© Aj ā© Ak | = for i, j, k distinct,

pi p j pk

and so on.

13. Continuing Problem 12, show that the number of positive integers less than or equal

to n that are relatively prime to n is

1 1 1

Ļ•(n) = n(1 ā’ )(1 ā’ ) Ā· Ā· Ā· (1 ā’ ).

p1 p2 pr

14. Give an example of a ļ¬nite group G (of order at least 3) with the property that the

only subgroups of G are {1} and G itself.

15. Does an inļ¬nite group with the property of Problem 14 exist?

1.2. PERMUTATION GROUPS 5

1.2 Permutation Groups

1.2.1 Deļ¬nition

A permutation of a set S is a bijection on S, that is, a function Ļ : S ā’ S that is one-

to-one and onto. (If S is ļ¬nite, then Ļ is one-to-one if and only if it is onto.) If S is not

too large, it is feasible to describe a permutation by listing the elements x ā S and the

corresponding values Ļ(x). For example, if S = {1, 2, 3, 4, 5}, then

1 2 3 4 5

3 5 4 1 2

is the permutation such that Ļ(1) = 3, Ļ(2) = 5, Ļ(3) = 4, Ļ(4) = 1, Ļ(5) = 2. If we

start with any element x ā S and apply Ļ repeatedly to obtain Ļ(x), Ļ(Ļ(x)), Ļ(Ļ(Ļ(x))),

and so on, eventually we must return to x, and there are no repetitions along the way

because Ļ is one-to-one. For the above example, we obtain 1 ā’ 3 ā’ 4 ā’ 1, 2 ā’ 5 ā’ 2.

We express this result by writing

Ļ = (1, 3, 4)(2, 5)

where the cycle (1, 3, 4) is the permutation of S that maps 1 to 3, 3 to 4 and 4 to 1,

leaving the remaining elements 2 and 5 ļ¬xed. Similarly, (2, 5) maps 2 to 5, 5 to 2, 1 to 1,

3 to 3 and 4 to 4. The product of (1, 3, 4) and (2, 5) is interpreted as a composition, with

the right factor (2, 5) applied ļ¬rst, as with composition of functions. In this case, the

cycles are disjoint, so it makes no diļ¬erence which mapping is applied ļ¬rst.

The above analysis illustrates the fact that any permutation can be expressed as a

product of disjoint cycles, and the cycle decomposition is unique.

1.2.2 Deļ¬nitions and Comments

A permutation Ļ is said to be even if its cycle decomposition contains an even number

of even cycles (that is, cycles of even length); otherwise Ļ is odd. A cycle can be de-

composed further into a product of (not necessarily disjoint) two-element cycles, called

transpositions. For example,

(1, 2, 3, 4, 5) = (1, 5)(1, 4)(1, 3)(1, 2)

where the order of application of the mappings is from right to left.

Multiplication by a transposition changes the parity of a permutation (from even to

odd, or vice versa). For example,

(2, 4)(1, 2, 3, 4, 5) = (2, 3)(1, 4, 5)

(2, 6)(1, 2, 3, 4, 5) = (1, 6, 2, 3, 4, 5);

(1, 2, 3, 4, 5) has no cycles of even length, so is even; (2, 3)(1, 4, 5) and (1, 6, 2, 3, 4, 5) each

have one cycle of even length, so are odd.

Since a cycle of even length can be expressed as the product of an odd number of

transpositions, we can build an even permutation using an even number of transpositions,

6 CHAPTER 1. GROUP FUNDAMENTALS

and an odd permutation requires an odd number of transpositions. A decomposition into

transpositions is not unique; for example, (1, 2, 3, 4, 5) = (1, 4)(1, 5)(1, 4)(1, 3)(1, 2)(3, 5),

but as mentioned above, the cycle decomposition is unique. Since multiplication by a

transposition changes the parity, it follows that if a permutation is expressed in two

diļ¬erent ways as a product of transpositions, the number of transpositions will agree in

parity (both even or both odd).

Consequently, the product of two even permutations is even; the product of two odd

permutations is even; and the product of an even and an odd permutation is odd. To

summarize very compactly, deļ¬ne the sign of the permutation Ļ as

+1 if Ļ is even

sgn(Ļ) =

ā’1 if Ļ is odd

Then for arbitrary permutations Ļ1 and Ļ2 we have

sgn(Ļ1 Ļ2 ) = sgn(Ļ1 ) sgn(Ļ2 ).

1.2.3 Deļ¬nitions and Comments

There are several permutation groups that are of major interest. The set Sn of all per-

mutations of {1, 2, . . . , n} is called the symmetric group on n letters, and its subgroup An

of all even permutations of {1, 2, . . . , n} is called the alternating group on n letters. (The

group operation is composition of functions.) Since there are as many even permutations

as odd ones (any transposition, when applied to the members of Sn , produces a one-to-one

correspondence between even and odd permutations), it follows that An is half the size

of Sn . Denoting the size of the set S by |S|, we have

|Sn | = n!, |An | = 1 n!

2

We now deļ¬ne and discuss informally D2n , the dihedral group of order 2n. Consider

a regular polygon with center O and vertices V1 , V2 , . . . , Vn , arranged so that as we move

counterclockwise around the ļ¬gure, we encounter V1 , V2 , . . . in turn. To eliminate some of

the abstraction, letā™s work with a regular pentagon with vertices A, B, C, D, E, as shown

in Figure 1.2.1.

n C yyyy

nnn yyy

n

nnn yyy

nnn yyy

nnn y

Dd O B

dd ˜˜

dd ˜˜

dd ˜˜

˜

E A

Figure 1.2.1

The group D10 consists of the symmetries of the pentagon, i.e., those permutations

that can be realized via a rigid motion (a combination of rotations and reļ¬‚ections). All

symmetries can be generated by two basic operations R and F :

1.2. PERMUTATION GROUPS 7

R is counterclockwise rotation by 360 = 360 = 72 degrees,

5

n

F (āļ¬‚ipā) is reļ¬‚ection about the line joining the center O to the ļ¬rst vertex (A in this

case).

The group D2n contains 2n elements, namely, I (the identity), R, R2 , . . . , Rnā’1 , F ,

RF , R2 F , . . . , Rnā’1 F (RF means F followed by R). For example, in the case of the

pentagon, F = (B, E)(C, D) and R = (A, B, C, D, E), so RF = (A, B)(C, E), which is

the reļ¬‚ection about the line joining O to D; note that RF can also be expressed as F Rā’1 .

In visualizing the eļ¬ect of a permutation such as F , interpret F ā™s taking B to E as vertex

B moving to where vertex E was previously.

D2n will contain exactly n rotations I, R, . . . , Rnā’1 and n reļ¬‚ections F, RF, . . . , Rnā’1 F .

If n is odd, each reļ¬‚ection is determined by a line joining the center to a vertex (and pass-

ing through the midpoint of the opposite side). If n is even, half the reļ¬‚ections are

determined by a line passing through two vertices (as well as the center), and the other

half by a line passing through the midpoints of two opposite sides (as well as the center).

1.2.4 An Abstract Characterization of the Dihedral Group

Consider the free group with generators R and F , in other words all ļ¬nite sequences whose

components are R, Rā’1 , F and F ā’1 . The group operation is concatenation, subject to

the constraint that if a symbol and its inverse occur consecutively, they may be can-

celled. For example, RF F F F ā’1 RF Rā’1 RF F is identiļ¬ed with RF F RF F F , also written

as RF 2 RF 3 . If we add further restrictions (so the group is no longer āfreeā), we can

obtain D2n . Speciļ¬cally, D2n is the group deļ¬ned by generators R and F , subject to the

relations

RF = F Rā’1 .

F 2 = I,

Rn = I,

The relations guarantee that there are only 2n distinct group elements I, R, . . . , Rnā’1 and

F, RF, . . . , Rnā’1 F . For example, with n = 5 we have

F 2 R2 F = F F RRF = F F RF Rā’1 = F F F Rā’1 Rā’1 = F Rā’2 = F R3 ;

also, R cannot be the same as R2 F , since this would imply that I = RF , or F = Rā’1 =

R4 , and there is no way to get this using the relations. Since the product of two group

elements is completely determined by the deļ¬ning relations, it follows that there cannot

be more than one group with the given generators and relations. (This statement is true

āup to isomorphismā; it is always possible to create lots of isomorphic copies of any given

group.) The symmetries of the regular n-gon provide a concrete realization.

Later we will look at more systematic methods of analyzing groups deļ¬ned by gener-

ators and relations.

Problems For Section 1.2

1. Find the cycle decomposition of the permutation

1 2 3 4 5 6

4 6 3 1 2 5

and determine whether the permutation is even or odd.

8 CHAPTER 1. GROUP FUNDAMENTALS

2. Consider the dihedral group D8 as a group of permutations of the square. Assume that

as we move counterclockwise around the square, we encounter the vertices A, B, C, D

in turn. List all the elements of D8 .

3. In S5 , how many 5-cycles are there; that is, how many permutations are there with

the same cycle structure as (1, 2, 3, 4, 5)?

4. In S5 , how many permutations are products of two disjoint transpositions, such as

(1, 2)(3, 4)?

5. Show that if n ā„ 3, then Sn is not abelian.

6. Show that the products of two disjoint transpositions in S4 , together with the identity,

form an abelian subgroup V of S4 . Describe the multiplication table of V (known as

the four group).

7. Show that the cycle structure of the inverse of a permutation Ļ coincides with that

of Ļ. In particular, the inverse of an even permutation is even (and the inverse of an

odd permutation is odd), so that An is actually a group.

8. Find the number of 3-cycles, i.e., permutations consisting of exactly one cycle of

length 3, in S4 .

9. Suppose H is a subgroup of A4 with the property that for every permutation Ļ in A4 ,

Ļ 2 belongs to H. Show that H contains all 3-cycles in A4 . (Since 3-cycles are even,

H in fact contains all 3-cycles in S4 .)

10. Consider the permutation

1 2 3 4 5

Ļ= .

2 4 5 1 3

Count the number of inversions of Ļ, that is, the number of pairs of integers that are

out of their natural order in the second row of Ļ. For example, 2 and 5 are in natural

order, but 4 and 3 are not. Compare your result with the parity of Ļ.

11. Show that the parity of any permutation Ļ is the same as the parity of the number

of inversions of Ļ.

1.3 Cosets, Normal Subgroups, and Homomorphisms

1.3.1 Deļ¬nitions and Comments

Let H be a subgroup of the group G. If g ā G, the right coset of H generated by g is

Hg = {hg : h ā H};

similarly, the left coset of H generated by g is

gH = {gh : h ā H}.

It follows (Problem 1) that if a, b ā G, then

if and only if abā’1 ā H

Ha = Hb

1.3. COSETS, NORMAL SUBGROUPS, AND HOMOMORPHISMS 9

and

if and only if aā’1 b ā H.

aH = bH

Thus if we deļ¬ne a and b to be equivalent iļ¬ abā’1 ā H, we have an equivalence relation

(Problem 2), and (Problem 3) the equivalence class of a is

{b : abā’1 ā H} = Ha.

Therefore the right cosets partition G (similarly for the left cosets). Since h ā’ ha,

h ā H, is a one-to-one correspondence, each coset has |H| elements. There are as many

right cosets as left cosets, since the map aH ā’ Haā’1 is a one-to-one correspondence

(Problem 4). If [G : H], the index of H in G, denotes the number of right (or left) cosets,

we have the following basic result.

1.3.2 Lagrangeā™s Theorem

If H is a subgroup of G, then |G| = |H|[G : H]. In particular, if G is ļ¬nite then |H|

divides |G|, and

|G|

= [G : H].

|H|

Proof. There are [G : H] cosets, each with |H| members. ā™£

1.3.3 Corollary

Let G be a ļ¬nite group.

(i) If a ā G then |a| divides |G|; in particular, a|G| = 1. Thus |G| is a multiple of the

order of each of its elements, so if we deļ¬ne the exponent of G to be the least common

multiple of {|a| : a ā G}, then |G| is a multiple of the exponent.

(ii) If G has prime order, then G is cyclic.

Proof. If the element a ā G has order n, then H = {1, a, a2 , . . . , anā’1 } is a cyclic subgroup

of G with |H| = n. By Lagrangeā™s theorem, n divides |G|, proving (i). If |G| is prime

then we may take a = 1, and consequently n = |G|. Thus H is a subgroup with as many

elements as G, so in fact H and G coincide, proving (ii). ā™£

Here is another corollary.

1.3.4 Eulerā™s Theorem

If a and n are relatively prime positive integers, with n ā„ 2, then aĻ•(n) ā” 1 mod n. A

special case is Fermatā™s Little Theorem: If p is a prime and a is a positive integer not

divisible by p, then apā’1 ā” 1 mod p.

Proof. The group of units mod n has order Ļ•(n), and the result follows from (1.3.3). ā™£

We will often use the notation H ā¤ G to indicate that H is a subgroup of G. If H is

a proper subgroup, i.e., H ā¤ G but H = G, we write H < G.

10 CHAPTER 1. GROUP FUNDAMENTALS

1.3.5 The Index is Multiplicative

If K ā¤ H ā¤ G, then [G : K] = [G : H][H : K].

Proof. Choose representatives ai from each left coset of H in G, and representatives bj

from each left coset of K in H. If cK is any left coset of K in G, then c ā ai H for some

unique i, and if c = ai h, h ā H, then h ā bj K for some unique j, so that c belongs to

ai bj K. The map (ai , bj ) ā’ ai bj K is therefore onto, and it is one-to-one by the uniqueness

of i and j. We therefore have a bijection between a set of size [G : H][H : K] and a set

of size [G : K], as asserted. ā™£

Now suppose that H and K are subgroups of G, and deļ¬ne HK to be the set of all

products hk, h ā H, k ā K. Note that HK need not be a group, since h1 k1 h2 k2 is not

necessarily equal to h1 h2 k1 k2 . If G is abelian, then HK will be a group, and we have the

following useful generalization of this observation.

1.3.6 Proposition

If H ā¤ G and K ā¤ G, then HK ā¤ G if and only if HK = KH. In this case, HK is the

subgroup generated by H āŖ K.

Proof. If HK is a subgroup, then (HK)ā’1 , the collection of all inverses of elements of HK,

must coincide with HK. But (HK)ā’1 = K ā’1 H ā’1 = KH. Conversely, if HK = KH,

then the inverse of an element in HK also belongs to HK, because (HK)ā’1 = K ā’1 H ā’1 =

KH = HK. The product of two elements in HK belongs to HK, because (HK)(HK) =

HKHK = HHKK = HK. The last statement follows from the observation that any

subgroup containing H and K must contain HK. ā™£

The set product HK deļ¬ned above suggests a multiplication operation on cosets. If

H is a subgroup of G, we can multiply aH and bH, and it is natural to hope that we get

abH. This does not always happen, but here is one possible criterion.

1.3.7 Lemma

If H ā¤ G, then (aH)(bH) = abH for all a, b ā G iļ¬ cHcā’1 = H for all c ā G. (Equiva-

lently, cH = Hc for all c ā G.

Proof. If the second condition is satisļ¬ed, then (aH)(bH) = a(Hb)H = abHH = abH.

Conversely, if the ļ¬rst condition holds, then cHcā’1 ā cHcā’1 H since 1 ā H, and

(cH)(cā’1 H) = ccā’1 H(= H) by hypothesis. Thus cHcā’1 ā H, which implies that

H ā cā’1 Hc. Since this holds for all c ā G, we have H ā cHcā’1 , and the result fol-

lows. ā™£

Notice that we have proved that if cHcā’1 ā H for all c ā G, then in fact cHcā’1 = H

for all c ā G.

1.3. COSETS, NORMAL SUBGROUPS, AND HOMOMORPHISMS 11

1.3.8 Deļ¬nition

Let H be a subgroup of G. If any of the following equivalent conditions holds, we say

that H is a normal subgroup of G, or that H is normal in G:

(1) cHcā’1 ā H for all c ā G (equivalently, cā’1 Hc ā H for all c ā G).

(2) cHcā’1 = H for all c ā G (equivalently, cā’1 Hc = H for all c ā G).

(3) cH = Hc for all c ā G.

(4) Every left coset of H in G is also a right coset.

(5) Every right coset of H in G is also a left coset.

We have established the equivalence of (1), (2) and (3) above, and (3) immediately

implies (4). To show that (4) implies (3), suppose that cH = Hd. Then since c belongs

to both cH and Hc, i.e., to both Hd and Hc, we must have Hd = Hc because right

cosets partition G, so that any two right cosets must be either disjoint or identical. The

equivalence of (5) is proved by a symmetrical argument.

Notation: H G indicates that H is a normal subgroup of G; if H is a proper

normal subgroup, we write H G.

1.3.9 Deļ¬nition of the Quotient Group

If H is normal in G, we may deļ¬ne a group multiplication on cosets, as follows. If aH

and bH are (left) cosets, let

(aH)(bH) = abH;

by (1.3.7), (aH)(bH) is simply the set product. If a1 is another member of aH and b1

another member of bH, then a1 H = aH and b1 H = bH (Problem 5). Therefore the set

product of a1 H and b1 H is also abH. The point is that the product of two cosets does

not depend on which representatives we select.

To verify that cosets form a group under the above multiplication, we consider the

four deļ¬ning requirements.

Closure: The product of two cosets is a coset.

Associativity : This follows because multiplication in G is associative.

Identity : The coset 1H = H serves as the identity.

Inverse: The inverse of aH is aā’1 H.

The group of cosets of a normal subgroup N of G is called the quotient group of G

by N ; it is denoted by G/N .

Since the identity in G/N is 1N = N , we have, intuitively, āset everything in N equal

to 1ā.

12 CHAPTER 1. GROUP FUNDAMENTALS

1.3.10 Example

Let GL(n, R be the set of all nonsingular n by n matrices with real coeļ¬cients, and let

SL(n, R) be the subgroup formed by matrices whose determinant is 1 (GL stands for

āgeneral linearā and SL for āspecial linearā). Then SL(n, R) GL(n, R), because if A is

a nonsingular n by n matrix and B is n by n with determinant 1, then det(ABAā’1 ) =

det A det B det Aā’1 = det B = 1.

1.3.11 Deļ¬nition

If f : G ā’ H, where G and H are groups, then f is said to be a homomorphism if for all

a, b in G, we have

f (ab) = f (a)f (b).

This idea will look familiar if G and H are abelian, in which case, using additive notation,

we write

f (a + b) = f (a) + f (b);

thus a linear transformation on a vector space is, in particular, a homomorphism on the

underlying abelian group. If f is a homomorphism from G to H, it must map the identity

of G to the identity of H, since f (a) = f (a1G ) = f (a)f (1G ); multiply by f (a)ā’1 to get

1H = f (1G ). Furthermore, the inverse of f (a) is f (aā’1 ), because

1 = f (aaā’1 ) = f (a)f (aā’1 ),

so that [f (a)]ā’1 = f (aā’1 ).

1.3.12 The Connection Between Homomorphisms and Normal

Subgroups

If f : G ā’ H is a homomorphism, deļ¬ne the kernel of f as

ker f = {a ā G : f (a) = 1};

then ker f is a normal subgroup of G. For if a ā G and b ā ker f , we must show that

abaā’1 belongs to ker f . But f (abaā’1 ) = f (a)f (b)f (aā’1 ) = f (a)(1)f (a)ā’1 = 1.

Conversely, every normal subgroup is the kernel of a homomorphism. To see this,

suppose that N G, and let H be the quotient group G/N . Deļ¬ne the map Ļ : G ā’ G/N

by Ļ(a) = aN ; Ļ is called the natural or canonical map. Since

Ļ(ab) = abN = (aN )(bN ) = Ļ(a)Ļ(b),

Ļ is a homomorphism. The kernel of Ļ is the set of all a ā G such that aN = N (= 1N ),

or equivalently, a ā N . Thus ker Ļ = N .

1.3. COSETS, NORMAL SUBGROUPS, AND HOMOMORPHISMS 13

1.3.13 Proposition

A homomorphism f is injective if and only if its kernel K is trivial, that is, consists only

of the identity.

Proof. If f is injective and a ā K, then f (a) = 1 = f (1), hence a = 1. Conversely, if K is

trivial and f (a) = f (b), then f (abā’1 ) = f (a)f (bā’1 ) = f (a)[f (b)]ā’1 = f (a)[f (a)]ā’1 = 1,

so abā’1 ā K. Thus abā’1 = 1, i.e., a = b, proving f injective. ā™£

1.3.14 Some Standard Terminology

A monomorphism is an injective homomorphism

An epimorphism is a surjective homomorphism

An isomorphism is a bijective homomorphism

An endomorphism is a homomorphism of a group to itself

An automorphism is an isomorphism of a group with itself

We close the section with a result that is applied frequently.

1.3.15 Proposition

Let f : G ā’ H be a homomorphism.

(i) If K is a subgroup of G, then f (K) is a subgroup of H. If f is an epimorphism

and K is normal, then f (K) is also normal.

(ii) If K is a subgroup of H, then f ā’1 (K) is a subgroup of G. If K is normal, so is

f ā’1 (K).

Proof. (i) If f (a) and f (b) belong to f (K), so does f (a)f (b)ā’1 , since this element coin-

cides with f (abā’1 ). If K is normal and c ā G, we have f (c)f (K)f (c)ā’1 = f (cKcā’1 ) =

f (K), so if f is surjective, then f (K) is normal.

(ii) If a and b belong to f ā’1 (K), so does abā’1 , because f (abā’1 ) = f (a)f (b)ā’1 , which

belongs to K. If c ā G and a ā f ā’1 (K) then f (cacā’1 ) = f (c)f (a)f (c)ā’1 , so if K is

normal, we have cacā’1 ā f ā’1 (K), proving f ā’1 (K) normal. ā™£

Problems For Section 1.3

In Problems 1ā“6, H is a subgroup of the group G, and a and b are elements of G.

1. Show that Ha = Hb iļ¬ abā’1 ā H.

2. Show that āa ā¼ b iļ¬ abā’1 ā Hā deļ¬nes an equivalence relation.

3. If we deļ¬ne a and b to be equivalent iļ¬ abā’1 ā H, show that the equivalence class

of a is Ha.

4. Show that aH ā’ Haā’1 is a one-to-one correspondence between left and right cosets

of H.

14 CHAPTER 1. GROUP FUNDAMENTALS

5. If aH is a left coset of H in G and a1 ā aH, show that the left coset of H generated

by a1 (i.e., a1 H), is also aH.

6. If [G : H] = 2, show that H is a normal subgroup of G.

7. Let S3 be the group of all permutations of {1, 2, 3}, and take a to be permutation

(1, 2, 3), b the permutation (1, 2), and e the identity permutation. Show that the

elements of S3 are, explicitly, e, a, a2 , b, ab and a2 b.

8. Let H be the subgroup of S3 consisting of the identity e and the permutation b = (1, 2).

Compute the left cosets and the right cosets of H in S3 .

9. Continuing Problem 8, show that H is not a normal subgroup of S3 .

10. Let f be an endomorphism of the integers Z. Show that f is completely determined

by its action on 1. If f (1) = r, then f is multiplication by r; in other words, f (n) = rn

for every integer n.

11. If f is an automorphism of Z, and I is the identity function on Z, show that f is

either I or ā’I.

12. Since the composition of two automorphisms is an automorphism, and the inverse of

an automorphism is an automorphism, it follows that the set of automorphisms of a

group is a group under composition. In view of Problem 11, give a simple description

of the group of automorphisms of Z.

13. Let H and K be subgroups of the group G. If x, y ā G, deļ¬ne x ā¼ y iļ¬ x can be

written as hyk for some h ā H and k ā K. Show that ā¼ is an equivalence relation.

14. The equivalence class of x ā G is HxK = {hxk : h ā H, k ā K}, called a double coset

associated with the subgroups H and K. Thus the double cosets partition G. Show

that any double coset can be written as a union of right cosets of H, or equally well

as a union of left cosets of K.

1.4 The Isomorphism Theorems

Suppose that N is a normal subgroup of G, f is a homomorphism from G to H, and Ļ is

the natural map from G to G/N , as pictured in Figure 1.4.1.

GH

f

G

za

z

z

Ļ

z f

G/N

Figure 1.4.1

We would like to ļ¬nd a homomorphism f : G/N ā’ H that makes the diagram com-

mutative. Commutativity means that we get the same result by traveling directly from G

to H via f as we do by taking the roundabout route via Ļ followed by f . This requirement

translates to f (aN ) = f (a). Here is the key result for ļ¬nding such an f .

1.4. THE ISOMORPHISM THEOREMS 15

1.4.1 Factor Theorem

Any homomorphism f whose kernel K contains N can be factored through G/N . In other

words, in Figure 1.4.1 there is a unique homomorphism f : G/N ā’ H such that f ā—¦ Ļ = f .

Furthermore:

(i) f is an epimorphism if and only if f is an epimorphism;

(ii) f is a monomorphism if and only if K = N ;

(iii) f is an isomorphism if and only if f is an epimorphism and K = N .

Proof. If the diagram is to commute, then f (aN ) must be f (a), and it follows that f , if

it exists, is unique. The deļ¬nition of f that we have just given makes sense, because if

aN = bN , then aā’1 b ā N ā K, so f (aā’1 b) = 1, and therefore f (a) = f (b). Since

f (aN bN ) = f (abN ) = f (ab) = f (a)f (b) = f (aN )f (bN ),

f is a homomorphism. By construction, f has the same image as f , proving (i). Now the

kernel of f is

{aN : f (a) = 1} = {aN : a ā K} = K/N.

By (1.3.13), a homomorphism is injective, i.e., a monomorphism, if and only if its kernel

is trivial. Thus f is a monomorphism if and only if K/N consists only of the identity

element N . This means that if a is any element of K, then the coset aN coincides with

N , which forces a to belong to N . Thus f is a monomorphism if and only if K = N ,

proving (ii). Finally, (iii) follows immediately from (i) and (ii). ā™£

The factor theorem yields a fundamental result.

1.4.2 First Isomorphism Theorem

If f : G ā’ H is a homomorphism with kernel K, then the image of f is isomorphic

to G/K.

Proof. Apply the factor theorem with N = K, and note that f must be an epimorphism

of G onto its image. ā™£

If we are studying a subgroup K of a group G, or perhaps the quotient group G/K,

we might try to construct a homomorphism f whose kernel is K and whose image H has

desirable properties. The ļ¬rst isomorphism theorem then gives G/K ā¼ H (where ā¼ is

= =

our symbol for isomorphism). If we know something about H, we may get some insight

into K and G/K.

We will prove several other isomorphism theorems after the following preliminary

result.

16 CHAPTER 1. GROUP FUNDAMENTALS

1.4.3 Lemma

Let H and N be subgroups of G, with N normal in G. Then:

(i) HN = N H, and therefore by (1.3.6), HN is a subgroup of G.

(ii) N is a normal subgroup of HN .

(iii) H ā© N is a normal subgroup of H.

Proof. (i) We have hN = N h for every h ā G, in particular for every h ā H.

(ii) Since N is normal in G, it must be normal in the subgroup HN .

(iii) H ā© N is the kernel of the canonical map Ļ : G ā’ G/N , restricted to H. ā™£

The subgroups we are discussing are related by a āparallelogramā or ādiamondā, as

Figure 1.4.2 suggests.

HN q

ww qq

ww qq

ww qq

ww

w

H qq N

w

qq ww

qq ww

qq ww

q ww

H ā©N

Figure 1.4.2

1.4.4 Second Isomorphism Theorem

If H and N are subgroups of G, with N normal in G, then

H/(H ā© N ) ā¼ HN/N.

=

Note that we write HN/N rather than H/N , since N need not be a subgroup of H.

Proof. Let Ļ be the canonical epimorphism from G to G/N , and let Ļ0 be the restriction

of Ļ to H. Then the kernel of Ļ0 is H ā©N , so by the ļ¬rst isomorphism theorem, H/(H ā©N )

is isomorphic to the image of Ļ0 , which is {hN : h ā H} = HN/N . (To justify the last

equality, note that for any n ā N we have hnN = hN ). ā™£

1.4.5 Third Isomorphism Theorem

If N and H are normal subgroups of G, with N contained in H, then

G/H ā¼ (G/N )/(H/N ),

=

a ācancellation lawā.

1.4. THE ISOMORPHISM THEOREMS 17

Proof. This will follow directly from the ļ¬rst isomorphism theorem if we can ļ¬nd an

epimorphism of G/N onto G/H with kernel H/N , and there is a natural candidate:

f (aN ) = aH. To check that f is well-deļ¬ned, note that if aN = bN then aā’1 b ā N ā H,

so aH = bH. Since a is an arbitrary element of G, f is surjective, and by deļ¬nition of

coset multiplication, f is a homomorphism. But the kernel of f is

{aN : aH = H} = {aN : a ā H} = H/N. ā™£

Now suppose that N is a normal subgroup of G. If H is a subgroup of G containing

N , there is a natural analog of H in the quotient group G/N , namely, the subgroup H/N .

In fact we can make this correspondence very precise. Let

Ļ(H) = H/N

be a map from the set of subgroups of G containing N to the set of subgroups of G/N .

We claim that Ļ is a bijection. For if H1 /N = H2 /N then for any h1 ā H1 , we have

h1 N = h2 N for some h2 ā H2 , so that hā’1 h1 ā N , which is contained in H2 . Thus

2

H1 ā H2 , and by symmetry the reverse inclusion holds, so that H1 = H2 and Ļ is

injective. Now if Q is a subgroup of G/N and Ļ : G ā’ G/N is canonical, then

Ļ ā’1 (Q) = {a ā G : aN ā Q},

a subgroup of G containing N , and

Ļ(Ļ ā’1 (Q)) = {aN : aN ā Q} = Q,

proving Ļ surjective.

The map Ļ has a number of other interesting properties, summarized in the following

result, sometimes referred to as the fourth isomorphism theorem.

1.4.6 Correspondence Theorem

If N is a normal subgroup of G, then the map Ļ : H ā’ H/N sets up a one-to-one

correspondence between subgroups of G containing N and subgroups of G/N . The inverse

of Ļ is the map Ļ„ : Q ā’ Ļ ā’1 (Q), where Ļ is the canonical epimorphism of G onto G/N .

Furthermore:

(i) H1 ā¤ H2 if and only if H1 /N ā¤ H2 /N , and, in this case,

[H2 : H1 ] = [H2 /N : H1 /N ].

(ii) H is a normal subgroup of G if and only if H/N is a normal subgroup of G/N .

More generally,

(iii) H1 is a normal subgroup of H2 if and only if H1 /N is a normal subgroup of H2 /N ,

and in this case, H2 /H1 ā¼ (H2 /N )/H1 /N ).

=

18 CHAPTER 1. GROUP FUNDAMENTALS

Proof. We have established that Ļ is a bijection with inverse Ļ„ . If H1 ā¤ H2 , we have

H1 /N ā¤ H2 /N immediately, and the converse follows from the above proof that Ļ is

injective. To prove the last statement of (i), let Ī· map the left coset aH1 , a ā H2 , to the

left coset (aN )(H1 /N ). Then Ī· is a well-deļ¬ned injective map because

aā’1 b ā H1

aH1 = bH1 iļ¬

iļ¬ (aN )ā’1 (bN ) = aā’1 bN ā H1 /N

iļ¬ (aN )(H1 /N ) = (bN )(H1 /N );

Ī· is surjective because a ranges over all of H2 .

To prove (ii), assume that H G; then for any a ā G we have

(aN )(H/N )(aN )ā’1 = (aHaā’1 )/N = H/N

so that H/N G/N . Conversely, suppose that H/N is normal in G/N . Consider the

homomorphism a ā’ (aN )(H/N ), the composition of the canonical map of G onto G/N

and the canonical map of G/N onto (G/N )/(H/N ). The element a will belong to the

kernel of this map if and only if (aN )(H/N ) = H/N , which happens if and only if

aN ā H/N , that is, aN = hN for some h ā H. But since N is contained in H, this

statement is equivalent to a ā H. Thus H is the kernel of a homomorphism, and is

therefore a normal subgroup of G.

Finally, the proof of (ii) also establishes the ļ¬rst part of (iii); just replace H by H1

and G by H2 . The second part of (iii) follows from the third isomorphism theorem (with

the same replacement). ā™£

We conclude the section with a useful technical result.

1.4.7 Proposition

If H is a subgroup of G and N is a normal subgroup of G, we know by (1.4.3) that HN ,

the subgroup generated by H āŖ N , is a subgroup of G. If H is also a normal subgroup

of G, then HN is normal in G as well. More generally, if for each i in the index set I, we

have Hi G, then Hi , i ā I , the subgroup generated by the Hi (technically, by the set

āŖiāI Hi ) is a normal subgroup of G.

Proof. A typical element in the subgroup generated by the Hi is a = a1 a2 Ā· Ā· Ā· an where ak

belongs to Hik . If g ā G then

g(a1 a2 Ā· Ā· Ā· an )g ā’1 = (ga1 g ā’1 )(ga2 g ā’1 ) Ā· Ā· Ā· (gan g ā’1 )

and gak g ā’1 ā Hik because Hik G. Thus gag ā’1 belongs to Hi , i ā I . ā™£

Problems For Section 1.4

1. Let Z be the integers, and nZ the set of integer multiples of n. Show that Z/nZ

is isomorphic to Zn , the additive group of integers modulo n. (This is not quite a

tautology if we view Zn concretely as the set {0, 1, . . . , nā’1}, with sums and diļ¬erences

reduced modulo n.)

1.5. DIRECT PRODUCTS 19

2. If m divides n then Zm ā¤ Zn ; for example, we can identify Z4 with the subgroup

{0, 3, 6, 9} of Z12 . Show that Zn /Zm ā¼ Zn/m .

=

3. Let a be an element of the group G, and let fa : G ā’ G be āconjugation by aā, that

is, fa (x) = axaā’1 , x ā G. Show that fa is an automorphism of G.

4. An inner automorphism of G is an automorphism of the form fa (deļ¬ned in Prob-

lem 3) for some a ā G. Show that the inner automorphisms of G form a group under

composition of functions (a subgroup of the group of all automorphisms of G).

5. Let Z(G) be the center of G, that is, the set of all x in G such that xy = yx for all y

in G. Thus Z(G) is the set of elements that commute with everything in G. Show that

Z(G) is a normal subgroup of G, and that the group of inner automorphisms of G is

isomorphic to G/Z(G).

6. If f is an automorphism of Zn , show that f is multiplication by m for some m relatively

prime to n. Conclude that the group of automorphisms of Zn can be identiļ¬ed with

the group of units mod n.

7. The diamond diagram associated with the second isomorphism theorem (1.4.4) illus-

trates least upper bounds and greatest lower bounds in a lattice. Verify that HN is the

smallest subgroup of G containing both H and N , and H ā© N is the largest subgroup

of G contained in both H and N .

8. Let g be an automorphism of the group G, and fa an inner automorphism, as deļ¬ned

in Problems 3 and 4. Show that g ā—¦ fa ā—¦ g ā’1 is an inner automorphism. Thus the group

of inner automorphisms of G is a normal subgroup of the group of all automorphisms.

9. Identify a large class of groups for which the only inner automorphism is the identity

mapping.

1.5 Direct Products

1.5.1 External and Internal Direct Products

In this section we examine a popular construction. Starting with a given collection of

groups, we build a new group with the aid of the cartesian product. Letā™s start with

two given groups H and K, and let G = H Ć— K, the set of all ordered pairs (h, k),

h ā H, k ā K. We deļ¬ne multiplication on G componentwise:

(h1 , k1 )(h2 , k2 ) = (h1 h2 , k1 k2 ).

Since (h1 h2 , k1 k2 ) belongs to G, it follows that G is closed under multiplication. The

multiplication operation is associative because the individual products on H and K are

associative. The identity element in G is (1H , 1K ), and the inverse of (h, k) is (hā’1 , k ā’1 ).

Thus G is a group, called the external direct product of H and K.

We may regard H and K as subgroups of G. More precisely, G contains isomorphic

copies of H and K, namely

H = {(h, 1K ) : h ā H} and K = {(1H , k) : k ā K}.

20 CHAPTER 1. GROUP FUNDAMENTALS

Furthermore, H and K are normal subgroups of G. (Note that (h, k)(h1 , 1K )(hā’1 , k ā’1 ) =

(hh1 hā’1 , 1K ), with hh1 hā’1 ā H.) Also, from the deļ¬nitions of H and K, we have

G = H K and H ā© K = {1}, where 1 = (1H , 1K ).

If a group G contains normal subgroups H and K such that G = HK and H ā©K = {1},

we say that G is the internal direct product of H and K.

Notice the key diļ¬erence between external and internal direct products. We construct

the external direct product from the component groups H and K. On the other hand,

starting with a given group we discover subgroups H and K such that G is the inter-

nal direct product of H and K. Having said this, we must admit that in practice the

distinction tends to be blurred, because of the following result.

1.5.2 Proposition

If G is the internal direct product of H and K, then G is isomorphic to the external direct

product H Ć— K.

Proof. Deļ¬ne f : H Ć— K ā’ G by f (h, k) = hk; we will show that f is an isomorphism.

First note that if h ā H and k ā K then hk = kh. (Consider hkhā’1 k ā’1 , which belongs

to K since hkhā’1 ā K, and also belongs to H since khā’1 k ā’1 ā H; thus hkhā’1 k ā’1 = 1,

so hk = kh.)

(a) f is a homomorphism, since

f ((h1 , k1 )(h2 , k2 )) = f (h1 h2 , k1 k2 ) = h1 h2 k1 k2 = (h1 k1 )(h2 k2 ) = f (h1 , k1 )f (h2 , k2 ).

(b) f is surjective, since by deļ¬nition of internal direct product, G = HK.

(c) f is injective, for if f (h, k) = 1 then hk = 1, so that h = k ā’1 .Thus h belongs

to both H and K, so by deļ¬nition of internal direct product, h is the identity, and

consequently so is k. The kernel of f is therefore trivial. ā™£

External and internal direct products may be deļ¬ned for any number of factors. We

will restrict ourselves to a ļ¬nite number of component groups, but the generalization to

arbitrary cartesian products with componentwise multiplication is straightforward.

1.5.3 Deļ¬nitions and Comments

If H1 , H2 , . . . Hn are arbitrary groups, the external direct product of the Hi is the cartesian

product G = H1 Ć— H2 Ć— Ā· Ā· Ā· Ć— Hn , with componentwise multiplication:

(h1 , h2 , . . . , hn )(h1 , h2 , . . . hn ) = (h1 h1 , h2 h2 , . . . hn hn );

G contains an isomorphic copy of each Hi , namely

H i = {(1H1 , . . . , 1Hiā’1 , hi , 1Hi+1 , . . . , 1Hn ) : hi ā Hi }.

As in the case of two factors, G = H 1 H 2 Ā· Ā· Ā· H n , and H i G for all i; furthermore, if

g ā G then g has a unique representation of the form

g = h1 h2 Ā· Ā· Ā· hn where hi ā H i .

1.5. DIRECT PRODUCTS 21

Speciļ¬cally, g = (h1 , . . . , hn ) = (h1 , 1, . . . , 1) . . . (1, . . . , 1, hn ). The representation is

unique because the only way to produce the i-th component hi of g is for hi to be the ith

component of the factor from H i . If a group G contains normal subgroups H1 , . . . , Hn

such that G = H1 Ā· Ā· Ā· Hn , and each g ā G can be uniquely represented as h1 Ā· Ā· Ā· hn with

hi ā Hi , i = 1, 2, . . . , n, we say that G is the internal direct product of the Hi . As in the

case of two factors, if G is the internal direct product of the Hi , then G is isomorphic

to the external direct product H1 Ć— Ā· Ā· Ā· Ć— Hn ; the isomorphism f : H1 Ć— Ā· Ā· Ā· Ć— Hn ā’ G

is given by f (h1 , . . . , hn ) = h1 Ā· Ā· Ā· hn . The next result frequently allows us to recognize

when a group is an internal direct product.

1.5.4 Proposition

Suppose that G = H1 Ā· Ā· Ā· Hn , where each Hi is a normal subgroup of G. The following

conditions are equivalent:

(1) G is the internal direct product of the Hi .

j=i Hj = {1} for i = 1, . . . , n; thus it does not matter in which order the Hi

(2) Hi

are listed.

iā’1

Hj = {1} for i = 1, . . . , n.

(3) Hi j=1

Proof. (1) implies (2): If g belongs to the product of the Hj , j = i, then g can be written

ńņš. 1 |