Chapter 2

Groups

Wherever groups disclose themselves, or could be introduced, simplicity crystallizes out of complete chaos.

—Eric Temple Bell

The origin of the modern theory of groups lies in the theory of equations. By the beginning of the nineteenth century, mathematicians had developed formulas for finding the roots of any cubic or quartic equation (analogous to the quadratic formula), and the best mathematicians of the day were trying to find such a formula for the quintic. It thus came as a great surprise when, in 1824, Niels Henrik Abel proved that no such formula exists. At about the same time, Evariste Galois showed that any equation of degree n has an associated group of permutations of the roots of the equation (that is, a set of permutations closed under compositions and inverses). He proved that the equation is solvable if and only if this group has a certain property (now called a solvable group). In particular, the fact that the group A_n of even permutations is not solvable for any n ≥ 5 implies that no formula exists for solving equations of degree n ≥ 5. This spectacular achievement led to modern Galois theory, but Galois' work went unrecognized until after his death at age 20.

Galois worked with groups of permutations. Then, in 1854, Arthur Cayley formulated the abstract group concept. While the study of permutation groups continues to occupy mathematicians, the abstract theory has the advantage that it isolates those properties of groups that do not depend on the underlying permutations and so can be applied more broadly. We pursue the abstract theory in this chapter (and in Chapters 7–9) with permutation groups as one of the most important examples. 71

2.1 Binary Operations

Abstract algebra is primarily concerned with the study of operations analogous to the addition and multiplication of numbers. We define such operations in this section and examine some of their general properties. The addition process for numbers assigns to any ordered pair (a, b) of numbers a new number, their sum, denoted a + b. Similarly, multiplication assigns the product ab to the pair (a, b).

In general, a binary operation * on a set M is a mapping that assigns to each ordered pair (a, b) of elements of M an element a * b of M. In this case M is said to be closed under the binary operation. Binary operations are usually denoted by other symbols (for example, + for numbers) but, for the moment, we use the generic notation a * b.

A binary operation * is called commutative if a * b = b * a for all a, b in M, and * is called associative if a * (b * c) = (a * b) * c for all a, b, c in M. An element e in M is called a unity (or an identity)¹⁸ for * if a * e = a = e * a for all a in M. The unity for a binary operation is often denoted by different symbols (for example, 0 and 1 are the identities for addition and multiplication of numbers, respectively).

Theorem 1. If a binary operation has a unity, that unity is unique.

Proof. If e and f are both unities, then f = e * f and e * f = e. So e = f.

A set M is called a monoid if a binary operation is defined on M that is associative and has an unity¹⁹. We say that (M, *) is a monoid if the operation * is to be emphasized. If the operation is commutative, we say that M is a commutative monoid.

Example 1. The sets are all commutative monoids under both addition and multiplication. The additive unity is 0 in all cases ( in ), and the multiplicative unity is 1 ( in ).

Example 2. The set of all n × n real matrices is a monoid under both matrix addition and matrix multiplication, the unities being 0 and I, respectively. The monoid is commutative. However, is not commutative if n ≥ 2 (the proof of associativity is given in Appendix B).

Example 3. If U is a set, let M = {X X ⊆ U} denote the set of all subsets of U. Then (M, ∪) and (M, ∩) are both commutative monoids, the unities being ∅ and U, respectively.

Example 4. S_n is a monoid with unity ε, and it is noncommutative if n ≥ 3 (see Exercise 23 §1.4).

Example 5. If X is a nonempty set, let M = {α α: X → X is a mapping}. Then M is a monoid using composition of mappings as the operation and the identity mapping 1_X as the unity (Theorem 3 §0.3). Moreover, M is noncommutative if X has at least two elements.

Example 6. Let * be the operation defined on by n * m = n^m. This operation is neither commutative (2 * 3 = 8 but 3 * 2 = 9) nor associative ((2 * 3) * 2 = 64, but 2 * (3 * 2) = 512), and there is no unity (m = x * m for all m is impossible). Thus is not a monoid. Note, however, that m * 1 = m for all m.

A comment on notation is in order here. Binary operations are denoted by many different symbols in mathematics. For example, + and · are universally used for addition and multiplication of numbers, but these symbols are also standard for the addition and multiplication of matrices. Similarly, ∩ and ∪ are well-established notations in set theory. When a binary operation has such a standard symbol, we use it along with any standard notation for the corresponding unity (as in the foregoing examples). However, when discussing monoids in general, we have been using * for the binary operation. But algebraists do not do this. They usually adopt one of the following two formats.

• Multiplicative Notation. Here a * b is written as ab (or sometimes a · b)  and is called the product of a and b. The multiplicative unity is denoted 1  (or 1_M if the monoid M must be emphasized).
• Additive Notation. Here a * b is written as a + b and is called the sum  of a and b. The additive unity is denoted 0 (or 0_M if the monoid M must  be emphasized).

Multiplicative notation is the most popular format among algebraists. Hence we adopt the following convention.

Convention. In dealing with monoids in general, we use multiplicative notation, and denote the unity by 1.

Hence ab can mean many different things, depending on the monoid under discussion, but the meaning is nearly always clear from the context. The small amount of confusion is more than balanced by the simplicity and conciseness of the notation.

For a finite monoid M, defining the operation by means of a table is sometimes convenient (as in Example 7 below). Given x and y in M, the product xy is the entry of the table in the row corresponding to x and the column corresponding to y. Hence, for the table in Example 7, ab = b and ca = e. The elements of the monoid appear in the same order across the top of the table as down the left side. Such a table is called the Cayley table of the monoid, honoring Arthur Cayley who used it in 1854.

Example 7. If M = {e, a, b, c}, consider the binary operation shown in the table. The first row and column show that e is the unity. That the operation is commutative is also clear from the table because the entries are symmetric about the main diagonal (upper left to lower right). However, this operation is not associative. For example

If a, b, c, and d are elements in a monoid M, there are various ways to form the product abcd—for example [(ab)c]d and a[b(cd)]. Verifying that these forms are equal is not difficult using associativity. In fact, we have

Theorem 2. General Associativity. Let a₁, a₂, , a_n be elements of a monoid M. If the product a₁a₂ a_n is formed (in that order), the result is the same no matter which bracketing is used.

Proof²⁰. Let the standard product be defined inductively by setting and for n ≥ 2. Thus, and so on. We use strong induction on n ≥ 1 to prove the following statement: If p is any product of a₁, a₂, , a_n in that order, then This is clear if n = 1 or n = 2; if n = 3, the only non-standard product is (a₁a₂)a₃, which equals by associativity. In general, because p is formed using multiplication, it must factor as p = qr, where q is a product of a₁, a₂, , a_k and r is a product of a_k+1, , a_n for some k with 1 ≤ k ≤ n − 1. Hence by induction. If k = 1, then

as required. If k > 1, then by induction, and

which completes the proof.

Theorem 2 enormously simplifies notation. It means that, in a monoid, we may (and do) write a₁a₂ a_n for the product of n elements with no ambiguity. If the operation were not associative, we would have to be careful about which bracketing we use. Of course, the order of the factors in a product does make a difference if the operation is not commutative.

Let a be an element of a monoid M. If n ≥ 0 is an integer, inductively define the nth power aⁿ of a as follows:

Thus, a¹ = a, a² = a · a, a³ = a · a · a, and so on. The following laws, familiar for numbers, hold for any monoid.

Theorem 3. Exponent Laws. Let a and b be elements of a monoid M.

Proof. (1) Fix m ≥ 0 and prove (1) by induction on n ≥ 0. If n = 0 then a⁰a^m = 1a^m = a^m = a^0+m. If n ≥ 1 then aⁿa^m = (aaⁿ⁻¹)a^m = a(aⁿ⁻¹a^m). Since aⁿ⁻¹a^m = a^n−1+m by induction, this gives aⁿa^m = a(a^n−1+m) = a^n+m.

(2) Fix n ≥ 0 and induct on m using (1). If m = 0, then (aⁿ)⁰ = 1 = a^n·0. If m ≥ 1, then (aⁿ)^m = aⁿ · (aⁿ)^m−1 = aⁿa^n(m−1) = a^n+n(m−1) = a^nm.

(3) This assertion follows by induction on n after first showing baⁿ = aⁿb for all n ≥ 0 (Exercise 10).

It is interesting to note that, in the monoids of Example 3 (with ∩ and ∪ as the operations), a² = a for all a. Hence aⁿ = a for all n ≥ 1.

Inverses

If s is a nonzero real number, the inverse is the solution to the equation xs = 1. In this form the idea extends to any monoid. If a is an element in a monoid M, an element b of M is called an inverse of a if ab = 1 = ba. An element with an inverse is called a unit. Note that the definition is symmetric in a and b, so that a is an inverse of b if and only if b is an inverse of a.

Theorem 4. If M is a monoid and a M has an inverse in M, then that inverse is unique .

Proof. If both b and b′ are inverses of a, then ab = 1 = ba and ab′ = 1 = b′a. Hence b′ = b′1 = b′(ab) = (b′a)b = 1b = b.

Note the use of associativity in Theorem 4. In fact, its use is essential: In Example 7, both a and c are inverses of c.

If a is a unit in a multiplicative monoid, the inverse of a is denoted a⁻¹. If the monoid is additive the inverse of a is denoted −a and is called the negative of a.

Example 8. Consider the additive monoids and Then every element is a unit and, in all cases, the usual negative −x of an element x is the (additive) inverse.

Example 9. In the multiplicative monoids and every nonzero element is a unit. However, 0 has no inverse in either case.

Example 10. The units of are 1 and −1.

Example 11. The units in are the residues where a and n are relatively prime (Theorem 5 §1.3).

Example 12. If M = {α α: X → X is a mapping} under composition, the units in M are the bijections (onto and one-to-one mappings). (See Theorem 6 §0.3.)

Example 12 is important, and we refer to it again. If X = {1, 2, , n}, the set of units is the symmetric group S_n of degree n (Section 1.4). If we get a monoid containing maps σ and τ such that στ = 1 but τσ ≠ 1. (Example 8 §0.3.)

Example 13. The units in are the matrices A with det A ≠ 0, where det A denotes the determinant of A.²¹ This is discussed in Appendix B.

The next theorem collects several basic properties of units that will be used without comment throughout the book. This theorem will be familiar to students of linear algebra where it is proved for invertible matrices.

Theorem 5. Let a, b, a₁, a₂, , a_n−1, a_n denote elements in a monoid M.

Proof. (1), (2), and (3) depend on the fact that, if ab = 1 = ba for some b then a is a unit and a⁻¹ = b. Thus (1) follows from 1· 1 = 1; (2) follows from a⁻¹a = 1 = aa⁻¹, and (3) follows if we can show that

But (ab)(b⁻¹a⁻¹) = a(bb⁻¹)a⁻¹ = a1a⁻¹ = aa⁻¹ = 1. The other equation can be similarly verified.

Finally (4) follows from (3) by induction on n (Exercise 16), and (5) is the special case of (4) where a₁ = a₂ = = a_n = a.

Note that every monoid has at least one unit: the unity. Moreover, if M is the set of all subsets of a set U, then (M, ∩) and (M, ∪) are monoids in which the unity is the only unit. At the other extreme are the monoids (called groups) in which every element is a unit. These are the principal objects of study in this chapter. With this in mind, we extend the definition of nth powers to include negative powers of a unit. Since (a⁻¹)ⁿ = (aⁿ)⁻¹ by Theorem 5 for any unit a, we define the negative powers a⁻ⁿ, n ≥ 1, by

Then the laws of exponents extend as follows (the proof is left to the reader).

Theorem 6. Let a and b denote units in a monoid M.

2.1 Exercises

2.2 Groups

A group is a monoid in which every element has an inverse. Because of its importance, we give the definition in full detail. A set G is called a group if it satisfies the following axioms.

G1 G is closed under a binary operation.

G2 The operation is associative.

G3 There is a unity element in G.

G4 Every element of G has an inverse in G.

The group G is called abelian²² if, in addition, it satisfies

G5 The operation is commutative.

If G is finite, the number |G| of elements in G is called the order of G.

The terminology used for groups (and other algebraic systems, such as monoids) is somewhat careless. Strictly speaking, a group (G, ·) consists of two things: a set G and a binary operation. However, common practice is simply to refer to a group G and not mention the operation. This practice usually causes no difficulty, because the operation in the group in question is understood. We adopt this loose notation because it is much simpler, and also to acquaint the reader with what is in fact used in more advanced books. When clarity is needed, we use terms such as the group (G, +) or the additive group G.

Examples 1–10 indicate the variety of ways that groups can occur, and we refer to many of them later. We leave verification of the axioms to the reader.

Example 1. {1}, {1, − 1}, and {1, − 1, i, − i} are all abelian groups of (complex) numbers under multiplication. Here −1 is self-inverse, and i and −i are inverses of each other.

Example 2. ²³ and are all abelian groups under multiplication. In each case the inverse of an element a is a⁻¹ = 1/a.

Example 3. The set of complex numbers

is a group under complex multiplication. Here e^iθ = cos θ + i sin θ, as in Appendix A, and we have e^iθeⁱ = e^i(θ+) and (e^iθ)⁻¹ = e^−iθ. The group is called the circle group because it consists of the points on the unit circle.

Example 4. For n ≥ 1, the group is a group under complex multiplication, called the group of nth roots of unity. As in Appendix A, we have

Clearly, for all n ≥ 1, and U₁, U₂, and U₄ are displayed in Example 1.

Example 5. The sets and are all abelian groups under addition. In each case the unity is 0 and the inverse of x is −x.

Although we write most groups multiplicatively, many important groups are written additively (as in Example 5). Then the unity element is denoted 0 and is called zero, and the inverse of x is denoted −x and is called the negative of x.

Example 6. If is an additive abelian group with zero and the negative of being We write in when no confusion can result.

Henceforth, when we refer to one of the groups or we mean the additive group.

Example 7. The set S_n of all permutations of {1, 2, . . ., n} is a group under composition (see Theorem 2 § 1.4), called the symmetric group of degree n.

The group S_n has historical significance because such groups of bijections were among the earliest examples of a group. They were used by Galois in his pioneering work on the theory of equations. In fact Galois was the first to use the term group.

Example 8. We single out S₃ for special emphasis. Recall from Section 1.4 that

If we denote σ = (123) and τ = (12), then σ² = (132), τσ = (23), and τσ² = (13) as is easily verified. Hence we can list S₃ as

The reason for doing this is that it provides an easy way to fill in the Cayley table. In fact, we can fill in the table by using three (easily verified) facts:

The resulting Cayley table is as follows

Note that

Then, for example, we compute the product (τσ)(τσ²) by

The other entries in the table are found in a similar manner (the reader should do this). The elements σ and τ are called generators for S₃, and the equations σ³ = ε, τ² = ε, and στσ = τ are called relations among the generators. We often describe S₃ in this way.

Examples 9 and 10 display two other important groups of permutations.

Example 9. The set A_n of all even permutations in S_n is a group using the operation of S_n, called the alternating group of degree n (Theorem 8 §1.4).

Example 10. Given a (nonsquare) wire rectangle with vertices 1, 2, 3, and 4 as in the diagram, consider the permutations of the vertices induced by moving the rectangle in space (without bending). The 180-rotations about vertical and horizontal axes (see the diagram) give permutations

respectively. If we compute their product in S₄ we obtain another motion στ = (13)(24) because the composite motion στ is the motion τ followed by the motion σ (the reader should verify this). Note that στ can also be viewed as the 180-rotation in the plane of the rectangle about its center. Of course, we have another motion τσ, but this is not a new motion because

is called the group of motions of the rectangle. Such groups of motions are important (for example they arise in the study of symmetries of molecules); we return to them in Section 2.7.

Recall that a set M with an associative operation that has a unity is called a monoid, and that an element u in M that has an inverse u⁻¹ in M is called a unit. A monoid may not be a group, but its units form a group.

Theorem 1. If M is a monoid, the set M^* of all units in M is a group using the operation of M, called the group of units of M.

Proof. From Theorem 5 §2.1, if u and are units, then uv is also a unit (the inverse is ), so M^* is closed under the operation of M. The associativity of M^* is inherited from M and 1 M^* (in fact 1⁻¹ = 1), so M^* itself is a monoid. Finally, if u M^*, then u⁻¹ M^* too (its inverse is u), so M^* is a group.

Theorem 1 provides many important examples of groups. For example, the multiplicative groups in Example 2 are and

Example 11. If X is a nonempty set, M = {α α: X → X is a mapping} is a monoid under composition and Theorem 6 §0.3 shows that the group M^* of units consists of the bijections

The bijections X → X are called permutations of X, and S_X is the permutation group of X. Of course, if X = {1, 2, . . ., n} then S_X = S_n.

Example 12. Consider where is regarded as a multiplicative monoid. Then Theorem 5 §1.3 gives

Hence if (and only if) p is a prime. Other examples include

We refer to these groups frequently.

Example 13. Let R denote . Then the set M_n(R) of all n × n matrices over R is a monoid using matrix multiplication. The group M_n(R)^* of units consists of the invertible n × n matrices over R, that is the matrices such that det A is a unit in R—see Appendix B. It is called the general linear group of degree n over R, denoted GL_n(R). Thus

If G₁, G₂, , G_n are sets, recall that the cartesian product G₁ × G₂ × × G_n is the set of all ordered n -tuples (g₁, g₂, , g_n), where g_i G_i for each i. This set has a natural group structure when the G_i are themselves groups. If G₁, G₂, , G_n are groups, their direct product is the set G₁ × G₂ × × G_n with the component-wise operation defined by

where is the product in G_i for each i. The routine proof of the next theorem is left to the reader.

Theorem 2. If G₁, G₂, , G_n are groups, so also is G₁ × G₂ × × G_n, with unity (1, 1, , 1) and inverses

Because groups are monoids, all the properties of monoids presented in Section 2.1 are automatically properties of groups. In particular:

The next theorem restates Theorem 5 §2.1 for units in monoids for reference.

Theorem 3. Let g, h, g₁, g₂, , g_n−1, g_n denote elements of a group G.

Recall that negative powers of an element g in a group are defined by g^−k = (g⁻¹)^k for k ≥ 1. The next theorem is a restatement of Theorem 6 §2.1.

Theorem 4. Exponent Laws. Let G be a group with elements g and h.

These laws are important and play a prominent role in Section 2.4.

The assumption that every element of a group has an inverse is a very powerful axiom. In particular, it implies the cancellation laws, which we use countless times in this book.

Theorem 5. Cancellation Laws. Let g, h, and f be elements of a group.

Proof. If gh = gf, then left multiplication by g⁻¹ gives (g⁻¹g)h = (g⁻¹g)f. Hence 1h = 1f; that is, h = f. This proves (1), and (2) follows similarly.

Note that “ mixed” cancellation is not valid in general: fg = gh does not imply that f = h. For example, in the group S₃, we have (12)(13) = (13)(23) so (13) cannot be cancelled.

Example 14. If G is a finite group and g G, show that gⁿ = 1 for some n ≥ 1.

Solution. The elements g, g², g³, in G cannot all be distinct because G is finite. So g^m = g^m+n for some m ≥ 1 and n ≥ 1. Thus g^m · 1 = g^m · gⁿ, so 1 = gⁿ by cancellation.

Another consequence of the fact that all elements of a group have inverses is that equations gx = h and xg = h are always solvable.

Theorem 6. Let g and h be elements of a group G.

Proof. If x = g⁻¹h, then gx = gg⁻¹h = 1h = h, so x is indeed a solution in (1). To prove that it is unique, let y also satisfy gy = h. Then gx = gy, so x = y by cancellation. This proves (1), and (2) follows in the same way.

Corollary. Every row (and column) of the Cayley table of a group G contains every element of G exactly once.

Proof. If g G, the row of the table corresponding to g consists of the elements gx as x ranges over G. This row contains every element h of G because gx = h is solvable for each h, and it contains h only once because the solution is unique. A similar argument applies to columns.

A group is determined completely by its Cayley table: associativity and existence of the unity and inverses, which are demanded by the group axioms, all depend entirely on the operation. Now consider the (multiplicative) group of units of and the (additive) group The Cayley tables are

They are the same in the sense that the Cayley table of becomes that of if we replace the symbols 1 and −1 by and respectively. Thus and are the same groups except for notation, and we say that they are isomorphic, or that they are the same up to isomorphism. We discuss this topic in more detail in Section 2.5; for now we prefer to treat the whole matter informally and call two groups isomorphic if they have the same Cayley table except for notation. As a result we can give an application of the Corollary to Theorem 6.

Example 15. Show that, up to isomorphism, there is only one group G of order 1, 2, or 3, and that group can be described in the following manner.

• If |G| = 1, then G = {1}.
• If |G| = 2, then G = {1, g}, where g² = 1.
• If |G| = 3, then G = {1, g, g²}, where g³ = 1.

In each case the Cayley table is determined by the laws of exponents.

Solution. In each case we show that there is only one way to fill in the Cayley table. Multiplication by 1 is prescribed. If |G| = 1, then G = {1} and the Cayley table is determined. If |G| = 2, let G = {1, g}, where g ≠ 1. The only entry in the Cayley table that is in doubt is whether g² = g or g² = 1. But g² = g is impossible because it implies that g = 1 by cancellation. Hence g² = 1 and the table is determined.

Turning to the case |G| = 3, write G = {1, g, h}. Then gh ≠ g and gh ≠ h by cancellation, so we must have gh = 1. Now repeated use of the Corollary to Theorem 6 (beginning with row 2 and column 3) gives the table on the left.

In particular, g² = h, so G = {1, g, g²}, and g³ = gh = 1, as shown in the table on the right. This table is associative, a known realization being the group {ε, (123), (132)} of permutations.

The groups in Example 15 all have the rather special property that every element is a power of a particular element and are called cyclic groups. There exists a cyclic group of order n for every n ≥ 1. Indeed the group U_n of nth roots of unity is cyclic of order n. In fact, if we write then has order n and

We discuss cyclic groups in detail in Section 2.4 and treat them informally for now. They occur frequently, and the following generic notation is useful. Given n ≥ 1, the cyclic group of order n is the group C_n of order n:

We write in this case, and the element a is called a generator of C_n. Our insistence that |C_n| = n means that 1, a, a², . . ., aⁿ⁻¹ are distinct elements of C_n.

The Cayley table of C_n is determined completely by the exponent laws and the condition aⁿ = 1. In fact, exponents in C_n can be reduced modulo n. That is, if k = qn + r, where 0 ≤ r ≤ n − 1, then a^k = a^r because a^k = (aⁿ)^qa^r = 1^qa^r = a^r. In particular,

This expression gives the Cayley table for C_n (below), and so is sufficient for all computations in C_n.

Example 16. Let C₁₂ = {1, a, a², . . ., a¹¹}, a¹² = 1, be a cyclic group of order 12. Compute a⁸⁹ and a⁻⁴⁰ in C₁₂.

Solution. Because 89 = 7 · 12 + 5, we get a⁸⁹ = (a¹²)⁷a⁵ = 1⁷a⁵ = a⁵. Similarly, −40 = (− 4) · 12 + 8, so a⁻⁴⁰ = (a¹²)⁻⁴a⁸ = 1⁻⁴a⁸ = a⁸.

Example 17. Show that bⁿ = 1 for every element b of C_n.

Solution. Write where aⁿ = 1. Then b = a^k for some k, so we have

Example 15 shows that every group of order 1, 2, or 3 is cyclic. However, this is not the case for groups of order 4.

Example 18. Show that there are only two groups of order 4, the cyclic group C₄ and a noncyclic group K₄ whose Cayley table is shown below.

table is the one on the left below. In that case a² = c, a³ = ca = b, and a⁴ = c² = 1, so is cyclic.

Similarly if the product of any two of a, b, and c equals 1 then G is cyclic (possibly with a different generator). Thus, if G is not cyclic, the product of any two of a, b, and c must equal the third (for example, bc ≠ b, c, or 1, so bc = a). Hence we get the Cayley table on the right as required.

The group K₄ = {1, a, b, c} in Example 18 is called the Klein group.²⁴ The multiplication can be described as follows: a² = b² = c² = 1, and the product of any two of a, b, and c is the third.

If you are nervous because we have not shown that K₄ is associative, you can relax. The (associative) group has exactly the Cayley table of K₄ if we write a = 3, b = 5, and c = 7. Another instance of K₄ is the permutation group K = {ε, (12)(34), (13)(24), (14)(23)}. Example 18 shows that there are two groups of order 4: the cyclic group and the (noncyclic) Klein group. The reader should try to show that every group of order 5 is cyclic; in fact, if p is any prime, we show in Section 2.6 that every group of order p is cyclic.

Exercises 2.2

2.3 Subgroups

Many important groups arise as subsets of known groups. Therefore, we are interested in knowing which subsets H of a group G are themselves groups (with the same operation). Thus a subset H of a group G is called a subgroup of G if H itself is a group using the operation of G. For example, is a subgroup of However the multiplicative group is not a subgroup of even though is a subset of because the operations are different.

Example 1. If G is any group, both {1} and G are subgroups of G. The subgroup {1} is the trivial subgroup of G. Any subgroup other than G is a proper subgroup.

Example 2. Each of the additive groups is a subgroup of the larger ones.

Example 3. A_n is a subgroup of S_n.

Example 4. denotes the circle group, then each of

is a subgroup of the larger ones.

In each of these examples, the subgroups of a group G not only have the same operation as G, but they also share the same unity element and the same inverses. This observation is true in general and, in fact, provides a very useful test for when a subset of a group is actually a subgroup.

Theorem 1. Subgroup Test. A subset H of a group G is a subgroup if and only if the following three conditions are satisfied .

In this case, H has the same unity as G and, if h H, its inverse in H is the same as its inverse in G.

Proof. If H satisfies (1), (2), and (3), then H is closed by (2), the unity of G is the unity for H by (1), and the inverse in G of an element h H serves as the inverse of h in H by (3). As H inherits the associative law from G, it is a subgroup.

Conversely, if H is a subgroup, let e denote the unity of H. Then e² = e = e · 1_G, so e = 1_G by cancellation in G. This proves (1), and (2) follows because H is closed under the operation of G. Finally, if h H, let h′ denote its inverse in H. If h⁻¹ is the inverse in G, then hh′ = 1 = hh⁻¹, so h′ = h⁻¹ by cancellation in G. This proves (3) and the last sentence in the theorem.

Theorem 1 is useful as the conditions are easily checked (see also Exercise 2).

Example 5. If R is one of or let Show that H is a group using matrix multiplication, called the special linear group.

Solution. We have —see Example 13 §2.2—so we show that it is a subgroup of We have I H because det I = 1. If A and B H, then det (AB) = det A det B = 1 · 1 = 1 and det A⁻¹ = 1/det A = 1/1 = 1. These results show that AB H and A⁻¹ H, so the subgroup test applies.

Example 6. If n ≥ 0, write Show that is a subgroup of

Solution. The unity of is 0, and If a and b are in write them as a = nk and b = nm, where and Then a + b = n(k + m) and −a = n(− k) both lie in so is a subgroup of by the subgroup test.

Theorem 2. Finite Subgroup Test. If H is a finite nonempty subset of a group G, then H is a subgroup of G if and only if H is closed (h, h₁ H implies hh₁ H).

Proof. If H is closed, let h H. Then each of h, h², h³, is in H so, because H is finite, they cannot all be distinct. Hence hⁿ = h^n+m for some n ≥ 1 and m ≥ 1. This means 1 = h^m by cancellation, so 1 H by hypothesis. But then 1 = h^m−1h implies that h⁻¹ = h^m−1, so h⁻¹ H, too. Because H is closed by hypothesis, it is a subgroup by Theorem 1. The converse is clear.

Example 7. Determine all subgroups of the Klein group K₄ = {1, a, b, c}, where a² = b² = c² = 1 and the product of two of a, b, and c is the third.

Solution. Each of H_a = {1, a}, H_b = {1, b}, and H_c = {1, c} is a subgroup by Theorem 2, because a² = b² = c² = 1. Any subgroup H with |H| ≥ 3 must contain two of a, b, and c and so contains the other one (their product). Thus, H = G and the complete list of subgroups is {1}, H_a, H_b, H_c, and G.

Example 8. Determine all subgroups of C₄ = {1, a, a², a³}, a⁴ = 1.

Solution. Let H = {1, a²}. Then H is a subgroup by Theorem 2 because (a²)² = a⁴ = 1. Suppose that K is a subgroup distinct from {1} and H. Then either a K or a³ K. If a K, then (because K is closed) each power a, a², and a³ is in K, so K = C₄. Similarly, H = C₄ if a³ H because, as the reader can verify, C₄ = {1, a³, (a³)², (a³)³}. Thus the subgroups are {1}, H = {1, a²}, and C₄.

It is descriptive to draw the lattice diagram of all subgroups of a group G. Here the subgroups are shown in such a way that a line can be drawn up from K to H whenever K ⊆ H. The diagrams for K₄ = {1, a, b, c} and for a cyclic group C₄ = {1, a, a², a³} of order 4 are given below.

If G is any group, the center of G is defined²⁶ by

The elements in Z(G) are said to be central in G.

Theorem 3. If G is any group, then Z(G)is an abelian subgroup of G.

Proof. Use the subgroup test. Clearly 1 Z(G). If z Z(G), then zg = gz for all g G, so multiplying this equation on the left by z⁻¹ gives g = z⁻¹gz. Then multiplication on the right by z⁻¹ gives gz⁻¹ = z⁻¹g. Thus z⁻¹ Z(G). Finally, if both y and z lie in Z(G), then, for all g G,

Thus, yz Z(G), so Z(G) is a subgroup. It is clearly abelian.

Observe that Z(G) = G if and only if G is abelian. At the other extreme, it can happen that Z(G) = {1} so G is as far from abelian as it can be. In fact we have:

Example 9. If n ≥ 3, show that Z(S_n) = {ε}, where ε is the identity permutation.

Solution. If σ S_n, σ ≠ ε, we must find τ S_n such that στ ≠ τσ. Because σ ≠ ε, choose k and m in X_n = {1, 2, , n} such that σk = m ≠ k. Because n ≥ 3, let l, k, and m be distinct, with l X_n, and take τ to be the transposition τ = (kl). Then (τσ)k = τm = m and (στ)k = σl, so it suffices to show that σl ≠ m. But if σl = m then σl = σk, so l = k because σ is one-to-one, a contradiction.

We now turn to two important ways of manufacturing new subgroups from old ones. The straightforward proof of Theorem 4 is left as Exercise 16.

Theorem 4. Let H and K be subgroups of a group G. then their intersection

is also a subgroup of G.

Note that H ∩ K is a subgroup of both H and K, and is the largest such subgroup in the sense that if X is a subgroup of both H and K then X ⊆ H ∩ K. Incidentally, the union H ∪ K of two subgroups is almost never a subgroup (see Exercise 17).

The next theorem introduces another important type of subgroup.

Theorem 5. Let H be a subgroup of a group G. If g G, then

is a subgroup of G. These subgroups are called the conjugates of H in G.

Proof. Clearly, 1 = g1g⁻¹ is an element of gHg⁻¹. Given ghg⁻¹, where h H,

Finally (ghg⁻¹)(gh₁g⁻¹) = g(hh₁)g⁻¹ for any h, h₁ in H, which shows that gHg⁻¹ is closed. Thus it is a subgroup by the subgroup test.

If H is a subgroup of G, then H = 1H1⁻¹, so H is always a conjugate of itself. If H is the only conjugate of H in G (that is, gHg⁻¹ = H for all g G), then H is said to be self-conjugate (or normal) in G. These subgroups play a fundamental role in group theory, and will be investigated in detail in Sections 2.8,2.9, and 2.10. Example 10 displays a subgroup that is not self-conjugate.

Example 10. Let S₃ = {ε, σ, σ², τ, τσ, τσ²}, where σ³ = ε = τ² and στσ = τ. Find the conjugates of the subgroup H = {ε, τ}.

Solution. Clearly εHε⁻¹ = H. Since σ⁻¹ = σ² and στσ = τ, we get

Similarly, σ²Hσ⁻² = {ε, τσ²}. These are all the conjugates of H in G (verify).

Exercises 2.3

2.4 Cyclic Groups and the Order of an Element

We have already introduced the cyclic groups C_n, n ≥ 1, but discussed these groups only informally. Recall that C_n has the form C_n = {1, a, , aⁿ⁻¹}, where aⁿ = 1, so C_n consists of powers of A. In this section, we classify groups consisting of all powers of a particular element and determine all subgroups of such groups. This endeavor is important because these groups are building blocks for all sufficiently “ small” abelian groups (including all finite ones).

We begin by showing that the set of all powers of an element of a group G is an important subgroup of G.

Theorem 1. Let g be an element of a group G and write

Then is a subgroup of G, and for every subgroup H of G with g H.

Proof. Clearly, If write them as x = g^k, y = g^m. Then the exponent laws give and and the subgroup test applies. Finally, and if g H where H is a subgroup then because g^k H for all integers k.

Hence, if g G then is the smallest subgroup of G containing the element g.

If g is an element of a group G, the subgroup is called the cyclic subgroup of G generated by g. If for some g G, we say that G is a cyclic group and that g is a generator of G. Thus, the generic cyclic group C_n = {1, a, , aⁿ⁻¹}, aⁿ = 1, is cyclic in the present sense, so the terminology is consistent.

Example 1. If G is any group, is a cyclic subgroup of G.

Example 2. The group G = {1, − 1, i, − i} is cyclic. In fact, i² = − 1 and i³ = − i show that Similarly, so both i and −i are generators. But −1 is not a generator, because all positive and negative powers of −1 are either 1 or −1. Hence is not all of G.

If a group X is written additively, recall that the unity element is denoted 0 and the inverse of x X is denoted −x. The exponent xⁿ (in multiplicative notation) becomes nx here, so the cyclic subgroup generated by x is

consisting of the multiples of x. The laws of exponents translate as follows:

and if x and y commute

Here are two important examples of cyclic additive groups.

Example 3. Show that is cyclic and that 1 and −1 are the only generators.

Solution. If then so Similarly, because k = (− k) · (− 1). Clearly , if n ≠ 1 and n ≠ − 1 (for example

Example 4. Show that is cyclic with generator

Solution. We have where, for the moment, we revert to the formal notation for residue classes. Given in note that is a multiple of and so It follows that as required.

Example 5. In the multiplicative group of nonzero real numbers, the cyclic group consists of all the powers (positive, zero, and negative) of 3. Note that these powers are all distinct in this case.

Example 6. Consider the group Here are the powers of 2:

If the elements in the bottom row are read left to right they “ cycle” endlessly through the sequence 1, 2, 4 (this is the source of the term cyclic group). Clearly and the reason that has three elements is that 3 is the smallest positive integer n such that 2ⁿ = 1 in

Order of an Element

These examples point to one of the most useful concepts in group theory. Let g be an element of a group, and suppose that g^k = 1 for some integer k ≠ 0. Since g^−k = 1 also holds, we may assume that k ≥ 1, so the well-ordering principle guarantees that there is a smallest integer n ≥ 1 such that gⁿ = 1. This integer n is called the order of g, and is denoted o(g) = n. If no such integer n exists we say that g has infinite order and write o(g) = ∞. To sum up:

In particular, in Example 5, o(3) =∞ in , while in Example 6, o(2) = 3 in Note that the unity element 1 is the only element of order 1 in any group.

Example 7. Find the order of each element in Is cyclic?

Solution. We have o(1) = 1. Since 3² = 9 = 1 in it follows o(3) = 2. Similarly, o(5) = 2 and o(7) = 2. Hence no element of has order 4, so is not cyclic.

Example 8. Find in

Solution. Write Then and so A⁶ = I. Since A⁴ ≠ I and A⁵ ≠ I, we conclude that

Example 9. If γ = (k₁k₂ k_r) is a cycle in S_n, then o(γ) = r is the length of γ.

Solution. If the integers k₁, k₂, . . . k_r are uniformly placed on a circle, the cycle γ moves each integer one position clockwise, as shown in the diagram. Hence γ², γ³, . . . carry each in-teger 2, 3, . . . positions clockwise, respectively, so γⁿ ≠ ε for 1 ≤ n ≤ r − 1, whereas γ^r = ε. This means that o(γ) = r.

Example 10. Show that o(g⁻¹) = o(g) for any group element g.

Solution. If then (g⁻¹)^k = (g^k)⁻¹, and it follows that (g⁻¹)^k = 1 if and only if g^k = 1. Hence the smallest positive integer n (if any) such that gⁿ = 1 is the same as the smallest positive integer n such that (g⁻¹)ⁿ = 1. That is, o(g⁻¹) = o(g).

Example 11. If G is a finite group, show that every element g G has finite order.

Solution. Since G is finite, the powers g, g², g³, are not all distinct, so let g^k = g^m with k < m. Then g^m−k = 1 where m − k > 0 so 0(g) is finite.

Computing the order of an element is simplified by the next theorem

Theorem 2. Let G be a group and let g G satisfy o(g) = n. Then

Proof. We use the laws of exponents.

(1) If n|k, say k = qn, then g^k = (gⁿ)^q = 1^q = 1. Conversely, if g^k = 1, write k = qn + r with 0 ≤ r < n (division algorithm). But then we have g^r = g^k(gⁿ)^−q = 1(1)^−q = 1. Since r < n, this contradicts the minimality of n unless r = 0. So r = 0 and n|k.

(2) We have g^k = g^m if and only if g^k−m = 1. Now apply (1).

(3) Clearly, To prove the other inclusion, let say x = g^k. As before, write k = qn + r, where 0 ≤ r ≤ n − 1. Then

which shows that Hence To complete the proof, suppose two of 1, g, g², , gⁿ⁻¹ are equal, say g^k = g^m, where 0 ≤ k ≤ m < n. Then g^m−k = 1 and 0 ≤ m − k < n. This implies that m − k = 0 by the minimality of n, so g^m = g^k. Thus 1, g, g², , gⁿ⁻¹ are distinct.

Theorem 2 asserts that if o(g) = n, then g^k = 1 if and only if n|k. The following example illustrates how useful this is.

Example 12. Find the order of 2 in

Solution. We compute in : 2³ = 8, so 2⁶ = 64 = 7 and 2⁹ = 56 = − 1. Hence 2¹⁸ = 1, so o(2) divides 18 by Theorem 2. Thus, o(2) is 1, 2, 3, 6, 9, or 18. We have already eliminated 3, 6, and 9, so as 2¹ = 2 and 2² = 4, the only possibility remaining is o(2) = 18. Note that, since = 18, this shows that is cyclic and that 2 is a generator.

The next result is the “ companion” of Theorem 2 for elements g with o(g) = ∞.

Theorem 3. Let G be a group and let g G satisfy o(g) = ∞. Then

Proof. (1) Clearly g⁰ = 1. If g^k = 1, k ≠ 0, then g^−k = (g^k)⁻¹ = 1⁻¹ = 1, too. Hence gⁿ = 1 for some n > 0, which implies that is finite, contrary to hypothesis. Thus g^k = 1 implies that k = 0.

(2) We have g^k = g^m if and only if g^k−m = 1. Apply (1).

(3) by definition, and these powers are distinct by (2).

If o(g) = n, then too, by (3) of Theorem 2, so in this case. Since this also holds if o(g) = ∞, we have shown that our two uses of the word “ order” are compatible.

Corollary. We have o(g) = for every element g of any group.

We now use Theorem 2 to derive an elegant formula for the order of any permutation σ in S_n. Recall that σ factors (uniquely) as a product of disjoint cycles γ_i (Theorem 5 §1.4). The order of σ turns out to be the least common multiple of the orders of the cycles γ_i (which are the lengths of the γ_i by Example 9).

Theorem 4. Let σ be a permutation in S_t with factorization σ = γ₁γ₂ γ_r into disjoint cycles. Then |σ| = lcm(o(γ₁), o(γ₂), , o(γ_r)).

Proof. Write n = o(σ), n_i = o(γ_i), and m = lcm(n₁, n₂, , n_r). As n_i|m for each i, we have and so (because the γ_i commute). Hence n|m by Theorem 2. To show that m|n, it suffices to show that for each i (then n_i|n by Theorem 2 so m|n by the definition of the least common multiple). We show that the others are similar. This requires proving that for all 0 ≤ k ≤ n. This is clear if k is fixed by γ₁, so let k be moved by γ₁. Then k is fixed by each of γ₂, , γ_r, because the γ_i are disjoint. Thus, since we have

It follows that as required.

Example 13. Find the order of

σ = .

Solution. Here σ = (151013414) (2712611) (39) is the cycle factorization, so Theorem 4 gives o(σ) = lcm(6, 5, 2) = 30.

The next result will be used several times below.

Theorem 5. Let o(g) = n for g in some group. If d|n, d ≥ 1, show that

Proof. Write for convenience. Then (g^d)^k = gⁿ = 1, so we must show that k is the smallest such positive integer. Suppose (g^d)^r = 1, r ≥ 1. Then g^dr = 1 so n|dr by Theorem 2, say dr = qn, q ≥ 1. But then dr = q(dk), so r = qk because these are integers and d ≠ 0. It follows that r ≥ k, as required.

Other Properties of Cyclic Groups

Theorem 6. Every cyclic group is abelian, but the converse does not hold.

Proof. Let be cyclic with generator g. If x, y G, write x = g^k, y = g^m, where Then the exponent laws give

so G is abelian. However is abelian but not cyclic by Example 7.

As the proof of Theorem 6 illustrates, computations in a cyclic group depend entirely on the exponents of the generator. As these exponents are integers, the facts about derived in Chapter 1 turn out to be useful. In particular, the division algorithm plays a natural role in the proof of Theorem 7.

Theorem 7. Every subgroup of a cyclic group is cyclic.

Proof. Suppose that is cyclic and let H be a subgroup of G. If H = {1}, then is cyclic. Otherwise, let g^k H, k ≠ 0. Because H is a subgroup, g^−k = (g^k)⁻¹ H, and so we may assume that k > 0. Hence let m be the smallest positive integer such that g^m H. Then and we claim this is equality. To see this, let g^k H and write k = qm + r, 0 ≤ r < m, by the division algorithm. It suffices to show that r = 0 (then ). But g^r = (g^m)^−qg^k H, which contradicts the minimality of m unless r = 0.

A cyclic group can have other generators, for example, Theorem 8 explicitly describes all generators of a finite cyclic group.

Theorem 8. Let be a cyclic group, where o(g) = n. Then if and only if gcd (k, n) = 1.

Proof. If then say g = (g^k)^m, where Thus g¹ = g^km, so n divides 1 − km by Theorem 2. Then 1 − km = qn for that is, 1 = km + qn, which implies that gcd (k, n) = 1. Conversely, if gcd (k, n) = 1 then 1 = xk + yn for some integers x and y by Theorem 4 §1.2. Hence

which implies that

Hence, for example, if o(g) = 12 the generators of are the powers g^k where gcd (k, 12) = 1, that is g, g⁵, g⁷, and g¹¹. In particular, the generators of the additive cyclic group are the residues and

Theorem 9 below gives a complete description of all subgroups of a finite cyclic group G. In particular, it shows that G has a unique subgroup of order k for every divisor k of n, and that these are the only subgroups of G.

Theorem 9. Fundamental Theorem of Finite Cyclic Groups. Let be a cyclic group of order n.

Proof. (1) Theorem 7 implies that for some m. Let d = gcd (m, n); we show that We have d|m, say m = qd, so when On the other hand, d = xm + yn, for some so

Hence so But then, by Theorem 5, so |H| divides n.

(2) Suppose that K is any subgroup of G of order k where k|n. By (1) let where d|n. Then Theorems 2 and 5 give It follows that so This proves (2).

If G is finite and cyclic and H is a subgroup, part (1) of Theorem 9 shows that |H| divides |G|. In fact, this result is true for any finite group G, cyclic or not. The general result is called Lagrange's theorem, which we prove in Section 2.6.

Example 14. Find all subgroups of C₁₂ and draw the lattice diagram.

Solution. Let , o(g) = 12. The divisors of 12 are 1, 2, 3, 4, 6, and 12. Using Theorem 5, the unique subgroup of each of these orders is, respectively,

, , , , , and

The lattice diagram is as shown at the right. Note that if and only if k|m.     

We speak of the cyclic subgroup as being generated by the single element g. We conclude this section with a brief discussion of subgroups generated by more than one element.

Theorem 10. Let X be a nonempty subset of a group G and let

denote the set of all products of powers of (not necessarily distinct) elements of X. Then

Proof. (1) Choose x X (because X ≠ ∅). Then The set is clearly closed and, if is in then is also in Hence is a subgroup of G by the subgroup test.

(2) If X ⊆ H and is in then each is in H because x_i X ⊆ H and H is a subgroup. Hence g H, proving (2).

Thus, if X is a nonempty subset of a group G, the subgroup in Theorem 10 is the smallest subgroup of G that contains X (in the sense of (2) of Theorem 10). Hence is called the subgroup generated by X. If G has the form for some X ⊆ G, we call X a set of generators for G; if X is finite, we say that G is a finitely generated group.

Obviously, so the cyclic groups are exactly the subgroups generated by singleton subsets. Similarly, it is customary to write

for finitely generated groups.

Example 15. Consider the symmetric group S₃ = {ε, σ, σ², τ, τσ, τσ²}, where |σ| = 3, |τ| = 2, and στ = τσ². Then

Example 16. The Klein group K₄ = {1, a, b, ab} is generated by any two nonunity elements.

Exercises 2.4

2.5 Homomorphisms and Isomorphisms

Mathematicians do not deal in objects, but in relations among objects; they are free to replace some objects by others so long as the relations remain unchanged. Content to them is irrelevant: they are interested in form only.

—Henri Poincaré

Up to this point we have ignored mappings from one group to another. The interesting ones are those that preserve the group multiplication in the following sense: If G and H are groups, a mapping α: G → H is called a homomorphism²⁷ if

Of course the product ab here is in G while α(a) · α(b) is in H.

Homomorphisms arise in many forms as the following examples illustrate.

Example 1. The mapping given by α(a) = 3a is a homomorphism of additive groups because α(a + b) = 3(a + b) = 3a + 3b = α(a) + α(b) for all

Example 2. If a is an element of a group G, define the exponent map by α(k) = a^k for all Then α is a homomorphism because (as the operation in is addition)

Example 3. Let denote the group of positive real numbers under multiplication. The absolute value map given by α(z) = |z| for all is a homomorphism (in fact, onto) because for all

Example 4. Let denote the general linear group of n × n invertible matrices over The determinant map given by A det A is a homomorphism because det (AB) = det A det B for all matrices A and B, and det A ≠ 0 if A is invertible.

Example 5. The identity map 1_G: G → G is a homomorphism for any group G because 1_G(ab) = ab = 1_G(a) · 1_G(b) for all a, b in G.

Example 6. For groups G and H, there is at least one homomorphism from G to H, the trivial homomorphism α: G → H defined by α(g) = 1 for all g G.

Example 7. If α: G → H and β: H → K are homomorphisms, show that the composite map βα: G → K is also a homomorphism.

Solution. This is because, for all a and b in G,

By definition, a homomorphism α: G → H is a mapping that preserves the operation in the sense that α(ab) = α(a)α(b) for all a and b in G. Theorem 1 shows that α is “ structure preserving” in the sense that it also preserves the unity, inverses, and powers.

Theorem 1. Let α: G → H be a group homomorphism. Then

Proof.

Hence (3) holds for all k ≥ 0 by induction. If k < 0, write k = − m, m > 0. Then (2) and the preceding calculation give

α(g^k) = α[(g^m)⁻¹] = [α(g^m)]⁻¹ = [α(g)^m]⁻¹ = [α(g)]^−m = [α(g)]^k.

Thus [α(g)]^k = α(g^k) for all

Corollary 1. Let α: G → H be a homomorphism. If g G has finite order, then α(g) also has finite order, and o(α(g))divides o(g).

Proof. If o(g) = n then gⁿ = 1, so α(g)ⁿ = α(gⁿ) = α(1) = 1. Hence o(α(g)) divides n by Theorem 2 §2.4.

Corollary 2. If α: G → H is a homomorphism, write α(G) = {α(g) g G}. Then α(G) is a subgroup of H.

Proof. This follows from the subgroup test because of the following observations: 1_H = α(1_G) α(G); α(g)α(g₁) = α(gg₁) α(G), and α(g)⁻¹ = α(g⁻¹) α(G).

The group α(G) in Corollary 2 is called the image of α. Note that α: G → H is onto if and only if α(G) = H.

Example 8. Let α: G → H be an onto homomorphism.

Solution. Let h, h₁ H. Since α is onto, write h = α(g) and h₁ = α(g₁), g, g₁ G.

Let G and H denote groups. In order to show that two mappings α: G → H and β: G → H are equal, we must verify that α(g) = β(g) holds for all g G. However, if α and β are homomorphisms, this need only be checked for all g in some generating set for G—see Theorem 10 §2.4.

Theorem 2. Let α: G → H and β: G → H be homomorphisms and assume that is generated by a subset X. Then

Proof. If α = β, the condition is obvious. If the condition holds, let g G and write (Theorem 10 §2.4) where x_i X and for each i. Then Theorem 1 gives

α(g) = α(x₁)k₁α(x₂)^k₂ α(x_n)^k_n = β(x₁)₁^kβ(x₂)₂^k β(x_n)_n^k = β(g).

As g G was arbitrary, this shows that α = β.

Theorem 2 shows that a group homomorphism α: G → H is completely determined by its effect on a generating set for G. This is useful because many groups are generated by a relatively small number of elements.

Example 9. Show that there are at most six homomorphisms S₃ → C₆.

Solution. As in Example 8 §2.2 we write S₃ = {1, σ, σ², τ, τσ, τσ²} where o(σ) = 3, o(τ) = 2, and στσ = τ, and write o(c) = 6. Hence so Theorem 2 shows that a homomorphism α: S₃ → C₆ is determined by the choice of α(σ) and α(τ) in C₆. Now α(σ)³ = α(σ³) = α(ε) = 1, so o(α(σ)) is 1 or 3. Hence there are three choices for α(σ): 1, c², or c⁴. Similarly, α(τ)² = 1, so α(τ) must be 1 or c³. Thus, there are at most 3 · 2 = 6 choices in all for α(σ).

We hasten to note that not all the choices in Example 9 correspond to actual homomorphisms. In fact, there are only two homomorphisms from S₃ to C₆, and we return to this example later (see Example 9 §2.10).

Isomorphisms

We have shown that there are two distinct groups of order 4: the cyclic group and the noncyclic Klein group. Determining how to distinguish between distinct groups leads to the notion of isomorphic groups. Roughly speaking, the two groups are isomorphic if they are the same except for notation.

As an illustration, consider the groups G = {1, − 1} and The two Cayley tables are

Clearly, they are alike. In fact, because the way the unity multiplies is always specified, we can describe both by saying that the nonunity element squares to 1. Here is a more precise comparison: Consider the mapping given by

Then α is a bijection, and we can obtain the entire Cayley table for from that of G by replacing a with σ(a) for every a in G. In other words, the two groups are the same except for notation; we obtain from G by changing symbols.

This works in general. If G and H are groups and σ: G → H is a bijection, we ask when the Cayley table for H results from applying σ to every element of the table for G. Looking at the diagram

the required condition is σ(ab) = σ(a)σ(b) for all a and b in G. In other words, σ must be is a homomorphism. This leads to the following definition.

If G and G₁ are groups, a mapping

if σ is a bijection (one-to-one and onto) which is also a homomorphism. When an isomorphism exists from G to H we say that G is isomorphic to H and we write

Hence, if σ: G → H is an isomorphism, the group H is just G with the change of notation g σ(g). As in the preceding illustration, G and H are the same group except for the symbols used. It is useful to think of isomorphic groups as two different realizations of the same (abstract) group.²⁸

Example 10. The set of even integers is an additive group, in fact a subgroup of Show that

Solution. The function given by σ(k) = 2k for all is clearly onto, and σ is one-to-one because σ(k) = σ(m) implies 2k = 2m, so k = m. Finally, σ is a homomorphism:

for all k and m in Thus σ is an isomorphism, so

Note that the argument in Example 10 shows that for any integer n ≠ 0.

Example 11. If show that G is a group using matrix multiplication, and that

Solution. Define by σ(n) = for all n in Then σ is clearly one-to-one, and it is a homomorphism because

Hence is a subgroup of by Corollary 2 of Theorem 1. Moreover, σ is a bijection so is an isomorphism.

Clearly, G G for any group G (the identity map G → G is an isomorphism). However, even though two groups are isomorphic, they sometimes appear to be quite different. As a remarkable example, the group of all nonzero complex numbers is known to be isomorphic to the circle group of complex numbers on the unit circle.²⁹ Here is a less spectacular example. Recall that

Example 12. Show that where is additive and is multiplicative.

Solution. Define by σ(r) = e^r, where e^x is the exponential function. To show that σ is one-to-one, let σ(r) = σ(s), where Then e^r = e^s so, if ln x denotes the natural logarithm of x, r = ln (e^r) = ln (e^s) = s. Thus σ is one-to-one. If then t > 0, so and σ(ln t) = e^lnt = t. Hence σ is onto. Finally,

σ(r + s) = e^r+s = e^re^s = σ(r) · σ(s), for all r and s in

which shows that σ is an isomorphism.

Example 13. If G G₁ and H H₁, show that G × G₁ H × H₁.

Solution. Let σ: G → G and τ: H → H₁ be isomorphisms, and define a mapping μ: G × H → G₁ × H₁ by μ(g, h) = (σ(g), τ(h)). This is a homomorphism because

for all (g, h) and (g′, h′) in G × H. The proof that τ is onto and one-to-one is left to the reader.

Verifying that a particular mapping is an isomorphism requires checking three things: that it is onto; that it is one-to-one; and that it is operation-preserving. Even if a particular mapping α: G → H may fail one of these tests, the groups G and H may very well be isomorphic (for example r r + 1 is a bijection but it is not an isomorphism). Conversely, showing that G and H are not isomorphic entails showing that no isomorphism exists from G to H. Examples 14 and 15 illustrate this situation.

Example 14. Show that is not isomorphic to

Solution. Suppose that is an isomorphism. Then σ is onto, so let satisfy σ(q) = 2, and write Since σ is a homomorphism, we have

This is impossible because (Example 3 §0.1), so no such σ can exist.

Example 15. Let G and H be cyclic groups with |G| = 9 and |H| = 3. Show that G and H × H are not isomorphic, even though both groups have order 9.

Solution. Suppose that σ: H × H → G is an isomorphism. If where o(a) = 9, let a = σ(x) with x H × H. Then x³ = 1 (this holds in H) so a³ = σ(x³) = 1, a contradiction. Hence

The reason that in Example 15 is that, while x³ = 1 for every element x of H × H, this is not the case for G. The condition x³ = 1 for all x is a property of the Cayley table of H × H but not of the Cayley table of G. The fact that group isomorphisms preserve such properties is the reason that H × H is not isomorphic to G. More generally, we can often show two groups are not isomorphic by exhibiting such a property that holds in one but not the other.

Theorem 3. Let G, H, and K denote groups.

Proof. (1) is clear.

(2) The inverse mapping σ⁻¹: H → G exists because σ is a bijection, and σ⁻¹ is also a bijection (Theorems 5 and 6 §0.3). So it remains to show that σ⁻¹ is a homomorphism. If g₁ and h₁ are in G₁, write g = σ⁻¹(g₁) and h = σ⁻¹(h₁). Then σ(g) = g₁ and σ(h) = h₁, so

σ⁻¹(g₁h₁) = σ⁻¹[σ(g) · σ(h)] = σ⁻¹[σ(gh)] = gh = σ⁻¹(g₁) · σ⁻¹(h₁).

Therefore σ⁻¹ is a homomorphism, and hence is an isomorphism.

(3) The map τσ is a bijection by Theorem 3 §0.3; now apply Example 7.

Corollary 1. The isomorphic relation is an equivalence for groups. That is

Proof. (1), (2), and (3) follows from the corresponding items in Theorem 3.

As an illustration of Corollary 1, we show that if G and H are both cyclic of order n then G H. Indeed and by Example 13, so G H by Corollary 1.

Automorphisms

If G is a group, an isomorphism G → G is called an automorphism of G.

Corollary 2. If G is a group, the set of all automorphisms G → G forms a group under composition.

Proof. The automorphisms G → G are a subset of the group S_G of all bijections G → G, and Theorem 3 shows that they are a subgroup of S_G by the subgroup test.

The set of all automorphisms of G is called the automorphism group of G, and is denoted autG.

Example 16. If G is abelian, the mapping σ: G → G defined by σ(g) = g⁻¹ for all g G is an automorphism of G. We leave the verification as Exercise 10.

If G is a group and a G, define a mapping σ_a: G → G by

This map σ_a is an automorphism of G (see Example 17 below), called the inner automorphism of G determined by a. Note that if H ⊆ G is a subgroup then σ_a(H) = aHa⁻¹ is a conjugate of H.

Example 17. If G is any group and a G, show that

Solution. (1) We leave as Exercise 11 the verification that σ_a is a bijection for all a G. If g, h G we have

σ_a(g) · σ_a(h) = aga⁻¹ · aha⁻¹ = ag1ha⁻¹ = agha⁻¹ = σ_a(gh).

Hence σ_a is an automorphism of G, proving (1).

(2) We must show that σ_aσ_b = σ_ab for a, b G. But for any g G:

σ_aσ_b(g) = σ_a(bgb⁻¹) = a(bgb⁻¹)a⁻¹ = (ab)g(ab)⁻¹ = σ_ab(g).

(3) This follows from (2) and Corollary 2 of Theorem 1.

In Example 17, the group θ(G) of all inner automorphisms G is denoted

The group innG is an important subgroup of autG, and it is easily described because each inner automorphism σ_a is given explicitly in terms of a. By contrast, the group autG can be difficult to determine. We do one simple case in Example 18 below.

Because it is a homomorphism, every isomorphism preserves the unity, inverses, and powers. But isomorphisms also preserve the order of an element (compare with Corollary 1 of Theorem 1).

Theorem 4. Let σ: G → G₁ be an isomorphism. Then o(σ(g)) = o(g) for all g G.

Proof. It suffices to show that g^k = 1 if and only if [σ(g)]^k = 1. If g^k = 1, then [σ(g)]^k = σ(g^k) = σ(1) = 1 by Theorem 1. Conversely, if [σ(g)]^k = 1, we have σ(g^k) = [σ(g)]^k = 1 = σ(1), so g^k = 1 because σ is one-to-one.

Example 18. If G is cyclic of order 6, show that autG = {1_G, λ}, where λ(g) = g⁻¹ for all g G.

Solution. Both 1_G and (as G is abelian) λ are automorphisms of G. If σ: G → G is any automorphism, we show σ = 1_G or σ = λ. Write where o(a) = 6. Theorem 2 shows that the choice of σ(a) completely determines σ. By Theorem 4, we have o(σ(a)) = o(a) = 6, so σ(a) = a, or σ(a) = a⁵ = a⁻¹. If g G, write g = a^k for some , so that

If σ(a) = a, this gives σ(g) = a^k = g for all g G, that is σ = 1_G. If σ(a) = a⁻¹, it shows that σ(g) = (a⁻¹)^k = (a^k)⁻¹ = g⁻¹ for all g G, that is σ = λ.

Cayley's Theorem

We conclude this section with a proof of a theorem of Cayley (proved in 1878) that every finite group is isomorphic to a group of permutations. If X is a nonempty set, recall that S_X denotes the group of all permutations of X (bijections X → X) under composition. We need one simple observation about these permutation groups: If a bijection σ: X → Y exists then S_X S_Y. Indeed, if λ S_X we have

so σλσ⁻¹ S_Y. But then : S_X → S_Y given by (λ) = σλσ⁻¹ is an isomorphism, as can be readily verified. In particular, S_X S_n whenever |X| = n.

Now let G be a group. We noted earlier that each row of the Cayley table of G is a permutation of G in the sense that each element appears exactly once. Since the row of a G is {ag g G}, this is just the assertion that g ag is a bijection G → G. This is the connection that Cayley noticed between the groups G and S_G.

Theorem 5. Cayley's Theorem. Every group G of order n is isomorphic to a subgroup of S_n.

Proof. By the preceding discussion, there is an isomorphism θ: S_G → S_n. So if we can find a one-to-one homomorphism σ: G → S_G, then G θσ(G) ⊆ S_n because θσ: G → θσ(G) is an isomorphism, and Cayley's theorem follows.

If a G, define μ_a: G → G by μ_a(g) = ag for all g G. Then it is easy to verify that μ_a is a bijection (so μ_a S_G). Hence define θ: G → S_G by σ(a) = μ_a for all a G. Then θ is a homomorphism because μ_ab = μ_aμ_b for all a, b G (verify). Finally, θ is one-to-one because μ_a = μ_b implies that a = μ_a(1) = μ_b(1) = b. So σ is a one-to-homomorphism, as required.

Cayley's theorem shows that every abstract group of order n is (up to isomor-phism) a subgroup of S_n. Hence, to study the groups of order n, we need only study the symmetric group S_n. At first this approach seems to be an advantage because S_n consists of concrete mappings that can be analyzed using tools (such as cycle factorization and parity) not available in an abstract group. However, these symmetric groups are extremely large, so a subgroup of order n is lost in S_n (for example, |S₁₀| = 10 ! = 3, 628, 800). However, in Section 8.3 we give a generalization of Cayley's theorem that cuts down the size of the symmetric group and so provides more information about G.

Arthur Cayley (1821–1895)  Cayley showed his mathematical talent at an early age, quickly excelling at school. After some initial reluctance, his merchant father sent him to Cambridge at the age of 17. During the following 8 years he read the works of the masters and published more than 20 papers on topics that would occupy him for the rest of his life. In addition, he developed broad interests in literature (he read Greek, German, and French, as well as English), architecture, and painting (he demonstrated talent in watercolors) and became an enthusiastic hiker and mountaineer.

At the age of 25, with no position as a mathematician in view, he began legal training and was admitted to the bar three years later. He earned a comfortable living as a lawyer but resisted the temptation to make a lot of money so as to free himself to do mathematics. And do it he did, publishing nearly 300 papers in 14 years. Finally, in 1863, he accepted the Sadlerian professorship at Cambridge and remained there for the rest of his life, valued for his administrative and teaching skills, as well as for his scholarship.

Although Cayley introduced the concept of an abstract group, his main accomplishments lay elsewhere. With his lifelong friend J. J. Sylvester, he founded the theory of invariants; he was one of the first to consider geometry of more than three dimensions; and he initiated matrix algebra. He also wrote on quaternions, the theory of equations, dynamics, and astronomy. He continued working until his death, leaving 966 papers filling 13 volumes of 600 pages each.

Exercises 2.5

2.6 Cosets and Lagrange's Theorem

He [Lagrange] would set to mathematics all the little themes on physical inquiries which his friends brought him, much as Schubert set to music any stray rhyme that took his fancy.

—Herbert Westron Turnbull

In this section we prove one of the most important theorems about finite groups, Lagrange's theorem, which asserts that the order of a subgroup of a finite group G is a divisor of |G|. This has far-reaching consequences as we shall see. The proof involves counting elements of G, and depends on the following basic notion.

Let H be a subgroup of a group G. If a G we identify two subsets of G:

We have H1 = H = 1H, so H is a right and left coset of itself. Also the fact that 1 H shows a Ha and a aH for all a. Of course, if G is abelian then Ha = aH for all a G and all subgroups H of G. However, this may not hold if G is not abelian (see Example 5 below).

Example 1. Let K₄ = {1, a, b, ab} be the Klein group where o(a) = o(b) = 2 and ab = ba. If H = {1, a}, find the cosets of H in K₄.

Solution. H1 = H and Ha = {a, a²} = {a, 1} = H too. Similarly, Hb = {b, ab} and Hab = {ab, a²b} = {ab, b} = Hb. Thus, there are exactly two cosets of H in K₄: H = {1, a} and Hb = {b, ab} = bH.

Note that the cosets H = {1, a} and {b, ab} form a partition³⁰ of K₄. This holds in general and, with the other properties in Theorem 1, makes finding cosets easier.

Theorem 1. Let H be a subgroup of a group G and let a, b G.

Proof. First, (1) is clear because 1 H and (2) follows from (3) with b = 1.

(3). If Ha = Hb then a Ha = Hb, say a = hb, h H. Hence ab⁻¹ = h H.

Conversely, suppose that ab⁻¹ H. Then ha = h(ab⁻¹)b Hb, so Ha ⊆ Hb. But ba⁻¹ = (ab⁻¹)⁻¹ H too, so Hb ⊆ Ha follows in the same way. Hence Ha = Hb.

(4) If a Hb then ab⁻¹ H so Ha = Hb by (3).

(5) If Ha ∩ Hb ≠ ∅, we show Ha = Hb. If x Ha ∩ Hb, then x Ha so Hx = Ha by (4). Similarly Hx = Hb, so Ha = Hx = Hb. This proves (5).

(6) If Ha ≠ Hb then Ha and Hb are disjoint by (5). In other words, the set of right cosets is pairwise disjoint. Moreover, each a G belongs to some right coset of H (in fact a Ha). This gives (6).

Corollary. The analogue of Theorem 1 for left cosets also holds. In particular, (3) becomes aH = bH if and only if b⁻¹a H. See Exercise 5.

Mnemonic. The condition in (3) that Ha = Hb if and only if ab⁻¹ H can be remembered by “ right multiplying” Ha = Hb by b⁻¹. Similarly, aH = bH if and only if b⁻¹a H can be recalled by “ left multiplying” by b⁻¹.

Example 2. Let where o(a) = 6. Find the right cosets of the subgroups and

Solution. We have H = H1 = {1, a³}. Thus a³ H so H = Ha³ by (4) of Theorem 1. In the same way Ha = {a, a⁴} = Ha⁴, and Ha² = {a², a⁵} = Ha⁵. This exhausts G so the cosets are

H = {1, a³}, Ha = {a, a⁴}, and  Ha² = {a², a⁵}.

Turning to K we find the partition in one step:

K = {1, a², a⁴} and  Ka = {a, a³, a⁵}.

In Example 2, the cosets of H (and those of K) do indeed partition G into pairwise disjoint cells, as Theorem 1(6) asserts. What is new here is that all the cosets of H have the same number of elements and, similarly, all the cosets of K have the same number of elements. This fact holds in general and lies at the heart of Lagrange's theorem, as we show shortly.

Example 3. Find all the right cosets of the subgroup in the additive group

Solution. The notation is additive, so the right coset of generated by a is For a = 0, we obtain the coset itself:

Now so it generates a new coset by Theorem 1:

We continue in this way, with 2 and 3 generating new cosets:

This is a complete list of cosets, because every integer has the form 4k + r, where the remainder r is 0, 1, 2, or 3.

Example 4. In the group give a geometrical description of the cosets of the circle group

Solution. Recall that is the unit circle. If then z = re^iθ, where r = |z| > 0 and Hence . In other words, is the circle with its center at the origin and radius r = |z|.

All these examples involve abelian groups so Ha = aH always holds. However, this does not hold in general as Example 5 shows.

Example 5. Let G = S₃ = {ε, σ, σ², τ, τσ, τσ²}, where σ³ = ε = τ² and στσ = τ. Find the right and left cosets of H = {ε, τ}.

Solution. As στ = τσ⁻¹ = τσ², the cosets are

Observe that Hσ ≠ σH and Hσ² ≠ σ²H in this case.

Note that, even though the right and left cosets of H may be different, they all have the same number of elements and there are the same number of them. This holds in general, even when the cosets are infinite sets.

Two sets X and Y are said to have the same cardinality if there is a bijection from one to the other, and in this case we write Of course if the sets are finite this means that they have the same number of elements, and this terminology is sometimes used for infinite sets too.

Lemma. Let H be a subgroup of a group G. Then

Proof. (1) |H| = |aH| since h ha is a bijection H → Ha. Similarly, |H| = |Ha|.

(2) We have Ha = Hb ab⁻¹ H a⁻¹H = b⁻¹H by Theorem 1 and its Corollary. So the map in (2) is well defined and one-to-one. It is clearly onto.

Part (2) of the Lemma shows that the sets of right and left cosets of a subgroup H of G have the same number of members (possibly infinite), and this common value has a name:

The index |G: H| of H in G is defined to be the number of distinct right (or left) cosets of H in G.

Note that a subgroup H can be of finite index in G even if both H and G are infinite (for example by Example 3).

The Lemma enables us to prove the single most important theorem about finite groups: It introduces numerical relations into the theory.

Theorem 2. Lagrange's Theorem. Let H be any subgroup of a finite group G.

(1) Then |H| divides |G|.

(2) The quotient is the index of H in G.

Proof. Write k = |G: H|, and let Ha₁, Ha₂, , Ha_k be the distinct right cosets of H in G. Then

which is a disjoint union by Theorem 1. By the Lemma, |Ha_i| = |H| for each i, so

This proves (1), and it also proves (2) because |G||H| = k = |G: H|.

Note that Lagrange's theorem shows that both the order and the index of a subgroup of a finite group G are divisors of |G|.

Lagrange's theorem has many important consequences.

Corollary 1. If G is a finite group and g G, then o(g) divides |G|.

Proof. The cyclic subgroup generated by g has o(g) = |H| by the Corollary to Theorem 3 §2.4. So Lagrange's theorem applies.

Note that the converse of Lagrange's theorem (and of Corollary 1) is false. For example, |A₄| = 12, but A₄ has no subgroup of order 6 and hence no element of order 6 (Exercise 34).

Corollary 2. If G is a group and |G| = n, then gⁿ = 1 for every g G.

Proof. If o(g) = m then m|n by Corollary 1, say n = qm for some But then gⁿ = (g^m)^q = 1^q = 1.

The next corollary will be referred to later, and illustrates how the numerical information in Lagrange's theorem can determine the structure of a finite group.

Corollary 3. If p is a prime, then every group G of order p is cyclic. In fact, for every element g ≠ 1 in G, so the only subgroups of G are {1} and G.

Proof. Let g ≠ 1 in G and write Then |H| divides |G| = p, so |H| = 1 or |H| = p. But |H| ≠ 1 because H contains both 1 and g ≠ 1, so |H| = p = |G|. This implies that H = G because G is finite. Finally, if K ≠ {1} is a subgroup of G, and 1 ≠ k K, then and so K = G.

Corollary 4. Let H and K be finite subgroups of a group G. If |H| and |K| are relatively prime, then H ∩ K = {1}.

Proof. As H ∩ K is a subgroup of both H and K, |H ∩ K| must divide both |H| and |K| by Lagrange's theorem. Since |H| and |K| are relatively prime, it follows that |H ∩ K| = 1. The Corollary follows.

Example 6. Let K ⊆ H ⊆ G be finite groups. If |G: K| is a prime, show that H = K or H = G.

Solution. By Lagrange's theorem, Since |G: K| is a prime, either |G: H| = 1 or |H: K| = 1; that is either H = G or H = K.

We showed earlier (Example 18 §2.2) that every group of order 4 = 2² is either cyclic or is isomorphic to the Klein group. In Example 7, Lagrange's theorem is used to give an analogous result for any prime p in place of 2.

Example 7. If G is a group and where p a prime, show that either G is cyclic or g^p = 1 for every element g G.

Solution. Assume that G is not cyclic. Then o(g) p², so o(g) = 1, p, or p². But o(g) ≠ p² because G is not cyclic, so o(g) is 1 or p. Either way g^p = 1.

Dihedral Groups

Recall (Example 8 §2.2) that the group S₃ can be presented as follows:

S₃ = {ε, σ, σ², τ, τσ, τσ²}, o(σ) = 3, o(τ) = 2, and στσ = τ.

In fact, we can take σ = (123) and τ = (12), but the point here is that the three conditions o(σ) = 3, o(τ) = 2, and στσ = τ are themselves sufficient to fill in the Cayley table of the group.

We now construct a family of groups D₂, D₃, . . ., D_n, . . . each presented in much the same way as S₃, and having D₃ S₃. We realize them as subgroups of the group of 2 × 2 invertible matrices with complex entries.

Let n ≥ 2 be fixed and let (an nth root of unity). Then in Consider the matrices:

in It is easy to verify that o(a) = n, o(b) = 2, and aba = b. This last equation shows that ab = ba⁻¹ = baⁿ⁻¹, and hence that the finite set

of matrices is closed under matrix multiplication (I is the 2 × 2 identity matrix). Hence G is a subgroup of by Theorem 2 §2.3. For convenience, write Then |A| = n and, as b ∉ A, the left cosets A and b A are disjoint. Hence |G| = 2n. We abstract this situation as follows.

If n ≥ 2, the dihedral group D_n is the group of order 2n presented as follows:

D_n = {1, a, a², . . ., aⁿ⁻¹, b, ba, ba², . . ., baⁿ⁻¹},

 where o(a) = n, o(b) = 2, and aba = b.

Note that the requirement that |D_n| = 2n is equivalent to insisting that We can carry out all calculations in D_n by using the conditions o(a) = n, o(b) = 2, and aba = b. The equation aba = b implies that a^kba^k = b for all by induction (Exercise 25), and so we obtain

a^kb = ba^−k = ba^n−k and o(ba^k) = 2 for all .

In particular, ab = baⁿ⁻¹, and these formulas enable us to fill in the Cayley table for D_n. Hence the conditions o(a) = n, o(b) = 2, and aba = b completely determine the group D_n (up to isomorphism). The group D₄ is called the octic group, and its Cayley table is as follows (the reader should verify this):

The group D₃ is isomorphic to S₃ because

D₃ = {1, a, a², b, ba, ba²}, o(a) = 3, o(b) = 2, and aba = b

which is the same as the presentation of S₃ given previously. If n = 2,

D₂ = {1, a, b, ba}, o(a) = 2, o(b) = 2, and aba = b.

We have a⁻¹ = a here because o(a) = 2, so D₂ is abelian (ba = a⁻¹b = ab) and is isomorphic to the Klein group K₄.

Thus, every group of order 4 is either cyclic or dihedral (Example 18 §2.2). The next theorem shows that this result holds for groups of order 2p where p is a prime.

Theorem 3. Let G be a group of order 2p where p is a prime. Then either G is cyclic or G D_p.

Proof. First, the theorem is true if p = 2 because implies G is cyclic or G K₄ D₂. Hence we assume that p is odd.

Assume that G is not cyclic. Hence o(g) = 1, 2, or p for every g G by Corollary 1 of Lagrange's theorem. We must show that G D_p.

Claim 1. G has an element of order p.

Proof. If not, g² = 1 for all g G, so G is abelian by Exercise 20 §2.2. Hence if 1, a, and b are distinct in G, then {1, a, b, ab} is a subgroup of order 4 by Theorem 2 §2.3, contrary to Lagrange's theorem. This proves Claim 1.

So let a G have order p and write

Claim 2. If x G and x ∉ H, then o(x) = 2.

Proof. We have G = H ∪ Hx so, because x² ∉ Hx, we must have x² H. If o(x) = p then, since p is odd, contrary to the choice of x. Thus o(x) ≠ p, so o(x) = 2 (x ≠ 1 because x ∉ H). This proves Claim 2.

Now choose b ∉ H. Then G = H ∪ bH, a disjoint union, so we obtain

G = {1, a, a², . . ., a^p−1, b, ba, ba², . . ., ba^p−1}.

As o(b) = 2 by Claim 2, it remains to show that aba = b. But ba ∉ H so (ba)² = 1 again by Claim 2. But then aba = b⁻¹(ba)² = b⁻¹ = b. Thus G D_p.

Theorem 3 together with Corollary 3 determines all groups G with |G| ≤ 7:

Note that K₄ C₂ × C₂, so every abelian group here is (isomorphic to) a direct product of cyclic groups. In fact this is true for every finite abelian group, an important result discussed in Chapter 7.

Obviously, the list continues. We will show that there are five nonisomorphic groups of order 8: C₈, C₄ × C₂, C₂ × C₂ × C₂, D₄, and another group Q called the quaternion group, to be introduced in Section 2.8. The groups of order 9 are C₉ and C₃ × C₃—both abelian,) and there are two distinct groups of order 10; C₁₀ and D₅. The next interesting case is the groups of order 12 (there are five). However, it is not our intention to imply that all the distinct groups of order n have been determined for an arbitrary integer n. That is a very difficult task!

We conclude with an application of Lagrange's theorem to number theory. If n ≥ 2, the Euler function is defined by

(n) is the number of integers k {1, 2, , n − 1} with gcd (k, n) = 1.

We define (1) = 1. Hence (2) = 1, (3) = 2, (4) = 2, (5) = 4, and (6) = 2. Clearly,

(p) = p − 1 whenever p is a prime.

Now recall (Theorem 5 §1.3) that, for n ≥ 2, the group of (multiplicative) units in is given by and gcd (k, n) = 1}. Hence

With this, Lagrange's theorem yields an elegant proof of the following famous result in number theory.

Theorem 4. Euler's Theorem. If a and n ≥ 2 are relatively prime integers, then a⁽ⁿ⁾ ≡ 1 (modn).

Proof. We have Since Lagrange's theorem (Corollary 2) gives in Euler's theorem follows.

A special case gives another proof of Fermat's theorem (Theorem 8 §1.3).

Corollary. Fermat's Theorem. If p is a prime, then a^p ≡ a(modp) for all integers a.

Proof. This is clear if a ≡ 0 (modp). Otherwise, a and p are relatively prime so, because (p) = p − 1, Euler's theorem gives a^p−1 ≡ 1 (modp). Fermat's theorem follows.

Joseph Louis Lagrange (1736–1813)  While his name sounds French, Lagrange was born in Italy and spent his early years in Turin. In 1766, he was appointed as Euler's successor at the Berlin Academy by Frederick the Great, who suggested that the “ greatest mathematician in Europe” should be at the court of the “ greatest king in Europe.” After the death of Frederick, Lagrange went to Paris at the invitation of Louis XVI. He remained there throughout the revolution and was made a count by Napoleon who called him the “ lofty pyramid of the mathematical sciences.”

Lagrange was one of the great mathematicians of all time. He made important contributions to many parts of mathematics, including number theory, the theory of equations, differential equations, celestial mechanics, and fluid dynamics. At age 19 he solved a famous problem, the so-called isoperimetrical problem, by inventing an entirely new method, known today as the calculus of variations. His work brought a new level of rigor to analysis. In addition to his mathematical achievements, he was a master of exposition, and his Mechanique Analytique is a masterpiece that William Rowan Hamilton described as a “ scientific poem,”.

In his work on the theory of polynomial equations, Lagrange studied the permutations of the roots of an equation in the hope of finding a general method of solution. He saw that, because the symmetric groups S₂, S₃, and S₄ were sufficiently “ nice” a general solution can always be found if the degree is 2, 3, or 4. But he never discovered what it was about S₅ that obstructed the solution of equations of degree 5. Abel, and later Galois, eventually clarified the matter. Nevertheless, Lagrange's work provided one of the sources from which the modern theory of groups evolved.

Exercises 2.6

2.7 Groups of Motions and Symmetries

Group theory began with the study of subgroups of the symmetric group S_n. In this short section we discuss some of these groups, which arise from the symmetries of geometric figures. By a figure we mean a finite set of points called vertices, some pairs of which are joined by line segments. A motion of a geometric figure is a permutation of its vertices that can be realized by a rigid motion in space.

Given two motions σ and τ of a figure, the composite στ is also a motion obtained by first doing τ and then σ. Similarly, σ⁻¹ is a motion achieved by reversing the motion that led to σ. Finally, the identity permutation ε is a motion (resulting from doing nothing at all). Hence the subgroup test gives Theorem 1.

Theorem 1. The set of motions of a figure with n vertices is a subgroup of S_n.

This theorem leads to many interesting groups.

Example 1. Find the group of motions of a (nonsquare) rectangle.

Solution. Label the vertices as shown. Then the motions (1 2)(3 4) and (1 4)(2 3) result from rotating the rectangle π radians (180) about the vertical and horizontal axes of symmetry, respectively. The composite of these is (1 3)(2 4), which is the motion obtained by a rotation of 180 in the plane of the rectangle. Hence

G = {ε, (12)(34), (14)(23), (13)(24)}

is the group of motions. This group is isomorphic to the Klein group.

Example 2. Find the group of motions of an equilateral triangle.

Solution. Label the vertices as shown. The motions σ = (1 2 3) and σ² = (1 3 2) are achieved by clockwise rotations of 2π/3 radians (120) and 4π/3 radians (240), respectively. In addition, τ = (1 2) is realized by rotating the triangle π radians (180) about the line through vertex 3 and the midpoint of the opposite side. Similarly (1 3) and (2 3) are motions, so the group is

S₃ = {ε, (1 2 3), (1 3 2), (1 2), (1 3), (2 3)}.

This shows that the equilateral triangle is highly symmetric because every possible permutation of the vertices can be obtained by a rigid motion in space.

It is vital that the rigid motions allowed in Example 2 are rigid motions in space. If the only motions allowed were those in the plane of the triangle, the group of motions would be {ε, (1 2 3), (1 3 2)}. The permutations (1 2), (1 3), and (2 3) cannot be achieved by rigid motions in the plane of the triangle.

A striking illustration of this phenomenon results when we consider the group G of motions of a tetrahedron. This figure is three-dimensional, with four vertices and six edges of equal length as in the diagram. Clearly (123) is a motion of the tetrahedron, obtained by a rotation of 2π/3 radians (120) about a line through vertex 4 and the center of the opposite face. Similarly, all 3 cycles are in G. The three permutations (1 2)(3 4), (1 3)(2 4), and (1 4)(2 3) are also motions, so A₄ ⊆ G, where A₄ is the alternating group of all even permutations:

We claim that A₄ = G. Suppose on the contrary that σ G is an odd motion. If γ = (1 2), write τ = γσ. Then τ is even so τ G and hence γ = τσ⁻¹ is in G because G is a group. But the transposition γ = (1 2) is not a motion of the tetrahedron, because interchanging vertices 1 and 2 by a rigid motion necessarily interchanges 3 and 4. It follows that

Example 3. The group of motions of the tetrahedron is A₄.

This situation is analogous to that for the equilateral triangle in Example 2, where the group of motions is A₃ = {ε, (1 2 3), (1 3 2)} if the motions are restricted to the plane containing the triangle. Any odd permutation is achieved as a motion only if the triangle is pulled out of its plane, flipped over, and placed back in its plane. Similarly, no odd permutation of the vertices of a tetrahedron can be realized by a motion in 3-space. It can be achieved only if the figure is “ moved” into 4-space in the process.

Even so, these odd permutations of the vertices of a tetrahedron are symmetries of the figure in the intuitive sense of the word. To make this precise, we let d(x, y) denote the distance between two points x and y in space. As in Section 1.4, if σ S_n, we write σ(k) = σk for all integers k. Given a geometric figure with n vertices labeled 1, 2, , n, a symmetry of the figure is a permutation σ of the vertices that preserves the distance between any two vertices; that is

Clearly, any motion of a figure is a symmetry, but the converse is not true. For example, the transposition γ = (12) is a symmetry of the tetrahedron, but it is not a motion, as we have demonstrated.

Theorem 2. The symmetries of a figure with n vertices are a subgroup of S_n.

Proof. The identity permutation is clearly a symmetry. If σ and τ are symmetries, then for vertices k and m we have

d[(στ)k, (στ)m] = d[σ(τk), σ(τm)] = d(τk, τm) = d(k, m).

Hence στ is a symmetry. Finally, write σ⁻¹k = k₁ and σ⁻¹m = m₁. Then k = σk₁ and m = σm₁ so, since σ is a symmetry,

This shows that σ⁻¹ is a symmetry and so completes the proof.

Now let G denote the group of symmetries of the tetrahedron. Then Example 3 gives A₄ ⊆ G ⊆ S₄, and A₄ ≠ G because (12) G. This implies that G = S₄ because |S₄: A₄| = 2 is a prime (see Example 6 §2.6). Hence

Example 4. The group of symmetries of the tetrahedron is S₄.

The group of motions (in 3-space) of a geometric figure is thus a subgroup of the group of symmetries, and the two may be distinct as the tetrahedron shows. However, if the figure can be drawn in a plane, the two groups coincide. The reason comes from a theorem of plane geometry. Call a mapping σ from the plane to itself an isometry if it preserves distance; that is if d[σ(x), σ(y)] = d(x, y) for all x and y. It can be shown that every isometry of the plane is a composite of translations, rotations about a point, and reflections in a line. Translations and rotations result from motions in the plane itself, whereas reflections can only be achieved by motions in 3 -space. Thus, every isometry of the plane (and hence every symmetry of a plane figure) is a motion in 3-space. Of course, this condition breaks down for a three-dimensional figure because reflections in a plane are isometries of 3-space that are not motions of 3-space.

We conclude this section by representing the dihedral group D_n as a group of motions. If n ≥ 3, a regular n -gon is a plane figure with n vertices evenly placed on a circle. Thus, a regular 3-gon is an equilateral triangle, a regular 4-gon is a square, and so on. Consider the group G of all motions of a regular n-gon. There are two obvious motions:

If n is odd, then τ fixes only the vertex n, whereas if n = 2m, then τ fixes n and m (see Figure 2.1). If λ is any motion of the n-gon, λ is determined by its effect λ1 and λ2 on vertices 1 and 2. If λ2 follows λ1 (clockwise round the n-gon) then λ = σ^k for some k. On the other hand, if λ2 precedes λ1, then λ = τσ^k for some k. For example, if n = 7 and the effect of λ is that shown in Figure 2.2, then λ can be achieved by τσ⁴ as shown in Figure 2.3.

Because |σ| = n and |τ| = 2, it follows that

Thus so |G| = 2n. Moreover, the relation στσ = τ is valid as the following diagram shows.

Because |σ| = n, |τ| = 2, and στσ = τ, the definition of D_n (in § 2.6) proves

Theorem 3. The group of motions of a regular n-gon is isomorphic to D_n.

If n = 3, Theorem 3 shows that the group of motions of an equilateral triangle is isomorphic to D₃, as is clear from Example 2. If n = 4, it shows that the group of motions of the square is isomorphic to the octic group D₄.

Exercises 2.7

2.8 Normal Subgroups

If H is a subgroup of a group G, we have seen that aH = Ha may fail to hold for some a G (Example 2 below). A subgroup H of a group G is called a

normal subgroup of G if gH = Hg holds for all g in G.

In this case H is said to be normal in G, written H G. These subgroups are of fundamental importance in group theory, and in this section we begin to see why.

Example 1. If G is any group, {1} G because g{1} = {g} = {1}g, and G G because gG = G = Gg for all g G.

Example 2. Let S₃ = {ε, σ, σ², τ, τσ, τσ²}, where o(σ) = 3, o(τ) = 2, and στσ = τ. If H = {ε, σ, σ²} and K = {ε, τ}, show that H S₃ but that K/ S₃.

Solution. Clearly, αH = H = Hα for all α H. Because στ = τσ² and σ²τ = τσ, we get

Hτ = {τ, στ, σ²τ} = {τ, τσ², τσ} = τH.

Similarly, Hτσ = τσH and Hτσ² = τσ²H, so H S₃.

However, σK = {σ, στ} and Kσ = {σ, σ²τ}, so σK ≠ Kσ. Hence K/ S₃.

Let H be a subgroup of a group G. If g G satisfies gh = hg for all h H, then obviously gH = Hg. In particular, this condition holds if each element h of H is in the center Z(G) of G. This proves Theorems 1 and 2.

Theorem 1. If G is a group, every subgroup of the center Z(G) is normal in G. In particular, Z(G) G.

Theorem 2. If G is an abelian group, every subgroup of G is normal in G.

Note that, given g G, it is not necessary that gh = hg for all h H to ensure that gH = Hg. For example, to show that gH ⊆ Hg it is only necessary to show that, given h H, gh = h′g for some h′ H.

The converse of Theorem 1 is false: The subgroup H in Example 2 is normal in S₃, but H is certainly not central in S₃ (in fact, Z(S₃) = {ε}). The converse of Theorem 2 is also false: Example 9 below exhibits a nonabelian group in which every subgroup is normal.

Example 3. If K = {ε, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}, show that K A₄.

Solution. If σ S_n and γ = (k₁k₂ k_r) is a cycle of length r, then σγσ⁻¹ is also a cycle of length r, in fact σγσ⁻¹ = (σk₁σk₂ σk_r)—see Lemma 3 below. With this, let (ab)(cd) K. If σ S₄, then

σ[(ab)(cd)]σ⁻¹ = σ(ab)σ⁻¹ σ(cd)σ⁻¹ = (σaσb) (σcσd) K.

It follows that K S_n, so certainly K A₄.

Theorem 3. Normality Test. The following conditions are equivalent for a subgroup H of a group G.

Proof. (1) ⇒ (2). Let x gHg⁻¹, say x = ghg⁻¹. Then gh gH = Hg by (1), say gh = h₁g. Then x = ghg⁻¹ = h₁gg⁻¹ = h₁ H. This proves (2).

(2) ⇒ (3). If g G then gHg⁻¹ ⊆ H by (2). Taking g⁻¹ in place of g in (2), we obtain g⁻¹Hg ⊆ H. This implies H ⊆ gHg⁻¹ (verify), so H = gHg⁻¹, proving (3).

(3) ⇒ (1). Given g G, we have gHg⁻¹ = H by (3). If x gH, this shows that xg⁻¹ H, so x Hg. This proves gH ⊆ Hg. Since g⁻¹Hg = H by (3) (with g⁻¹ replacing g), a similar argument shows that Hg ⊆ gH. Now (1) follows.

Conditions (2) and (3) in Theorem 3 become even more useful if G has a known set X of generators (see Theorem 10 §2.4). The proof is Exercise 13.

Corollary 1. If , a subgroup H is normal in G if and only if xHx⁻¹ ⊆ H for all x X. In particular, if and only if for all g G.

If H is a subgroup of G and g G, recall (Theorem 5 §2.3) that gHg⁻¹ is also a subgroup of G which is isomorphic to H,³¹ and is called a conjugate of H in G. For this reason, normal subgroups of G are sometimes called self-conjugate subgroups. Incidentally, this discussion proves

Corollary 2. If H is a subgroup of G, and if G has no other subgroups isomorphic to H, then H is normal in G.

In particular, if H is finite and H is the only subgroup of its order, then H G because |gHg⁻¹| = |H| for all g G.

Theorem 3 suggests a stronger condition than normality. A subgroup H of a group G is called a characteristic subgroup of G if σ(H) = H for all automorphisms σ: G → G (equivalently if σ(H) ⊆ H for all automorphisms σ). The center Z(G) is characteristic in G, and other examples are given in Exercise 24. If σ = σ_a is the inner automorphism induced by a G then aHa⁻¹ = σ_a(H), and it follows that characteristic subgroups are necessarily normal. However, the converse is false by Exercise 24 (c). The following result is often useful.

Corollary 3. If K G and H ⊆ K is characteristic in K, then necessarily H G.

Proof. If a G, σ_a: K → K is an automorphism of K because K G. It follows that σ_a(H) = H because H is characteristic in K. Hence K G.

Corollary 3 fails if H is merely normal in K (Exercise 4). Many important subgroups are characteristic subgroups (for example, the center); some of their properties are given in Exercise 24.

Example 4. Let and let H be the subgroup of all matrices with determinant 1. Show that H G.

Solution. If A G and B H, the properties of determinants give

This shows that ABA⁻¹ H, so H is normal in G by part (2) of Theorem 3.

Theorem 4. If H is a subgroup of index 2 in G, then H is normal in G.

Proof. Let a G. If a H, then Ha = H = aH. If a ∉ H then (because H has exactly 2 right cosets) G = H ∪ Ha, a disjoint union. Hence Ha = G H. Similarly aH = G H as H has two left cosets, so Ha = G H = aH. Thus, H G.

Note that subgroups of index 3 need not be normal (Example 2).

Example 5. Show A_n S_n where A_n is the alternating group.

Solution. The alternating group A_n is of index two in S_n (Theorem 8 §1.4).

Example 6. Let D_n = {1, a, a², , aⁿ⁻¹, b, ba, ba², , baⁿ⁻¹} denote the dihedral group, where o(a) = n, o(b) = 2, and aba = b. Then by Theorem 4 because has index 2 in D_n.

We defined H G to mean gH = Hg for all g G, which is a kind of commutativity condition on H. The next result gives a situation where actual commuting of elements is implied. It will be referred to later.

Lemma 1. Let H G and K G. If H ∩ K = {1}, then hk = kh for all elements h H and k K.

Proof. Consider x = hkh⁻¹k⁻¹. Thinking of x = h(kh⁻¹k⁻¹) we see that x H because kh⁻¹k⁻¹ kHk⁻¹ = H since H G. Similarly, writing x = (hkh⁻¹)k⁻¹ shows that x K because K G. Hence x H ∩ K = {1} by hypothesis, so x = 1. But then hkh⁻¹k⁻¹ = 1, which gives hk = kh.

Let H and K be subgroups of a group G. The intersection H ∩ K is the largest subgroup of G contained in both H and K (it contains any such subgroup), and one wonders if there is a smallest subgroup of G containing both H and K. Note that, while H ∪ K is the smallest subset containing H and K, it is a subgroup only if H ⊆ K or K ⊆ H (see Exercise 17 §2.3). A much more useful construction turns out to be the product HK of the subgroups defined as follows:

HK = {hk h H, k K}.

Then HK contains both H and K, and is contained in any such subgroup, but HK need not be a subgroup (consider H = {ε, τ} and K = {ε, τσ} in S₃ with the usual notation). However we do have the following result.

Lemma 2. The following are equivalent for subgroups H and K of a group G:

Proof. We prove only (1) (2); then (1) (3) follows by interchanging H and K.

(1) ⇒ (2). If kh KH, then kh = (h⁻¹k⁻¹)⁻¹ HK by (1). This shows that KH ⊆ HK. On the other hand, if hk HK then k⁻¹h⁻¹ = (hk)⁻¹ HK by (1), say k⁻¹h⁻¹ = h₁k₁. Hence so HK ⊆ KH.

(2) ⇒ (1). We use the subgroup test. Clearly 1 = 1 · 1 HK always holds. If hk HK then (hk)⁻¹ = k⁻¹h⁻¹ KH = HK by (2). Finally, given hk and h₁k₁ in HK, we have kh₁ KH = HK, say kh₁ = h₂k₂. But then it follows that (hk)(h₁k₁) = h(h₂k₂)k₁ = (hh₂)(k₂k₁) HK, which completes the proof of (1).

A note of caution is needed here: To say that HK = KH does not mean that hk = kh for all h H and k K. To show that HK ⊆ KH means that, if h H and k K are given, then hk = k₁h₁ for some h₁ H and k₁ K.

If G is abelian then HK is certainly a subgroup by Lemma 2. There is more:

Theorem 5. Let H and K be subgroups of a group G.

Proof. (1) Suppose that K is normal in G. If hk HK then hk = (hkh⁻¹)h KH because hkh⁻¹ hKh⁻¹ = K. Hence HK ⊆ KH. The other inclusion is proved the same way, so Lemma 2 applies. A similar argument works if H G.

(2) If g G and hk HK, then g⁻¹(hk)g = (g⁻¹hg)(g⁻¹kg) HK because H G and K G. This proves (2).

Many groups arise as direct products of groups of smaller order, and the following useful theorem gives an important way to recognize when this is the case.

Theorem 6. If H G and K G satisfy H ∩ K = {1}, then HK H × K.

Proof. First, HK is a subgroup of G by Theorem 5. Define

σ: H × K → HK by σ(h, k) = hk for all h H and k K.

We show that σ is an isomorphism. Given (h, k) and (h₁, k₁) in H × K, we have h₁k = kh₁ by Lemma 1, so σ is a homomorphism because

σ[(h, k) · (h₁, k₁)] = σ(hh₁, kk₁) = hh₁ kk₁ = hk h₁k₁ = σ(h, k) · σ(h₁, k₁).

Since σ is clearly onto, it remains to show that σ is one-to-one. If σ(h, k) = σ(h₁, k₁), then hk = h₁k₁ so Thus so h = h₁ and k = k₁. But then (h, k) = (h₁k₁), proving that σ is one-to-one.

The map σ in Theorem 6 is a bijection for any subgroups H and K. Hence

Corollary 1. If G is a finite group, and H and K are subgroups with H ∩ K = {1}, then

Corollary 2. Let G be a finite group and let H and K be normal subgroups such that H ∩ K = {1} and |H| |K| = |G|. Then G H × K.

Proof. By Corollary 1, we have Hence G = HK because HK ⊆ G and G is finite, so Theorem 6 applies.

Examples 7 and 8 below illustrate how to use Theorem 6. It is easy to verify that the direct product of two cyclic groups of relatively prime orders is again cyclic (Exercise 25 §2.4). Example 7 is the converse. Recall that C_n denotes the generic cyclic group of order n.

Example 7. Let m and n be relatively prime positive integers. If G is a cyclic group of order mn, show that G C_m × C_n.

Solution. Let where o(a) = mn, and write and Then |H| = o(aⁿ) = m and |K| = o(a^m) = n, so H C_m and K C_n. Moreover, H ∩ K = {1} by Lagrange's theorem (Corollary 4). Also, H G and K G because G is abelian, and |H| · |K| = mn = |G|. Hence G H × K by Corollary 2 of Theorem 6, that is G C_m × C_n by Example 13 §2.5.

The fundamental theorem of finite abelian groups asserts that every finite abelian group is isomorphic to a uniquely determined direct product of cyclic groups. We prove this assertion in Section 7.2. Example 8 gives a special case.

Example 8. Let G be an abelian group and assume that p a prime. Then either is cyclic or G C_p × C_p.

Solution. Assume that G is not cyclic. Then o(g) = p if 1 ≠ g G because o(g) divides p². Choose a G with o(a) = p, and write Then H ≠ G, so choose b ∉ H, b G, and write Hence |K| = p too, so we have Moreover H G and K G because G is abelian. Finally, H ∩ K = {1} because, otherwise, H = H ∩ K = K by Corollary 3 of Lagrange's theorem. Thus G H × K by Corollary 2 of Theorem 6, that is G C_p × C_p.

We have already noted (Theorem 2) that every subgroup of an abelian group is normal. The converse is not true: A nonabelian group of order 8 exists in which every subgroup is normal. It is constructed as follows: Let

Q = { ± 1, ±i, ±j, ±k}

be a set of eight elements with multiplication determined by the following equations:

Here 1 and −1 multiply as usual, and the multiplication of i, j, and k is best remembered by the diagram above: The product of any two of i, j, and k taken clockwise around the circle is the next one, whereas the product counterclockwise is the negative of the next one. One realization of Q is in where, if satisfies we take

The group Q in the preceding discussion is called the quaternion group, and it rules out the converse to Theorem 2.

Example 9. Show that Q is a nonabelian group in which every subgroup is normal.

Solution. Q is nonabelian because ij = k while ji = − k. If a subgroup H contains one of ±i, ±j, or ±k, then |H| = 4 or 8 (because these elements have order 4), so H Q by Theorem 4. Otherwise, H ⊆ {1, − 1} ⊆ Z(Q) and again H Q.

Simple Groups

Lagrange's theorem shows that the cyclic groups G of prime order have no subgroups except {1} and G. More generally, if G is a group then we say that

G is simple if G ≠ {1} and the only normal subgroups of G are {1} and G.

Theorem 7. An abelian group G ≠ {1} is simple if and only if it is cyclic of prime order.

Proof. Suppose G is simple and abelian. Then the only subgroups of G are {1} and G (all subgroups are normal). If a G, a ≠ 1, this means that Then o(a)≠ ∞ because, otherwise, does not equal {1} or G. So o(a) is finite, say o(a) = n ≥ 2. If p|n for some prime p, then is a subgroup of order p by Theorem 5 §2.4. Hence is cyclic of prime order.

The converse is by Lagrange's theorem.

Nonabelian finite simple groups are more difficult to find. We conclude with a proof that, although A₄ is not simple by Example 3, the alternating groups A_n are all simple if n ≥ 5. This has applications in the theory of equations (Chapter 10). The proof requires three preliminary results, the first two of independent interest.

Lemma 3. If σ S_n and γ = (k₁ k₂ k_r) is a cycle of length r, then σγσ⁻¹ is also a cycle of length r. In fact, σγσ⁻¹ = (σk₁ σk₂ σk_r).

Proof. Write δ = (σk₁σk₂ σk_r). Because σ is one-to-one, δ is a cycle of length r. We must show that σγσ⁻¹ = δ, that is σγ = δσ, that is σ(γk) = δ(σk) for each k = 1, 2, . . ., n. The reader can verify that (writing k_r+1 = k₁)

σ(γk_i) = σk_i+1 = δ(σk_i) for each i = 1, 2, . . ., r.

But σ(γk) = σk = δ(σk) whenever k ∉ {k₁, k₂, , k_r}because (as σ is one-to-one) this implies that σk ∉ {σk₁, σk₂, , σk_r}. This is what we wanted.

Lemma 4. If n ≥ 2, A_n is generated by the 3-cycles.

Proof. As each 3-cycle is in A_n, it suffices to show that each permutation σ A_n is either ε or a product of 3-cycles. But σ is even and so is a product of pairs of transpositions. Hence the following formulas complete the proof:

(i j)(i j) = ε, (i j)(i k) = (i k j), and (i j)(k l) = (i l k)(i j k).

Lemma 5. Suppose that n ≥ 5. If H A_n and H contains a 3-cycle, then H = A_n.

Proof. If (i j k) H we claim that (a j k), (i a k) and (i j a) are all in H for any a ∉ {i, j, k}. Indeed: Since n ≥ 5, choose b ∉ {a, i, j, k}. Then we have (a j k) = (i a b)(i j k)(i a b)⁻¹ H by Lemma 3. Similarly, (i a k), (i j a) H.

Let σ = (1 2 3) H: by Lemma 4 we must show that every 3-cycle τ = (i j k) is in H. Write S = {1, 2, 3} and T = {i, j, k}. If then S = T so τ = σ H or τ = σ⁻¹ H. If say i = 1, j = 2 and k ≠ 3, then (1 2 3) H ⇒ τ = (1 2 k) H by the first paragraph. If say i = 1 and {2, 3} ∩ {j, k} = ∅, then (1 2 3) H ⇒ (1 j 3) H ⇒ τ = (1 j k) H. Finally if then (1 2 3) H ⇒ (i 2 3) H ⇒ (i j 3) H ⇒ τ = (i j k) H.

Theorem 8. If n ≥ 5, the alternating group A_n is simple.

Proof. Let H A_n, H ≠ {ε}. Among all elements of H (excluding ε) let τ be one that moves the smallest number m of integers. Then m ≥ 3, because τ A_n is not a transposition. If m = 3 then τ is a 3-cycle, and we are done by Lemma 5. So assume m≥ 4; we show that this leads to a contradiction. Factor τ into disjoint cycles and consider two cases.

• Case 1: τ contains a cycle of length ≥ 3, say τ = (1 2 3 )γ₂ γ_r. If τ moves exactly 4 integers, then τ = (1 2 3 k) is odd. So assume that τ moves (say) 4 and 5, as well as 1, 2, and 3. Let β = (3 4 5) and write τ₁ = τ⁻¹βτβ⁻¹. Then τ₁ H because H A_n, and τ₁ ≠ ε because τ₁2 = τ⁻¹4 ≠ 2. Moreover, if k > 5 is fixed by τ, then k is also fixed by τ₁ (because βk = k). Hence if τ₁ moves k > 5, then τ also moves k. But τ₁ fixes 1, whereas τ does not. Thus τ₁ moves fewer elements than τ, a contradiction.
• Case 2: τ is a product of disjoint transpositions, say, τ = (1 2)(3 4) . As before, let β = (3 4 5) and τ₁ = τ⁻¹βτβ⁻¹. Now τ₁ fixes 1 and 2 and any integer k > 5 that is fixed by τ. Because τ₁ ≠ ε (for example, τ₁5 = 3), this is a contradiction, as in Case 1.

Other infinite families of finite simple groups exist (in addition to the alternating groups A_n, n ≥ 5). The complete classification of these groups was first given in 1981. This was the culmination of more than 30 years of effort by hundreds of mathematicians, yielding thousands of pages of published work. It is certainly one of the greatest achievements of twentieth-century mathematics. One spectacular landmark came in 1963 when J. Thompson and W. Feit proved³² a long-standing conjecture of William Burnside that every finite nonabelian simple group has even order (the proof is more than 250 pages long!). Thompson went on to publish the “ N -group” paper in which he introduced many fundamental techniques, and which has been called the single most important paper in simple group theory.³³ Then in the 1970s, M. Aschbacher carried the work forward in a series of papers, building on the methods of Thompson. The main difficulty was the existence of sporadic finite simple groups not belonging to any of the known families. R. L. Griess finally constructed the largest of these, called the monster (the order is approximately 8 × 10⁵³). The complete classification encompasses several infinite families of finite simple groups and exactly 26 sporadic groups.³⁴

Exercises 2.8

2.9 Factor Groups

If n ≥ 2, recall the construction of in Section 1.3. Given the subgroup of the set consists of all “ residue classes” (mod n)} where These classes are really cosets Moreover, we defined addition in by that is,

This suggests a general definition: If K is a subgroup of a multiplicative group G, we could define an analogous multiplication on the set of right cosets by

However, this may not make sense for some subgroups K because cosets can have different generators: Ka = Ka₁ can happen where a and a₁ may not be equal.

More precisely, let x = Ka = Ka₁ and y = Kb = Kb₁ be cosets. If we multiply x = Ka and y = Kb using (*) we get xy = Kab, but if we view x and y as x = Ka₁ and y = Kb₁ we obtain xy = Ka₁b₁. Clearly, what is needed is:

In this case we say that the multiplication Ka Kb = Kab is well defined. This condition on K is equivalent to K being normal in G.

Lemma. The following conditions are equivalent for a subgroup K of G.

Proof. (1) ⇒ (2). If K G, let Ka = Ka₁ and Kb = Kb₁, that is and We must show that Kab = Ka₁b₁, that is ab(a₁b₁)⁻¹ K. Compute

because aKa⁻¹ ⊆ K. This is what we wanted.

(2) ⇒ (1). If a G we must show that aka⁻¹ K for all k K. Clearly Ka = Ka and Kk = K1, so applying (2) gives Kak = Ka1, that is Kak = Ka. But then (ak)a⁻¹ K, as required.

Theorem 1. Let K G and write G/K = {Ka a G} for the set of cosets.

Proof. (1) The operation on G/K is well defined by the Lemma. The unity of G/K is K = K1 because Ka K1 = Ka = K1 Ka for all Ka in G/K. We have Ka Ka⁻¹ = K1 = Ka⁻¹ Ka, so the inverse of the coset Ka is (Ka)⁻¹ = Ka⁻¹. Finally, associativity in G/K is inherited from G:

(2) We have (a) (b) = Ka Kb = Kab = (ab) for all a, b G, so is a homomorphism. It is clearly onto.

(3) If G is abelian, Ka Kb = Kab = Kba = Kb Ka, proving (3).

(4) Let so every coset in G/K has the form Ka^k for some integer k. If is the map in (2), then Ka^k = (a^k) = (a)^k = (Ka)^k by Theorem 1 §2.5. It follows that as required.

(5) As |G: K| is finite, |G/K| = |G: K| is the definition of the index |G: K|. If is finite, then |G/K| = |G|/|K| is (2) of Lagrange's theorem.

Thus, if n ≥ 2 in then as additive groups. If K is a normal subgroup of a group G, write G/K = {Ka a G} as in Theorem 1. We make two definitions:

The group G/K of all cosets of K in G is called the factor group of G by K.

The homomorphism : G → G/K where (a) = Ka is called the coset map.

Hence the unity of G/K is K = K1, and inverses are given by (Ka)⁻¹ = Ka⁻¹. It is important for a student of group theory (and ring theory for that matter) to develop skill in working with factor groups. All the group theoretic techniques we have developed up to now apply to these groups; the only new aspect is that the elements are now cosets.

Example 1. If G is a group then we always have G G and {1} G.

If K = G there is only one coset, so G/K = {G} is the group with one element.

If K = {1}, then Ka = {a} for each a G, so G/K is the set of all singleton

  subsets of G. The operation is {a}{b} = {ab}, so G/K ≅ G in this case.

Example 2. Let where o(a) = 12, and let Find all the cosets in G/K and write down the Cayley table.

Solution. Note first that K G because G is abelian. The cosets are

K = {1, a⁴, a⁸}, Ka = {a, a⁵, a⁹}, Ka² = {a², a⁶, a¹⁰}, Ka³ = {a³, a⁷, a¹¹}.

Two computations are needed to fill in the Cayley table: Ka · Ka³ = K (because a⁴ K) and Ka² · Ka³ = Ka⁵ = Ka (because a⁵ Ka). Then

We have as Ka² = (Ka)², Ka³ = (Ka)³, and K = Ka⁴ = (Ka)⁴. This confirms Theorem 1(4) in this case.

Example 3. Let K = {ε, (12)(34), (13)(24), (14)(23)}. Show that K A₄, find all the cosets in A₄/K, and write down the Cayley table.

Solution. We showed that K A₄ in Example 3 §2.8. The cosets are

The Cayley table is as shown.

Here the fact that K(132) = [K(123)]² shows that is cyclic. Of course, this also follows from the fact that |G/K| = 3 is prime.

Example 4. Consider the octic group D₄ = {1, a, a², a³, b, ba, ba², ba³}, where o(a) = 4, o(b) = 2, and aba = b. Show that Z(D₄) = {1, a²} and that D₄/Z(D₄) is isomorphic to the Klein group K₄.

Solution. Write Z = Z(D₄) for short. We have a(ba^k) = ba^k+3 ≠ ba^k+1 = (ba^k)a for each k, so ba^k ∉ Z. Similarly, ab = ba³ ≠ ba and a³b = ba ≠ ba³ show that a ∉ Z and a³ ∉ Z. Hence Z⊆ {1, a²}. However, a²b = ba², so a² commutes with both generators a and b of D₄. This implies that a² Z, so Z = {1, a²}.

Of course, Z = Z(D₄) is normal in D₄, and the cosets are

Thus D₄/Z = {Z, Za, Zb, Zba}, and the Cayley table is as shown.

This is evidently the noncyclic group of order 4, that is D₄/Z ≅ K₄.

Example 5. Let where o(a) = 18, and let Find the order of the element Ka⁵ in G/K.

Solution 1. As K = {1, a⁶, a¹²}, we have |G/K| = |G|/|K| = 18/3 = 6. Then, from Lagrange's theorem, the order o(Ka⁵) of Ka⁵ is 1, 2, 3, or 6. Now

Hence o(Ka⁵) is not 1, 2, or 3, so it must be 6.

Solution 2. because gcd (5, 18) = 1, so . Hence by Theorem 1. Because |G/K| = 6, this means that o(Ka⁵) = 6.

The next theorem provides a useful method of proving that a group is abelian. We include it for reference later.

Theorem 2. Suppose a group G has a subgroup K ⊆ Z(G) such that G/K is cyclic. Then G is abelian.

Proof. Let If a, b G, this means that we can write Ka and Kb in the form Ka = Kg^m and Kb = Kgⁿ. Thus a = kg^m and b = k₁gⁿ where k and k₁ are in K (and hence are central in G by hypothesis). But then

This shows that G is abelian.

The Derived Subgroup

If H G there is a useful test for determining when a factor group G/H is abelian. To motivate it, consider the following way of deciding that two cosets Ha and Hb commute:

With this in mind, an element in a group G of the form aba⁻¹b⁻¹ is called a commutator and is denoted

Hence, if H G then G/H is abelian if and only if H contains every commutator.

The commutator subgroup or derived subgroup G′ of G is defined by

G′ = {all finite products of commutators from G}.

To see that G′ really is a subgroup of G, note that 1 = [a, a] is in G′ and that G′ is clearly closed under the operation of G. The fact that G′ is closed under inverses follows from the first of the following easily verified properties of commutators.

These facts reveal the relationship between G′ and the abelian factor groups of G.

Theorem 3. Let G be a group and let H be a subgroup of G.

Proof. We have already established that G′ is a subgroup of G. Since (2) ⇒ (1) by taking H = G′, we prove only (2). If H G, the above argument shows that G/H is abelian if and only if every commutator belongs to H, that is, if and only if G′ ⊆ H. Hence it remains to show that G′ ⊆ H implies that H G. If G′ ⊆ H, let g G and h H. Then

Thus gHg⁻¹ ⊆ H, so H G as required.

Hence G′ = {1} if and only if G is abelian. Since G is abelian if and only if Z(G) = G, this contrasts the way G′ and Z(G) measure the commutativity of the group G.

Theorem 3 asserts that G′ is the smallest normal subgroup H of G with the property that the factor group G/H is abelian. This fact can be very useful in computing G′, as Example 6 illustrates.

Example 6. Compute where D₄ = {1, a, a², a³, b, ba, ba², ba³}, where o(a) = 4, o(b) = 2, and aba = b.

Solution. In Example 4 we showed that the center of D₄ is Z = {1, a²} and that D₄/Z is abelian. Hence by Theorem 3 and so, because |Z| = 2, either or But is impossible because D₄/{1} ≅ D₄ is not abelian. Hence

Exercises 2.9

2.10 The Isomorphism Theorem

There is a connection between normal subgroups, homomorphisms and factor groups. The main relationship between these concepts is embodied in the isomorphism theorem, which is the principal result in this section and one of the most useful theorems in group theory. To describe it, we begin by identifying two subgroups associated with a group homomorphism α: G → H. The first is

This is a subgroup of H as was shown in Corollary 2 of Theorem 1 §2.5. We now turn to a subgroup of G determined by α: G → H:

The kernel of α, defined by ker α = {k G α(k) = 1}.

Theorem 1. Let α: G → H be a group homomorphism.

Proof. (1) This is Corollary 2 of Theorem 1 §2.5.

(2) We have 1 ker α because α(1) = 1. If k, k′ ker α, then

Hence kk′ ker α and k⁻¹ ker α, so ker α is a subgroup. If g G and k K then

This shows that g(ker α)g⁻¹ ⊆ ker α for all g G, and so proves that ker α G.

Note that the image of a homomorphism α: G → H need not be normal in H. For example, if K is any subgroup of H, define the inclusion mapping ı: K → H by ı(k) = k for all k K. This is a one-to-one homomorphism, but ı(K) = K need not be normal in H.

Theorem 1 shows that kernels of homomorphisms from G are normal in G. Conversely, every normal subgroup of a group G arises as the kernel of some homo-morphism with G as domain:

Theorem 2. If K G, then K = ker where : G → G/K is the coset mapping.

Proof. The coset map is defined by (g) = Kg for all g G and is a homo-morphism by Theorem 1 §2.9. Because K is the unity of the group G/K, we have g ker if and only if Kg = K, if and only if g K. Hence ker = K.

Many important subgroups are kernels of naturally occurring homomorphisms; indeed, the easiest way to verify that a subgroup of a group G is normal in G is often to exhibit it as the kernel of a homomorphism with G as domain.

Example 1. The absolute value homomorphism given by z |z| has kernel the circle group

Example 2. The kernel of the determinant homomorphism A det A from is the special linear group

Example 3. If G is a group and g G has finite order n, let be the exponent mapping given by α(k) = g^k. Then by Theorem 2 §2.4.

Example 4. Show that A_n S_n by exhibiting A_n as a kernel.

Solution. Define the sign of a permutation σ S_n by

Then the sign mapping α: S_n → {1, − 1} given by α(σ) = sgnσ is a homomorphism (see Exercise 29 §1.4). Clearly ker α = A_n.

Example 5. The trivial homomorphism G → H is the only one with G as kernel.

It is clear that a homomorphism α: G → H is onto if and only if α(G) = H, that is, if and only if the image α(G) is as large a subgroup of H as possible. The next theorem shows that α is one-to-one if and only if ker α is as small as possible.

Theorem 3. If α: G → H is a homomorphism, then α is one-to-one if and only if ker α = {1}.

Proof. If α is one-to-one, let g ker α. Thus α(g) = 1 = α(1), so g = 1 because α is one-to-one. Hence ker α = {1}. Conversely, let ker α = {1} and suppose that α(a) = α(b) where a and b are in G. Then α(ab⁻¹) = α(a)α(b)⁻¹ = 1, so ab⁻¹ ker α = {1}. This shows that ab⁻¹ = 1 and hence that a = b. Thus α is one-to-one.

Theorem 3 is used frequently to test when a homomorphism is one-to-one.

We now come to one of the most useful theorems in group theory.

Theorem 4. Isomorphism Theorem³⁵. Let α: G → H be a group homomorphism and write K = ker α. Then

Proof. Write K = ker α for simplicity, and define

First is well defined; that is, Kg = Kg₁ implies that α(g) = α(g₁). In fact,

Hence is well defined (⇒) and one-to-one (⇐). As is clearly onto α(G), it remains to show that it is a homomorphism. But

holds for all Kg and Kg₁ in G/K.

If G is a group, a group of the form α(G) where α: G → H is some homomorphism is called a homomorphic image of G. Hence the isomorphism theorem shows that the factor groups of G and the homomorphic images of G are the same set of groups up to isomorphism.

Remark. The diagram to the right depicts the mappings α and in the isomorphism theorem. Here K = ker α as in the theorem, and the mapping : G → G/K is the coset mapping. Note that is a factorization

of the (arbitrary) homomorphism α as a composite where is onto and is one-to-one. Indeed, for all g G. Moreover, is the only homomorphism G/K → H with the property that Indeed, if this condition holds then the action of is determined: for all Kg in G/K. Hence:

Corollary. Let α: G → H be a group homomorphism. Then α factors uniquely as where : G → G/ker α is the coset map, and is defined in Theorem 4. Note that is onto, and is one-to-one.

The isomorphism theorem is a marvelous result. It sheds light on nearly every situation to which it is applied. It is used as follows: If we want to show that G/K ≅ H, we find an onto homomorphism G → H with kernel K. As a bonus, the fact that K is a kernel automatically proves that it is normal in G. Examples 6–9 illustrate the use of the isomorphism theorem.

Example 6. If G is a cyclic group, show that or

Solution. Let and define by α(k) = a^k for all This is an onto homomorphism and ker α = {k a^k = 1}. If o(a) is infinite, ker α = {0} and the isomorphism theorem gives If o(a) = n, then and =

Example 7. Let K G and K₁ G₁. Show that (K × K₁) (G × G₁) and

Solution. We define α: (G × G₁) → (G/K) × (G₁/K₁) by α(g, g₁) = (Kg, K₁g₁). It is routine to verify that this is an onto homomorphism, and ker α = K × K₁. The isomorphism theorem now gives all our assertions.

Example 8. Show that where is the circle group.

Solution. We define by α(x) = e^2πxi. We have

so α is a homomorphism. It is clearly onto, and

Thus, and the isomorphism theorem does the rest.

If we are interested in determining all homomorphisms α: G → G₁, the fact that α(G₁) is isomorphic to G/(ker α) is useful because sometimes we can determine the normal subgroups of G. In Example 9 §2.5, we showed that there are at most six homomorphisms: S₃ → C₆, and hence at most 6 from D₃ → C₆. Using the isomorphism theorem, we can show that in fact there are only two.

Example 9. Write D₃ = {1, a, a², b, ba, ba²}, where o(a) = 3, o(b) = 2, and aba = b, and write where o(c) = 6. Show that there are only two homomorphisms, D₃ → C₆, the trivial one and

Solution. We know that D₃ has only three normal subgroups: {1}, D₃, and . Thus if α: D₃ → C₆ is a homomorphism, ker α must be one of them. It is impossible that ker α = {1} because then α(D₃) ≅ D₃ would be a nonabelian subgroup of C₆. If ker α = D₃ then α is the trivial homomorphism. So assume that . In this case, let : D₃ → D₃/K be the coset map. If α exists, the corollary to the isomorphism theorem guarantees that α = σ, whereσ: D₃/K → α(D₃) is an

isomorphism. In this case D₃/K = {K, bK} is cyclic of order 2, so α(D₃) is the (unique) subgroup of order 2 in C₆; that is α(D₃) = {1, c³}. Clearly, σ(K) = 1 and σ(bK) = c³, so α = σ is given by

α(b^ka^m) = σ(b^ka^m) = σ(b^ka^mK) = σ(bK)^k · σ(aK)^m = (c³)^k · 1^m = c^3k.

We conclude this section with one more result using the isomorphism theorem. Recall (Example 18 §2.5) that the set innG of all inner automorphisms of a group G is a subgroup of the group autG of all automorphisms of G.

Theorem 5. If G is any group, then G/Z(G) ≅ innG.

Proof. If a G, recall that the inner automorphism σ_a: G → G is defined by σ_a(g) = aga⁻¹ for all g G. Then σ_aσ_b = σ_ab for all a, b G (Example 17 §2.5), and so θ(a) = σ_a defines a group homomorphism θ: G → autG. Clearly, θ(G) = innG, and

The result now follows from the isomorphism theorem.

Example 10. Show that innS₃ ≅ S₃. Show further that innS₃ = autS₃.

Solution. Z(S₃) = {ε} is easily verified, so S₃ ≅ innS₃ by Theorem 5. Hence so, since innS₃ ⊆ autS₃, it suffices to show that But S₃ = {1, σ, σ², τ, τσ, τσ²} where o(σ) = 3 and o(τ) = 2. So if θ: S₃ → S₃ is an automorphism then o(θ(σ)) = o(σ) = 3, so θ(σ) = σ or σ². Similarly θ(τ) = τ, τσ or τσ², so there are at most 2 · 3 = 6 choices for θ because .

Exercises 2.10

2.11 An Application to Binary Linear Codes

The value of mathematics in any science lies more in disciplined analysis and abstract thinking than in particular theories or techniques.

—Alan Tucker

Coding theory is concerned with the transmission of information over a channel that is affected by noise. The noise causes errors, and the general aim is to detect such errors when they occur and to correct them if possible. Such codes are used every day in communication systems such as radio, television, and telephone; in data storage systems such as those used by banks; in the internal circuits of computers; and in many other systems where information is being processed. With the advent of computers, information is often expressed in digital form, that is as strings of 0s and 1s which computers can easily handle. Consequently we deal with binary codes that are based on

General coding theory originated in the 1940s, primarily with the work of Claude Shannon. He created a mathematical theory of information and proved that certain codes exist which can transmit information at near optimal rates with arbitrarily small chance of error. In 1950, Richard W. Hamming discovered the error-detecting and error-correcting codes that now bear his name. Many of these codes are widely used today.

Example 1 concretely illustrates many of the features of general coding.

Example 1. Suppose that a spacecraft is orbiting the moon, and assume that the message 1 or 0 is to be sent instructing the mission commander to land or not. Because of static interference (noise) the probability³⁶ is 0.1 that an error will occur during transmission (and hence a probability of 0.9 that no error will occur). To ensure accuracy, the earth station transmits five signals: 11111 instead of 1 and 00000 for 0. The spacecraft computer receives a five-digit message and decodes it by a simple majority: It concludes that 11111 was sent if more 1s than 0s are received and that 00000 was sent otherwise. For example, if it receives 11001 it concludes that 11111 was sent. Thus, the spacecraft computer will get the wrong message if and only if three or more errors occur in transmission and (assuming successive errors occur independently) the probability of this happening³⁷ is 0.00856. This probability is less than 1 %, even though there is a 10% chance of error on any one transmission. This decision method is called maximum likelihood decoding.

Example 1 is a good illustration of the way coding works. A sender has a message to send (say, 1 in Example 1). It is encoded (as 11111) and transmitted over a noisy channel where it is received (as, say, 11001) and decoded (as 1) before being sent to the receiver. In Example 1, the coding process can detect errors and correct them with a probability of less than 0.01 of being wrong.

In general, it is desirable to have more messages than 1 or 0 available for encoding and transmission. For convenience (and due to the ubiquity of computers) we assume that our messages, and the encoded messages to be transmitted, are strings of 0s and 1s. We use the following notation. If n ≥ 1, let

denote the direct product of n copies of the (additive abelian) group The elements of Bⁿ are called words of length n and, for convenience, we write them as strings of 0s and 1s rather than as n-tuples. Thus, 110101 in B⁶ stands for (1, 1, 0, 1, 0, 1). We call the individual 0s and 1s the bits of the word (an abbreviation for binary digits). A subset C of Bⁿ, with |C| ≥ 2, is called an n -binary code (or simply an n-code). The words in C are called code words.

We describe the general coding process in the diagram.

A set of words, called message words, is given in B^k. They are paired with a set C of longer words in Bⁿ, n ≥ k, which will actually be transmitted. Thus C is an n-code, and the process of passing from a message to the corresponding code word is called encoding. Only code words are transmitted but, as some bits may be altered during transmission, words other than code words may be received. The sole purpose of the encoding process is to enable the receiver to detect errors and, if there are not too many, to correct them. The encoding and transmission processes are usually quite simple. The message words in B^k are paired with code words in Bⁿ in such a way that passing back and forth is easy. A common method is to add extra bits (called check bits) to the end of the message so that the message itself forms the first k bits of the code word (making retrieval easy). The transmission process is more complex, and the design of codes that are easy and inexpensive to transmit (using, say, shift registers) is an important problem that we do not consider here. The most mathematically interesting part of the process is decoding. A method must be devised to detect bit errors in the received word and, hopefully, to correct them and so reconstruct the transmitted code word. The transmission and decoding part of the process begins and ends with code words, so we concentrate on constructing codes and pay less attention to encoding and retrieving.

In Example 1, the 5-code {00000, 11111} has so few code words that a system (majority rule) of decoding can correct errors with a small probability of error. However, sometimes (for example, when retransmission is easy and inexpensive) all that is needed is to detect errors. Example 2 gives one such system that is commonly used.

Example 2. Parity-check Codes are n-codes that are constructed as follows. The message words are the elements of Bⁿ⁻¹, and we form the code words by adding one extra bit at the end, selecting it so that the total number of 1 s is even (equivalently, the sum of the bits (in ) is 0). Such words are said to have even parity. Thus, the 4-parity-check code C is

If a member of C is transmitted and one error occurs, the received word will have an odd number of 1s (odd parity) and so the error is detected. This code can thus detect any odd number of errors, but it cannot detect an even number of errors and it cannot correct any errors. Nonetheless, it is used in banking (the last digit of an account number is often a control digit) and in the internal arithmetic of digital computers.

Nearest Neighbor Decoding

Many important error-correcting codes operate in the following way. A method is found to define the distance between two words in Bⁿ. Then a code C ⊆ Bⁿ is found whose members are so far apart that, if any one bit (say) in a code word c is changed, the new word is still closer to c than to any other word in the code. Thus, if c is transmitted and one error occurs, the received word can be corrected by replacing it with the code word closest to it. We state this more compactly as follows.

Nearest Neighbor Decoding Let C be an n -code. If a word is received, it is decoded as the code word in C closest to it.(If more than one candidate appears, choose arbitrarily³⁸.)

Codes can be constructed that will correct any finite number of errors using nearest neighbor decoding.

Of course the whole thing depends on the existence of an appropriate distance function on Bⁿ. If a word c is transmitted and t errors occur, the received word will differ from c in exactly t bits. This is the distance between c and

More precisely, let and be words in Bⁿ. The Hamming distance ³⁹ between and is the number of coordinates at which their corresponding bits differ. Thus, if and where the and are the bits, then is the number of indices i such that Define the Hamming weight of by Thus, is the number of 1s occurring as bits of the word

The following theorem gives some fundamental properties of the Hamming weight and distance functions. The proof uses the fact that Bⁿ is an additive group under componentwise operations. Thus two words are added by adding corresponding bits modulo 2. For example,

Note that the unity is the word 000 0, each of whose bits is 0, which we denote 0. Also, for each word in Bⁿ, but we write for clarity.

Theorem 1. Let and be words in Bⁿ.

Proof. (1) A bit of is a 1 if and only if and differ at that coordinate. Hence the number of bits of that are 1 s equals the number of coordinates where and differ. This is (1).

(2), (3). We leave the proofs to the reader.

(4) Write and so that Then, using (1), condition (4) becomes wt(x + y) ≤ wtx + wty. Now let x_i and y_i denote the ith bits of x and y, respectively. Then the wt(x + y) is the number of values of i for which x_i + y_i = 1. Hence (4) certainly holds if x_i + y_i = 1 implies that x_i = 1 or y_i = 1. But this implication is clear because x_i = 0 = y_i implies that x_i + y_i = 0.

Properties (2), (3), and (4) of Theorem 1 justify calling d a distance function on Bⁿ. The first two are clearly true of ordinary distance. With respect to

property (4), we may regard , and as the vertices of a triangle (see the figure). Then (4) asserts that the length of one side of a triangle is not greater than the sum of the lengths of the other two sides. For this reason we call (4) the triangle inequality.

This geometric terminology for Hamming distance is useful for discussing nearest neighbor decoding. If is a word in Bⁿ and r ≥ 0 is a real number, the set

is called the ball of radius r about w or simply the r-ball about ). We use this to describe how to construct a code C that can detect (or correct) t errors.

Suppose that a code word c is transmitted and a word is received with s errors, where 1 ≤ s ≤ t. Then s is the number of coordinates at which the digits of c and differ; that is, Hence S_t(c) consists of all possible received words where at most t errors have occurred. We first assume that C has the property that no code word lies in the t-ball of another code word. Because and this means that is not a code word and that the error has been detected. If we strengthen the assumption on C to require that the t-balls about code words are pairwise disjoint, then belongs to a unique ball (that about c), so will be correctly decoded as c.

To describe when this happens, let C be an n-code. The minimum distance d of C is defined to be the smallest distance between two distinct code words in C. That is,

Theorem 2. Let C be an n -code with minimum distance d. Assume that nearest neighbor decoding is used.

Proof. (1) If c C, the t-ball S_t(c) contains no other code word because t < d. Hence C can detect t errors by the preceding discussion.

(2) If 2t + 1 ≤ d, it suffices (by the preceding discussion) to show that the t-balls about distinct code words are pairwise disjoint. But if c ≠ c′ in C and then the triangle inequality gives

by the hypothesis, a contradiction.

Example 3. The following 7-code has minimum distance 3, so it can detect 2 errors and correct 1 error.

{0000000, 0101010, 1010101, 1110000, 1011010, 0100101, 0001111, 1111111}.

If c is any word in Bⁿ, a word satisfies if and only if and c differ in exactly r bits. Hence there are exactly nr such words (where nr is the binomial coefficient), because there are nr ways to choose r bits of c to change. Therefore

This leads to a useful bound on the size of error-correcting codes.

Theorem 3. Hamming Bound. If an n-code C can correct t errors, then

Proof. Write N = n0 + n1 + + nt. The t-balls centered at distinct code words each contain N words, and there are |C| of them. Hence they contain N|C| distinct words (being pairwise disjoint). Hence N|C| ≤ 2ⁿ because |Bⁿ| = 2ⁿ. This proves the theorem.

An n-code C is called perfect if there is equality in Theorem 3 or, equivalently, if every word in Bⁿ lies in exactly one t-ball about a code word. Such codes exist. For example, if n = 3 and t = 1, then 30 + 31 = 4 and the Hamming bound is 2³/4 = 2. The 3 -code C = {000, 111} has minimum distance 3, so by Theorem 2 it can correct 1 error. Hence C is perfect. We present another example of a perfect code later.

Binary Linear Codes and Coset Decoding

Up to this point we have regarded any nonempty subset of Bⁿ as an n-code. However, many important codes are subgroups. The group Bⁿ has order 2ⁿ so, by Lagrange's theorem, each subgroup has order 2^k for some k = 0, 1, , n. Given integers k and n, with 1 ≤ k ≤ n, an additive subgroup C of Bⁿ of order 2^k is called an (n,k)-binary linear code (or simply an (n,k)-code). Note that we do not regard the trivial subgroup (k = 0) as a code.

Example 4. The code {00000, 11111} in Example 1 is a (5, 1)-code.

Example 5. The n-parity-check codes in Example 2 are (n, n − 1)-codes, because the sum of two words of even parity also has even parity.

Example 6. {0000, 0101, 1010, 1111} is a (4, 2) -code. The following is a (4, 3)-code: {0000, 0010, 0101, 0111, 1000, 1010, 1101, 1111}.

Many of the properties of the general n-codes take a simpler form for linear codes. The first part of the next theorem gives a much easier way to find the minimum distance of a linear code, the second and third parts strengthen Theorem 2, and the fourth part reformulates the Hamming bound.

Theorem 4. Let C be an (n, k) -code with minimum distance d.

Proof. (1) Write If then by the definition of d. Hence d′ ≥ d. However, Theorem 1 gives for all in C, so because (C is a group). Hence d ≥ d′.

(2) Assume that C can detect t errors. If the t -ball about contains no other code word (see the discussion preceding Theorem 2). In particular, it does not contain the code word 0, so Hence t + 1 ≤ d by (1). The converse is part of Theorem 2.

(3) If C corrects t errors, the t-balls about code words are pairwise disjoint (see the discussion preceding Theorem 2). It suffices to show that wtc ≥ 2t + 1 for all c C, c ≠ 0, since then d ≥ 2t + 1.

So assume, on the contrary, that wtc ≤ 2t. We show that then S_t(0) ∩ S_t(c) ≠ ∅, a contradiction. Since c ∉ S_t(0), we have wt(c) > t, so c has more than t ones as bits. Form by changing exactly t of these ones to zeros, and leaving the other bits of c as they were. Then , so . But c has at most 2t ones as digits (wt(c) ≤ 2t), so will have at most t ones. Hence ; that is that is . So S_t(0) ∩S_t(c) ≠ Φ, as required.

(4) Because |C| = 2^k, this assertion restates Theorem 3.

In practice, an (n, k)-code C contains a large number of words, so implementing nearest neighbor decoding by computing the distance between a received word and all 2^k code words is impractical at best. Fortunately, methods exist for reducing the amount of work required. One of these methods, called coset decoding, is based on the fact that the group Bⁿ is partitioned into cosets by the subgroup C. In fact, there are 2ⁿ/2^k = 2^n−k cosets where The method depends on the following notion.

In each coset of C in Bⁿ, choose a word e of minimum weight, called the coset leader for that coset. Note that there may be more than one candidate for coset leader. For example, if C is the code in Example 3 and the coset

has two members of minimum weight 2.

After choosing the coset leaders, we can easily state the decoding procedure.

Coset Decoding Let C be an (n, k) -code. If a word is received, and if e is any coset leader for decode as

Theorem 5. Coset decoding is nearest neighbor decoding.

Proof. Let C be an (n, k)-code. If a word is received and e is any coset leader in then is a code word in C (because e is in ). We must show that is as close to c as any other element d of C. We have so by the choice of e in C. Hence

which is what we wanted.

Example 7. Consider the (6, 3)-code:

If and are received, decode them using coset decoding.

Solution. The cosets generated by and are

One of the coset leaders in is e = 001000, so decodes as However, has three potential coset leaders: f = 010010, g = 001001, and h = 100100. These leaders decode as 001110, 010101, and 111000, respectively. Note that C has minimum distance 3, so it will correct one error by Theorem 4. Since is one error away from 100011 (in C), the code corrects But for every word c in C, so the code does not correct Note that 001110, 010101, and 111000 are all the elements of C at distance 2 from

Given an (n, k)-code C for which |C| = 2^k is not too large, we can carry out coset decoding by constructing a table (called a standard array for C), the rows of which are the various cosets of C in Bⁿ. The coset C = 0 + C is listed in the top row with 0 in column 1. (Note that 0 is the coset a for C.) In general, if e is any coset leader for then and we place the elements of this coset in a row of the table with e in column 1 and e + c in the column headed by c for each c C. We then decode as follows: If we receive a word we locate it in the table (so where e is a coset leader) and decode it as the code word c at the head of its column. Here is an example.

Example 8. Construct the standard array for the (4, 2)-code C = {0000, 0110, 1011, 1101}.

row, choose any element of B⁴ not in C, say 1111, and construct the coset

Next, we choose a coset leader, say, e₁ = 0100, (0010 would do as well), and obtain row 2 of the table by adding e₁ to the elements of row 1 in order. Thus, for example, the word 1111 in column 3 is the sum of e₁ and the word 1011 (in C) at the head of column 3.

We complete the rest of the table in the same way. To form any row, we choose an element of B⁴ not yet listed, find a coset leader in its coset, and list the coset as a row. The remaining coset leaders are e₂ = 1000 and e₃ = 0001 (each the unique word of minimum weight in its coset).

With the table complete, decoding is easy. For example, if we receive we decode as c = 1011 because is in column 3 of the table.

This method is impractical for large linear codes. For example, a (40, 10) -code has 2³⁰ > 10⁹ cosets, so finding the coset leaders is practically impossible. Hence large codes are constructed using more systematic methods.

Matrix Methods

One convenient way to obtain codes is by using matrix multiplication. Here we take the original messages to be the elements of B^k. We regard them as 1 × k row matrices with entries from and encode by multiplying by a fixed binary matrix (entries from ). We use the usual rules for matrix multiplication, except that we do arithmetic modulo 2.

Example 9. The Hamming (7, 4)-code.⁴² We use the binary matrix

The message words are the elements of B⁴; for example, u = 1011 is encoded as uG = 1011001 because of the matrix product

In the chart below, the code words corresponding to all entries of B⁴ appear on the right. Here each nonzero code word has weight at least 3, so the code can detect two errors and correct one error by Theorem 4.

Observe that the first four columns of the matrix G in Example 9 form the 4 × 4 identity matrix I₄. This ensures that the first four digits of each code word uG form the original message word. The general situation is described using the following terminology.

An (n, k)-code C is called a systematic code if each message word in B^k forms the first k digits of exactly one code word. A k × n matrix of the form⁴³

is a standard generator matrix if I_k is the k × k identity matrix and A is a k × (n − k) binary matrix. Thus, the matrix G in Example 9 is a 4 × 7 standard generator matrix G = [I₄A] where

The code itself is given as C = {uG u B^k}.

Theorem 6. Let G be a k × n standard generator matrix. Then

is a systematic (n, k)-code. Conversely, every systematic (n, k)-code is given in this way by a standard generator matrix G.

Proof. Define σ: B^k → Bⁿ by σ(u) = uG for all u B^k. Then σ is a group homomorphism because matrix multiplication satisfies As σ is clearly onto C, this shows that C is a subgroup of Bⁿ. In fact, σ is one-to-one. To see this, write G = [I_kA], where A is k × (n − k). Then

Hence σ is one-to-one because implies that [uuA] = [vvA], when Thus B^k and C are isomorphic groups and, in particular, |C| = |B^k| = 2^k. Thus C is an (n, k)-code; it is systematic because σ(u) = [uuA] for all u B^k. This proves the first part of Theorem 6; we leave the converse as Exercise 26.

Example 10. The (6, 3)-code

in Example 7 is systematic, and the reader can verify that it is generated by the standard generator matrix

That is, C = {uG u B³}.

If C is a systematic (n, k)-code, we can easily write down a standard generator matrix for C. Because C is systematic, it contains a word c_i whose first k digits form row i of I_k. Let G be the k × n matrix whose rows are c₁, c₂, , c_k in order:

Then G is a standard generator matrix and C = {uG u B^k} (See Exercise 26). Incidentally, we say that C is generated by G when C = {uG u B^k}. In this case C consists of 0 and all sums of (1 or more) of the generating words c₁, c₂, , c_k. This is illustrated in Example 11.

Example 11. Both the codes {0000, 0101, 1010, 1111} and

in Example 6 are systematic with matrices and .

On the other hand, the (7, 3)-code in Example 3 is not systematic. Nonetheless, every (n, k)-code is close to being systematic in the sense that it contains k words with the following property: If F is the k × n matrix with these words as rows, F contains every column of the k × k identity matrix I_k (Exercise 27).

The use of a standard generator matrix is a convenient method of generating (n, k)-codes not only because retrieval is easy but also because a k × n matrix has only kn entries to store, whereas the code contains 2^k words of n entries each. Moreover, the process of encoding with a systematic code is simple: Multiply the message word by the generator matrix. Hence it is not surprising that matrix methods give a simple way to detect and correct errors.

To understand why, let C be a systematic binary (n, k)-code with standard generator matrix G = [I_kA], where A is a k × (n − k) binary matrix. The parity-check matrix⁴⁴ for C is the n × (n − k) matrix given in block form by

If is a word in Bⁿ, the word wH in B^n−k is called the syndrome of Note that each of G and H completely determines the other, so either matrix determines the code C.

Example 12. The Hamming (7, 4)-code in Example 9 has the generator matrix

Hence the parity-check matrix is H = .

In Example 12, the reader can verify that GH = 0 is the zero matrix. This relation holds in general.

Lemma. If G and H are the standard generator matrix and the parity-check matrix of a systematic(n, k)-code, then GH = 0.

Proof. Write G = [I_kA] so that Then block multiplication gives

where A + A = 0 because A is binary and x + x = 0 for all

Theorem 7. Orthogonality Theorem. Let C be a systematic (n, k)-code with parity-check matrix H.

Proof. (1) Let G = [I_kA] be the generator matrix for C, so Define α: Bⁿ → B^n−k by for all Then α is a group homomorphism because and (1) amounts to showing that C = ker α. We first verify that α is onto. If let be the word whose first k bits are zero and which ends with Then

Hence α is onto, so imα = B^n−k. Now the isomorphism theorem (Theorem 4 §2.10) gives Bⁿ/(ker α) ≅ B^n−k, so |Bⁿ|/|ker α| = |B^n−k|. Therefore | ker α| = 2^k and so | ker α| = |C|. Then to prove that C = ker α, it suffices to show that C ⊆ ker α. But if c C, then c = uG for some u B^k (Theorem 6), so α(c) = cH = uGH = u0 = 0 by the lemma. Hence C ⊆ ker α.

(2) For and in Bⁿ, we have a chain of equivalences

where the first equivalence comes from Theorem 1 §2.6, the second is by (1), and the third is because

The orthogonality theorem enables us to reformulate the coset decoding algorithm entirely in terms of the parity-check matrix.

Syndrome Decoding Let C be a systematic (n, k)-code with parity-check matrix H. If is received, compute its syndrome wH and find a word e Bⁿ of minimal weight with the same syndrome (that is, wH = eH). Decode as

The advantage of this method is that it requires knowing only the syndromes of the coset leaders (rather than the entire standard array), and sometimes the coset leaders can be discovered without finding the whole array.

Nearest neighbor decoding, as we have described it, is complete decoding in the sense that every received word is decoded. However, in many cases (especially where retransmission is easy) a better approach is to use a partial decoding procedure that corrects t errors and calls for retransmission when more than t errors are detected. We conclude by describing one such algorithm.

In this section, we have merely touched the surface of algebraic coding theory. For example, these results generalize with very little change if an (n, k)-code is defined to be a k-dimensional subspace of an n-dimensional vector space V over a finite field F (in our discussion, V = Bⁿ and ). Even more sophisticated coding algorithms exist that use ring theory and field theory as well as group theory and linear algebra (see Section 6.7 for one such application).⁴⁵

Exercises 2.11

Notes

18. The term “identity” is often used here but it has other meanings in algebra. So we use the term unity.

19. A set with an associative binary operation, but possibly no unity, is called a semigroup.

20. This proof will not be used below and so may be omitted at a first reading. By contrast, the theorem will be used hundreds of times.

21. See Nicholson, W.K., Linear Algebra with Applications, 7th ed., McGraw-Hill Ryerson, 2012 (Theorem 2 §3.2).

22. The name honors the Norwegian mathematician Niels Henrik Abel.

23. If X and Y are sets the set difference is defined by .

24. The name honors Felix Klein. This group is also called the four group.

25. To avoid confusion, we sometimes denote the unity of a group G by 1_G when other groups are present.

26. The notation Z(G) comes from zentrum, the German word for center.

27. Homomorphisms were first used explicitly (for permutation groups) by Jordan in 1870.

28. The term isomorphism comes from isos, meaning equal, and morphe, meaning shape.

29. See, for instance, Clay, J.R., The punctured plane is isomorphic to the unit circle, Journal of Number Theory, 1, (1964), 500–501.

30. Recall (Section 0.4) that a partition of a nonempty set X is a collection of nonempty subsets of X (called the cells of the partition) which are pairwise disjoint (distinct cells are disjoint) and every element of X is in some cell (hence in exactly one cell).

31. In fact where is the inner automorphism determined by g.

32. Thompson, J. G., and Feit, W., Solvability of Groups of Odd Order, Pacific Journal of Mathematics, 13 (1963), 775–1029.

33. John Thompson was awarded the Fields Medal in 1970, the highest honor a mathematician can receive.

34. More information can be found in Chapter 17 of “Finite Groups” by D. Gorenstein, Chelsea, 1980.

35. This result goes back to Camille Jordan (1838–1922) in his book Traité des Substitutions (1870), where the concept of a homomorphism was introduced.

36. We treat probability informally here. The probability that an event occurs is the long-term proportion of the time that the event does indeed occur. Thus probabilities are numbers between 0 and 1. A probability of 0 means that the event in question is impossible; a probability of 1 means that the event is certain to occur; and a probability of 0.5 means that the event is as likely as not to occur.

37. The probability is computed as . It is based on the assumption that at most one error occurs in each digit transmitted and that these errors occur independently.

38. If it is feasible, retransmission may be called for in this case.

39. The name honors Richard W. Hamming. Distance functions are also called metrics.

40. If C can detect (correct) t or fewer errors, we say simply that C detects (corrects) t errors.

41. Because of this the minimum distance of a linear code is sometimes called the minimum weight of the code.

42. This code was the first nontrivial example of an error correcting code given in the groundbreaking paper in which information theory was originated (Shannon, C.E., A mathematical theory of communication, Bell Systems Technical Journal 27 (1948), 623–656).

43. If A and B are k × m and k × n matrices, the notation [A B] indicates the k × (m + n) matrix with A occupying the first m columns and B occupying the last n columns. The matrix [A B] is said to be given in block form.

44. Systematic binary codes are often defined using the parity-check matrix. Then the transpose of H is referred to as the parity-check matrix.

45. An introduction to the subject is given in Pless, V., Introduction to the Theory of Error Correcting Codes, New York: Wiley, 1982. A more thorough treatment (with an extensive bibliography) is that by MacWilliams, F.I., and Sloan, N.J.A., The Theory of Error Correcting Codes, Vols. I and II, New York: North Holland, 1977. Finally, a useful survey is contained in Chapter 4 of Lidl, R., and Pilz, G., Applied Abstract Algebra, New York: Springer-Verlag, 1984.