A Book of Abstract Algebra, Second Edition (1982)

Chapter 3. THE DEFINITION OF GROUPS

One of the simplest and most basic of all algebraic structures is the group. A group is defined to be a set with an operation (let us call it *) which is associative, has a neutral element, and for which each element has an inverse. More formally,

By a group we mean a set G with an operation * which satisfies the axioms:

(G1)* is associative.

(G2)There is an element e in G such that a * e = a and e * a = a for every element a in G.

(G3)For every element a in G, there is an element a^−l in G such that a * a⁻¹ = e and a⁻¹ * a = e.

The group we have just defined may be represented by the symbol ⟨G, *⟩. This notation makes it explicit that the group consists of the set G and the operation *. (Remember that, in general, there are other possible operations on G, so it may not always be clear which is the group’s operation unless we indicate it.) If there is no danger of confusion, we shall denote the group simply with the letter G.

The groups which come to mind most readily are found in our familiar number systems. Here are a few examples.

is the symbol customarily used to denote the set

{…, −3, −2, −1, 0, 1, 2, 3, …}

of the integers. The set , with the operation of addition, is obviously a group. It is called the additive group of the integers and is represented by the symbol ⟨, +⟩. Mostly, we denote it simply by the symbol .

designates the set of the rational numbers (that is, quotients m/n of integers, where n ≠ 0). This set, with the operation of addition, is called the additive group of the rational numbers, ⟨, +⟩. Most often we denote it simply by .

The symbol represents the set of the real numbers. , with the operation of addition, is called the additive group of the real numbers, and is represented by ⟨, +⟩, or simply .

The set of all the nonzero rational numbers is represented by *. This set, with the operation of multiplication, is the group ⟨*, ·⟩, or simply *. Similarly, the set of all the nonzero real numbers is represented by *. The set * with the operation of multiplication, is the group ⟨*, ·⟩, or simply *.

Finally, ^pos denotes the group of all the positive rational numbers, with multiplication. ^pos denotes the group of all the positive real numbers, with multiplication.

Groups occur abundantly in nature. This statement means that a great many of the algebraic structures which can be discerned in natural phenomena turn out to be groups. Typical examples, which we shall examine later, come up in connection with the structure of crystals, patterns of symmetry, and various kinds of geometric transformations. Groups are also important because they happen to be one of the fundamental building blocks out of which more complex algebraic structures are made.

Especially important in scientific applications are the finite groups, that is, groups with a finite number of elements. It is not surprising that such groups occur often in applications, for in most situations of the real world we deal with only a finite number of objects.

The easiest finite groups to study are those called the groups of integers modulo n (where n is any positive integer greater than 1). These groups will be described in a casual way here, and a rigorous treatment deferred until later.

Let us begin with a specific example, say, the group of integers modulo 6. This group consists of a set of six elements,

{0, 1, 2, 3, 4, 5}

and an operation called addition modulo 6, which may be described as follows: Imagine the numbers 0 through 5 as being evenly distributed on the circumference of a circle. To add two numbers h and k, start with h and move clockwise k additional units around the circle: h + k is where you end up. For example, 3 + 3 = 0, 3 + 5 = 2, and so on. The set {0, 1, 2, 3, 4, 5} with this operation is called the group of integers modulo 6, and is represented by the symbol ₆.

In general, the group of integers modulo n consists of the set

{0, 1, 2, …, n − 1}

with the operation of addition modulo n, which can be described exactly as previously. Imagine the numbers 0 through n − 1 to be points on the unit circle, each one separated from the next by an arc of length 2π/n.

To add h and k, start with h and go clockwise through an arc of k times 2π/n. The sum h + k will, of course, be one of the numbers 0 through n − 1. From geometrical considerations it is clear that this kind of addition (by successive rotations on the unit circle) is associative. Zero is the neutral element of this group, and n − h is obviously the inverse of h [for h + (n − h) = n, which coincides with 0]. This group, the group of integers modulo n, is represented by the symbol _n.

Often when working with finite groups, it is useful to draw up an “operation table.” For example, the operation table of ₆ is

The basic format of this table is as follows:

with one row for each element of the group and one column for each element of the group. Then 3 + 4, for example, is located in the row of 3 and the column of 4. In general, any finite group ⟨G, *⟩ has a table

The entry in the row of x and the column of y is x * y.

Let us remember that the commutative law is not one of the axioms of group theory; hence the identity a * b = b * a is not true in every group. If the commutative law holds in a group G, such a group is called a commutative group or, more commonly, an abelian group. Abelian groups are named after the mathematician Niels Abel, who was mentioned in Chapter 1 and who was a pioneer in the study of groups. All the examples of groups mentioned up to now are abelian groups, but here is an example which is not.

Let G be the group which consists of the six matrices

with the operation of matrix multiplication which was explained on page 8. This group has the following operation table, which should be checked:

In linear algebra it is shown that the multiplication of matrices is associative. (The details are simple.) It is clear that I is the identity element of this group, and by looking at the table one can see that each of the six matrices in {I, A, B, C, D, K} has an inverse in {I, A, B, C, D, K}. (For example, B is the inverse of D, A is the inverse of A, and so on.) Thus, G is a group! Now we observe that AB = C and BA = K, so G is not commutative.

EXERCISES

A. Examples of Abelian Groups

Prove that each of the following sets, with the indicated operation, is an abelian group.

Instructions Proceed as in Chapter 2, Exercise B.

1 x * y = x + y + k(k a fixed constant), on the set of the real numbers.

2 , on the set {x ∈ : x ≠ 0}.

3 x * y = x + y + xy, on the set {x ∈ : x ≠ −1}.

# 4 , the set {x ∈ : −1 < x < 1}.

B. Groups on the Set ×

The symbol × represents the set of all ordered pairs (x, y) of real numbers. × may therefore be identified with the set of all the points in the plane. Which of the following subsets of × , with the indicated operation, is a group? Which is an abelian group?

Instructions Proceed as in the preceding exercise. To find the identity element, which in these problems is an ordered pair (e₁, e₂) of real numbers, solve the equation (a, b) * (e₁, e₂) = (a, b) for e₁ and e₂. To find the inverse (a′, b′) of (a, b), solve the equation (a, b) * (a′, b′) = (e₁, e₂) for a′ and b′. [Remember that (x, y) = (x′, y′) if and only if x = x′ and y = y′.]

1 (a, b)*(c, d) = (ad + bc, bd), on the set {(x, y) ∈ × : y ≠ 0}.

# 2 (a, b)*(c, d) = (ac, bc + d), on the set {(x, y) ∈ × : x ≠ 0}.

3 Same operation as in part 2, but on the set × .

4 (a, b)*(c, d) = (ac − bd, ad + bc), on the set × with the origin deleted.

5 Consider the operation of the preceding problem on the set × . Is this a group? Explain.

C. Groups of Subsets of a Set

If A and B are any two sets, their symmetric difference is the set A + B defined as follows:

A + B = (A − B) ∪ (B − A)

NOTE: A − B represents the set obtained by removing from A all the elements which are in B.

It is perfectly clear that A + B = B + A; hence this operation is commutative. It is also associative, as the accompanying pictorial representation suggests: Let the union of A, B, and C be divided into seven regions as illustrated.

A + B consists of the regions 1, 4, 3, and 6.

B + C consists of the regions 2, 3, 4, and 7.

A + (B + C) consists of the regions 1, 3, 5, and 7.

(A + B) + C consists of the regions 1, 3, 5, and 7.

Thus, A + (B + C) = (A + B) + C.

If D is a set, then the power set of D is the set P_D of all the subsets of D. That is,

P_D = {A: A ⊆ D}

The operation + is to be regarded as an operation on P_D.

1 Prove that there is an identity element with respect to the operation +, which is _________.

2 Prove every subset A of D has an inverse with respect to +, which is _________. Thus, ⟨P_D, +⟩ is a group!

3 Let D be the three-element set D = {a, b, c}. List the elements of P_D. (For example, one element is {a}, another is {a, b}, and so on. Do not forget the empty set and the whole set D.) Then write the operation table for ⟨P_D, +⟩.

D. A Checkerboard Game

Our checkerboard has only four squares, numbered 1, 2, 3, and 4. There is a single checker on the board, and it has four possible moves:

V:Move vertically; that is, move from 1 to 3, or from 3 to 1, or from 2 to 4, or from 4 to 2.

H:Move horizontally; that is, move from 1 to 2 or vice versa, or from 3 to 4 or vice versa.

D:Move diagonally; that is, move from 2 to 3 or vice versa, or move from 1 to 4 or vice versa.

I:Stay put.

We may consider an operation on the set of these four moves, which consists of performing moves successively. For example, if we move horizontally and then vertically, we end up with the same result as if we had moved diagonally:

H * V = D

If we perform two horizontal moves in succession, we end up where we started: H * H = I. And so on. If G = {V, H, D, I}, and * is the operation we have just described, write the table of G.

Granting associativity, explain why ⟨G, *⟩ is a group.

E. A Coin Game

Imagine two coins on a table, at positions A and B. In this game there are eight possible moves:

M₁:Flip over the coin at A.

M₂:Flip over the coin at B.

M₃:Flip over both coins.

M₄:Switch the coins.

M₅:Flip coin at A; then switch.

M₆:Flip coin at B; then switch.

M₇:Flip both coins; then switch.

I:Do not change anything.

We may consider an operation on the set {I, M₁, …, M₇}, which consists of performing any two moves in succession. For example, if we switch coins, then flip over the coin at A, this is the same as first flipping over the coin at Bthen switching:

M₄ * M₁ = M ₂ * M₄ = M₆

If G = {I, M₁, …, M₇} and * is the operation we have just described, write the table of ⟨G, *⟩.

Granting associativity, explain why ⟨G, *⟩ is a group. Is it commutative? If not, show why not.

F. Groups in Binary Codes

The most basic way of transmitting information is to code it into strings of Os and Is, such as 0010111, 1010011, etc. Such strings are called binary words, and the number of 0s and Is in any binary word is called its length. All information may be coded in this fashion.

When information is transmitted, it is sometimes received incorrectly. One of the most important purposes of coding theory is to find ways of detecting errors, and correcting errors of transmission.

If a word a = a₁a₂ … a_n is sent, but a word b = b₁b₂ … b_n is received (where the a_i and the b_j are 0s or 1s), then the error pattern is the word e = e₁e₂ … e_n where

With this motivation, we define an operation of adding words, as follows: If a and b are both of length 1, we add them according to the rules

0 + 0 = 01 + 1 = 00 + 1 = 11 + 0 = 1

If a and b are both of length n, we add them by adding corresponding digits. That is (let us introduce commas for convenience),

(a₁, a₂, …, a_n) + (b₁, b₂, …, b_n) = (a₁ + b₁ a₂ + b₂, …, a_n + b_n

Thus, the sum of a and b is the error pattern e.

For example,

The symbol will designate the set of all the binary words of length n. We will prove that the operation of word addition has the following properties on :

1.It is commutative.

2.It is associative.

3.There is an identity element for word addition.

4.Every word has an inverse under word addition.

First, we verify the commutative law for words of length 1:

0 + 1 = 1 = 1 + 0

1 Show that (a₁, a₂, …, a_n) + (b₁, b₂, …, b_n) = (b₁, b₂, …, b_n) + (a₁, a₂, …, a_n).

2 To verify the associative law, we first verify it for words of length 1:

1 + (1 + 1) = 1 + 0 = 1 = 0 + 1 = (1 + 1) + 1

1 +(1 + 0) = 1 + 1 = 0 = 0 + 0 = (l + l) + 0

Check the remaining six cases.

3 Show that (a₁, …, a_n) + [(b₁, …, b_n) + (c₁, …, c_n)] = [(a₁, …, a_n) + (b₁, …, b_n)] + (c₁, …, c_n).

4 The identity element of , that is, the identity element for adding words of length n, is __________.

5 The inverse, with respect to word addition, of any word (a₁, …, a_n) is __________.

6 Show that a + b = a − b [where a − b = a + (−b*)].

7 If a + b = c, show that a = b + c.

G. Theory of Coding: Maximum-Likelihood Decoding

We continue the discussion started in Exercise F: Recall that designates the set of all binary words of length n. By a code we mean a subset of . For example, below is a code in ⁵. The code, which we shall call C₁, consists of the following binary words of length 5:

00000
00111
01001
01110
10011
10100
11010
11101

Note that there are 32 possible words of length 5, but only eight of them are in the code C,. These eight words are called codewords; the remaining words of B⁵ are not codewords. Only codewords are transmitted. If a word is received which is not a codeword, it is clear that there has been an error of transmission. In a well-designed code, it is unlikely that an error in transmitting a codeword will produce another codeword (if that were to happen, the error would not be detected). Moreover, in a good code it should be fairly easy to locate errors and correct them. These ideas are made precise in the discussion which follows.

The weight of a binary word is the number of Is in the word: for example, 11011 has weight 4. The distance between two binary words is the number of positions in which the words differ. Thus, the distance between 11011 and 01001 is 2 (since these words differ only in their first and fourth positions). The minimum distance in a code is the smallest distance among all the distances between pairs of codewords. For the code C₁, above, pairwise comparison of the words shows that the minimum distance is 2. What this means is that at least two errors of transmission are needed in order to transform a codeword into another codeword; single errors will change a codeword into a noncodeword, and the error will therefore be detected. In more desirable codes (for example, the so-called Hamming code), the minimum distance is 3, so any one or two errors are always detected, and only three errors in a single word (a very unlikely occurrence) might go undetected.

In practice, a code is constructed as follows: in every codeword, certain positions are information positions, and the remaining positions are redundancy positions. For instance, in our code C₁, the first three positions of every codeword are the information positions: if you look at the eight codewords (and confine your attention only to the first three digits in each word), you will see that every three-digit sequence of 0s and Is is there namely,

000, 001, 010, 011, 100, 101, 110, 111

The numbers in the fourth and fifth positions of every codeword satisfy parity-check equations.

# 1 Verify that every codeword a₁a₂a₃a₄a₅ in C₁ satisfies the following two parity-check equations: a₄ = a₁ + a₃; a₅ = a₁ + a₂ + a₃.

2 Let C₂ be the following code in . The first three positions are the information positions, and every codeword a₁a₂a₃a₄a₅a₆ satisfies the parity-check equations a₄ = a₂, a₅ = a₁ + a₂, and a₆ = a₁ + a₂ + a₃.

# (a)List the codewords of C₂.

(b)Find the minimum distance of the code C₂.

(c)How many errors in any codeword of C₂ are sure to the detected? Explain.

3 Design a code in where the first two positions are information positions. Give the parity-check equations, list the codewords, and find the minimum distance.

If a and b are any two words, let d(a, b) denote the distance between a and b. To decode a received word x (which may contain errors of transmission) means to find the codeword closest to x, that is, the codeword a such that d(a, x) is a minimum. This is called maximum-likelihood decoding.

4 Decode the following words in C₁: 11111, 00101, 11000, 10011, 10001, and 10111.

You may have noticed that the last two words in part 4 had ambiguous decodings: for example, 10111 may be decoded as either 10011 or 00111. This situation is clearly unsatisfactory. We shall see next what conditions will ensure that every word can be decoded into only one possible codeword.

In the remaining exercises, let C be a code in , let m denote the minimum distance in C, and let a and b denote codewords in C.

5 Prove that it is possible to detect up to m − 1 errors. (That is, if there are errors of transmission in m − 1 or fewer positions of a codeword, it can always be determined that the received word is incorrect.)

# 6 By the sphere of radius k about a codeword a we mean the set of all words in whose distance from a is no greater than k. This set is denoted by S_k(a); hence

S_k(a) = {x: d(a, x) ≤ k}

If , prove that any two spheres of radius t, say S_t(a) and S_t(b), have no elements in common. [HINT: Assume there is a word x such that x ∈ S_t(a) and x ∈ S_t,(b). Using the definitions of t and m, show that this is impossible.]

7 Deduce from part 6 that if there are t or fewer errors of transmission in a codeword, the received word will be decoded correctly.

8 Let C₂ be the code described in part 2. (If you have not yet found the minimum distance in C₂, do so now.) Using the results of parts 5 and 7, explain why two errors in any codeword can always be detected, and why one error in any codeword can always be corrected.