## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 5. SUBGROUPS

Let *G* be a group, and *S* a nonempty subset of *G*. It may happen (though it doesn’t have to) that the product of every pair of elements of *S* is in *S*. If it happens, we say that *S* is *closed with respect to multiplication*. Then, it may happen that the inverse of every element of *S* is in *S*. In that case, we say that *S* is *closed with respect to inverses*. If both these things happen, we call *S* a *subgroup* of *G*.

When the operation of *G* is denoted by the symbol +, the wording of these definitions must be adjusted: if the *sum* of every pair of elements of *S* is in *S*, we say that *S* is *closed with respect to addition*. If the negative of every element of *S* is in *S*, we say that *S* is *closed with respect to negatives*. If both these things happen, *S* is a *subgroup* of *G*.

For example, the *set of all the even integers* is a subgroup of the additive group of the integers. Indeed, the sum of any two even integers is an even integer, and the negative of any even integer is an even integer.

As another example, * (the group of the nonzero rational numbers, under multiplication) is a subgroup of * (the group of the nonzero real numbers, under multiplication). Indeed, * ⊆ * because every rational number is a real number. Furthermore, the product of any two rational numbers is rational, and the inverse (that is, the reciprocal) of any rational number is a rational number.

An important point to be noted is this: if *S* is a subgroup of *G*, *the operation of S is the same as the operation of G*. In other words, if *a* and *b* are elements of *S*, the product *ab* computed in *S* is precisely the product *ab* computed in *G*.

For example, it would be meaningless to say that ⟨*, ·⟩ is a subgroup of ⟨, +⟩; for although it is true that * is a subset of , the operations on these two groups are different.

The importance of the notion of subgroup stems from the following fact: *if G is a group and S is a subgroup of G*, *then S itself is a group*.

It is easy to see why this is true. To begin with, the operation of *G*, restricted to elements of *S*, is certainly an operation on *S*. *It is associative*: for if *a*, *b*, and *c* are in *S*, they are in *G* (because *S* ⊆ *G*); but *G* is a group, so *a*(*bc*) = (*ab*)*c*. Next, *the identity element e of G is in S* (and continues to be an identity element in *S*) for *S* is nonempty, so *S* contains an element *a*; but *S* is closed with respect to inverses, so *S* also contains *a*^{–1}; thus, *S* contains *aa*^{–1} = *e*, because *S* is closed with respect to multiplication. Finally, *every element of S has an inverse in S* because *S* is closed with respect to inverses. Thus, *S* is a group!

One reason why the notion of subgroup is useful is that it provides us with an easy way of showing that certain things are groups. Indeed, if *G* is already known to be a group, and *S* is a subgroup of *G*, we may conclude that *S* is a group without having to check all the items in the definition of “group.” This conclusion is illustrated by the next example.

Many of the groups we use in mathematics are groups whose elements are functions. In fact, historically, the first groups ever studied as such were groups of functions.

() represents the *set of all functions from* to , that is, the set of all real-valued functions of a real variable. In calculus we learned how to add functions: if *f* and *g* are functions from to , their *sum* is the function *f* + *g*given by

[*f* + *g*](*x*) = *f*(*x*) + *g*(*x*) for every real number *x*

Clearly, *f* + *g* is again a function from to , and is uniquely determined by *f* and *g*.

(), with the operation + for adding functions, is the group ⟨(),+⟩, or simply (). The details are simple, but first, let us remember what it means for two functions to be equal. If *f* and *g* are functions from to , then *f*and *g* are *equal* (that is, *f* = *g*) if and only if *f*(*x*) = *g*(*x*) for every real number *x*. In other words, to be equal, *f* and *g* must yield the same value when applied to every real number *x*.

To check that + is associative, we must show that *f* + [*g* + *h*] = [*f* + *g*] + *h*, for every three functions, *f*, *g*, and *h* in (). This means that for any real number *x*, {*f* + [*g* + *h*]}(*x*) = {[*f* + *g*] + *h*}(*x*). Well,

{*f* + [*g* + *h*]}(*x*) = *f*(*x*) + [*g* + *h*] (*x*) = *f*(*x*) + *g*(*x*) + *h*(*x*)

and {[*f* + *g*] + *h*}(*x*) has the same value.

The neutral element of () is the function given by

(*x*) = 0 for every real number *x*

To show that + *f* = *f*, one must show that [ + *f*](*x*) = *f*(*x*) for every real number *x*. This is true because [ + *f*](*x*) = (*x*) + *f*(*x*) = 0 + *f*(*x*) = *f*(*x*).

Finally, the inverse of any function *f* is the function –*f* given by

[–*f*](*x*) = –*f*(*x*) for every real number *x*

One perceives immediately that *f* + [–*f*] = , for every function *f*.

() represents the set of all *continuous* functions from to . Now, (), with the operation +, is a subgroup of (), because we know from calculus that the sum of any two continuous functions is a continuous function, and the negative –*f* of any continuous function *f* is a continuous function. Because any subgroup of a group is itself a group, we may conclude that (), with the operation +, is a group. It is denoted by ⟨(), +⟩, or simply ().

() represents the set of all the *differentiable* functions from to . It is a subgroup of () because the sum of any two differentiable functions is differentiable, and the negative of any differentiable function is differentiable. Thus, (), with the operation of adding functions, is a group denoted by ⟨(), +⟩, or simply ().

By the way, in any group *G* the one-element subset {*e*}, containing only the neutral element, is a subgroup. It is closed with respect to multiplication because *ee* = *e*, and closed with respect to inverses because *e*^{–1} = *e*. At the other extreme, the whole group *G* is obviously a subgroup of itself. These two examples are, respectively, the smallest and largest possible subgroups of *G*. They are called the *trivial* subgroups of *G*. All the other subgroups of *G* are called *proper* subgroups.

Suppose *G* is a group and *a*, *b*, and *c* are elements of *G*. Define *S* to be the subset of *G* which contains *all the possible products of a, b, c, and their inverses*, in any order, with repetition of factors permitted. Thus, typical elements of *S* would be

*abac*^{–1}

*c*^{–1}*a*^{–1}*bbc*

and so on. It is easy to see that *S* is a subgroup of *G*: for if two elements of *S* are multiplied together, they yield an element of *S*, and the inverse of any element of *S* is an element of *S*. For example, the product of *aba* and *cb*^{–1}*ac* is

*abacb*^{–1}*ac*

and the inverse of *ab*^{–1}*c*^{–1}*a* is

*a*^{–1}*cba*^{–1}

*S* is called the *subgroup of G generated by a, b, and c*.

If *a*_{1}, …, *a _{n}* are any finite number of elements of

*G*, we may define the

*subgroup generated by a*

_{1}, …,

*a*in the same way. In particular, if

_{n}*a*is a single element of

*G*, we may consider the subgroup generated by

*a*. This subgroup is designated by the symbol ⟨

*a*⟩, and is called a

*cyclic subgroup*of

*G*;

*a*is called its

*generator*. Note that ⟨

*a*⟩ consists of all the possible products of

*a*and

*a*

^{−}

^{1}, for example,

*a*

^{–1}

*aaa*

^{–1}and

*aaa*

^{–1}

*aa*

^{–1}. However, since factors of

*a*

^{–1}cancel factors of

*a*, there is no need to consider products involving both

*a*and

*a*

^{–1}side by side. Thus, ⟨

*a*⟩ contains

*a*, *aa*, *aaa*,. . .,

*a*^{–1}, *a*^{–1}*a*^{–1}, *a*^{–1}*a*^{–1}*a*^{1}, …,

as well as *aa*^{–1} = *e*.

If the operation of *G* is denoted by +, the same definitions can be given with “sums” instead of “products.”

In the group of matrices whose table appears on page 28, the subgroup generated by *D* is ⟨*D*⟩ = {*I*, *B*, *D*} and the subgroup generated by *A* is ⟨*A*⟩ = {*I*, *A*}. (The student should check the table to verify this.) In fact, the entire group *G* of that example is generated by the two elements *A* and *B*.

If a group *G* is generated by a single element *a*, we call *G* a *cyclic group*, and write *G* − ⟨*a*⟩. For example, the additive group _{6} is cyclic. (What is its generator?)

Every finite group *G* is generated by one or more of its elements (obviously). A set of equations, involving only the generators and their inverses, is called a set of *defining equations* for *G* if these equations completely determine the multiplication table of *G*.

For example, let *G* be the group {*e*, *a*, *b*, *b*^{2}, *ab*, *ab*^{2}} whose generators *a* and *b* satisfy the equations

*a*^{2} = *e* *b*^{3} = *e* *ba* = *ab*^{2} (1)

These three equations do indeed determine the multiplication table of *G*. To see this, note first that the equation *ba* = *ab*^{2} allows us to switch powers of *a* with powers of *b*, bringing powers of *a* to the left, and powers of *b* to the right. For example, to find the product of *ab* and *ab*^{2}, we compute as follows:

But by __Equations (1)__, *a*^{2} = *e* and *b*^{4} = *b*^{3}*b* = *b*; so finally, (*ab*)(*ab*^{2}) = *b*. All the entries in the table of *G* may be computed in the same fashion.

When a group is determined by a set of generators and defining equations, its structure can be efficiently represented in a diagram called a *Cayley diagram*. These diagrams are explained in __Exercise G__.

**EXERCISES**

**A. Recognizing Subgroups**

In parts 1–6 below, determine whether or not *H* is a subgroup of *G*. (Assume that the operation of *H* is the same as that of *G*.)

**Instructions** If *H* is a subgroup of *G*, show that both conditions in the definition of “subgroup” are satisfied. If *H is not* a subgroup of *G*, explain which condition fails.

**Example** *G* = *, *the multiplicative group of the real numbers*.

*H* = {2* ^{n}* :

*n*∈ }

*H*is is not □ a subgroup of

*G*.

(i) If 2* ^{n}*, 2

*∈*

^{m}*H*, then 2

*2*

^{n}*= 2*

^{m}

^{n}^{+m}. But

*n*+

*m*∈ , so 2

^{n}^{+m}∈

*H*.

(ii) If 2* ^{n}* ∈

*H*, then 1/2

*= 2*

^{n}^{–n}. But –

*n*∈ , so 2

^{n}^{+m}∈

*H*.

(Note that in this example the operation of *G* and *H* is multiplication. In the next problem, it is addition.)

**1** *G* = ⟨, +⟩, *H* = {log *a* : *a* ∈ , *a* > 0}. *H* is □ is not □ a subgroup of *G*.

**2** *G* = ⟨, +⟩, *H* = {log *n* : *n* ∈ , *n* > 0}. *H* is □ is not □ a subgroup of *G*.

**3** *G* = ⟨, +⟩, *H* = {*x* ∈ : tan *x* ∈ }. *H* is □ is not □ a subgroup of *G*.

HINT: Use the following formula from trigonometry:

**4** *G* = ⟨*, ·⟩, *H* = {2* ^{n}*3

*:*

^{m}*m*,

*n*∈ }.

*H*is □ is not □ a subgroup of

*G*.

**5** *G* = ⟨ × , +⟩, *H* = {(*x*, *y*) : *y* = 2*x*}. *H* is □ is not □ a subgroup of *G*.

**6** *G* = ⟨ × , +⟨, *H* = {(*x*, *y*) : *x*^{2} + *y*^{2} > 0}. *H* is □ is not □ a subgroup of *G*.

**7** Let *C* and *D* be sets, with *C* ⊆ *D*. Prove that *P _{C}* is a subgroup of

*P*. (See

_{D}__Chapter 3__,

__Exercise C__.)

**B. Subgroups of Functions**

In each of the following, show that *H* is a subgroup of *G*.

**Example** *G* = ⟨(), +⟩, *H* = {*f* ∈ () : *f*(0) = 0}

(i) Suppose *f*, *g* ∈ *H*; then *f*(0) = 0 and *g*(*0*) = 0, so [*f* + *g*](0) = *f*(0) + *g*(0) = 0 + 0 = 0. Thus, *f* + *g* ∈ *H*.

(ii) If *f* ∈ *H*, then *f*(0) = 0. Thus, [–*f*](0) = –*f*(0) = –0 =0, so –*f* ∈ *H*.

**1** *G* = ⟨(), +⟩, *H* = {*f* ∈ () : *f*(*x*) = 0 for every *x* ∈ [0,1]}

**2** *G* = ⟨(), +⟩, *H* = {*f* ∈ () : *f*(–*x*) = –*f*(*x*)}

**3** *G* = ⟨(), +⟩, *H* = {*f* ∈ () : *f* is periodic of period *π*}

REMARK: A function *f* is said to be *periodic* of period *a* if there is a number *a*, called the period of *f*, such that *f*(*x*) = *f*(*x* + *na*) for every x ∈ and *n* ∈ .

**4** *G* = ⟨ (), +⟩, *H* = {*f* ∈ () :

**# 5**

*G*= ⟨(),+⟩,

*H*= {

*f*∈() :

*df*/

*dx*is constant}

**6** *G* = ⟨(),+⟩, *H* = {*f* ∈ () : *f*(*x*)∈ for every *x*∈}

**C. Subgroups of Abelian Groups**

In the following exercises, let *G* be an abelian group.

**1** If *H* = {*x* ∈ *G* : *x* = *x*^{–1}}, that is, *H* consists of all the elements of *G* which are their own inverses, prove that *H* is a subgroup of *G*.

**2** Let *n* be a fixed integer, and let *H* = {*x* ∈ *G* : *x ^{n}* =

*e*}. Prove that

*H*is a subgroup of

*G*.

**3** Let *H* = {*x* ∈ *G* : *x* = *y*^{2} for some *y* ∈ *G*}; that is, let *H* be the set of all the elements of *G* which have a square root. Prove that *H* is a subgroup of *G*.

**4** Let Hbe a subgroup of *G*, and let *K* = {*x* ∈ *G* : *x*^{2} ∈ *H*}. Prove that *K* is a subgroup of *G*.

# ** 5.** Let

*H*be a subgroup of

*G*, and let

*K*consist of all the elements

*x*in

*G*such that some power of

*x*is in

*H*. That is,

*K*= {

*x*∈

*G*: for some integer

*n*> 0,

*x*∈

^{n}*H*). Prove that

*K*is a subgroup of

*G*.

**6** Suppose *H* and *K* are subgroups of *G*, and define *HK* as follows:

*HK* = {*xy* : *x* ∈ *H* and *y* ∈ *K*}

Prove that *HK* is a subgroup of *G*.

**7** Explain why parts 4–6 are not true if *G* is not abelian.

**D. Subgroups of an Arbitrary Group**

Let *G* be a group.

**1** If *H* and *K* are subgroups of a group *G*, prove that *H* ∩ *K* is a subgroup of *G*. (Remember that *x* ∈ *H* ∩ *K* iff *x* ∈ *H* and *x* ∈ *K*.)

**2** Let *H* and *K* be subgroups of *G*. Prove that if *H* ⊆ *K*, then *H* is a subgroup of *K*.

**3** By the *center of* a group *G* we mean the set of all the elements of *G* which commute with every element of *G*, that is,

*C* = {*a* ∈ *G* : *ax* = *xa* for every *x* ∈ *G*)

Prove that *C* is a subgroup of *G*.

**4** Let *C′* = {*a* ∈ *G*: (*ax*)^{2} = (*xa*)^{2} for every *x* ∈ *G*). Prove that *C′* is a subgroup of *G*.

**# 5** Let

*G*be a

*finite*group, and let

*S*be a nonempty subset of

*G*. Suppose

*S*is closed with respect to multiplication. Prove that

*S*is a subgroup of

*G*. (HINT: It remains to prove that

*S*contains

*e*and is closed with respect to inverses. Let

*S*= {

*a*

_{1}, …,

*a*}. If

_{n}*a*∈

_{i}*S*, consider the

*distinct*elements

*a*

_{i}a_{1},

*a*

_{i}a_{2}, …,

*a*.)

_{i}a_{n}**6** Let *G* be a group and *f* : *G* → *G* a function. A *period* of *f* is any element *a* in *G* such that *f*(*x*) = *f*(*ax*) for every *x* ∈ *G*. Prove: The set of all the periods of *f* is a subgroup of *G*.

**# 7** Let

*H*be a subgroup of

*G*, and let

*K*= {

*x*∈

*G*:

*xax*

^{−}

^{1}∈

*H*iff

*a*∈

*H*}. Prove:

(*a*) *K* is a subgroup of *G*.

(*b*) *H* is a subgroup of *K*.

**8** Let *G* and *H* be groups, and *G* × *H* their direct product.

(*a*) Prove that {(*x*, *e*) : *x* ∈ *G*} is a subgroup of *G* × *H*.

(*b*) Prove that {(*x*, *x*) : *x* ∈ *G*} is a subgroup of *G* × *G*.

**E. Generators of Groups**

**1** List all the cyclic subgroups of ⟨_{10}, +⟩.

**2** Show that _{10} is generated by 2 and 5.

**3** Describe the subgroup of _{12} generated by 6 and 9.

**4** Describe the subgroup of generated by 10 and 15.

**5** Show that is generated by 5 and 7.

**6** Show that _{2} × _{3} is a cyclic group. Show that _{3} × _{4} is a cyclic group.

**# 7** Show that

_{2}×

_{4}is

*not*a cyclic group, but is generated by (1, 1) and (1, 2).

**8** Suppose a group *G* is generated by two elements *a* and *b*. If *ab* = *ba*, prove that *G* is abelian.

**F. Groups Determined by Generators and Defining Equations**

**# 1** Let

*G*be the group {

*e*,

*a*,

*b*,

*b*

^{2},

*ab*,

*ab*

^{2}} whose generators satisfy

*a*

^{2}=

*e*,

*b*

^{3}=

*e*,

*ba*=

*ab*

^{2}. Write the table of

*G*.

**2** Let *G* be the group {*e*, *a*, *b*, *b*^{2}, *b*^{3}, *ab*, *ab*^{2}, *ab*^{3}} whose generators satisfy *a*^{2} = *e*, *b*^{4} = *e*, *ba* = *ab*^{3}. Write the table of *G*. (*G* is called the *dihedral group D*_{4}.)

**3** Let *G* be the group {*e*, *a*, *b*, *b*^{2}, *b*^{3}, *ab*, *ab*^{2}, *ab*^{3}} whose, generators satisfy *a*^{4} = *e*, *a*^{2} = *b*^{2}, *ba* = *ab*^{3}. Write the table of *G*. (*G* is called the *quaternion group*.)

**4** Let *G* be the *commutative* group {*e*, *a*, *b*, *c*, *ab*, *be*, *ac*, *abc*} whose generators satisfy *a*^{2} = *b*^{2} = *c*^{2} = *e*. Write the table of *G*.

**G. Cayley Diagrams**

Every finite group may be represented by a diagram known as a Cayley diagram. A Cayley diagram consists of points joined by arrows.

*There is one point for every element of the group*.

*The arrows represent the result of multiplying by a generator*.

For example, if *G* has only one generator *a* (that is, *G* is the cyclic group ⟨*a*⟩), then the arrow → represents the operation “multiply by *a*”:

*e*→*a*→*a*^{2}→*a*^{3} · · ·

If the group has two generators, say *a* and *b*, we need *two kinds of arrows*, say and →, where means “multiply by *a*,” and → means “multiply by *b*.”

For example, the group *G* = {*e*, *a*, *b*, *b*^{2}, *ab*, *ab*^{2}} where *a*^{2} = *e*, *b*^{3} = *e*, and *ba* = *ab*^{2} (see page 47) has the following Cayley diagram:

Moving in the *forward* direction of the arrow → means multiplying by *b*,

whereas moving in the *backward* direction of the arrow means multiplying by *b*^{–1}:

(Note that “multiplying *x* by *b*” is understood to mean multiplying *on the right* by *b:* it means *xb*, not *bx*.) It is also a convention that if *a*^{2} = *e* (hence *a* = *a*^{–1}), then no arrowhead is used:

for if *a* = *a*^{–1}, then multiplying by *a* is the same as multiplying by *a*^{–1}.

The Cayley diagram of a group contains the same information as the group’s table. For instance, to find the product (*ab*)(*ab*^{2}) in the figure on page 51, we start at *ab* and follow the path corresponding to *ab*^{2} (multiplying by *a*, then by *b*, then again by *b*), which is

This path leads to *b*; hence (*ab*)(*ab*^{2}) = *b*.

As another example, the inverse of *ab*^{2} is the path which leads from *ab*^{2} back to *e*. We note instantly that this is *ba*.

A point-and-arrow diagram is the Cayley diagram of a group iff it has the following two properties: (*a*) For each point *x* and generator *a*, there is exactly one *a*-arrow starting at *x*, and exactly one *a*-arrow ending at *x*; furthermore, at most one arrow goes from *x* to another point *y*. (*b*) If two different paths starting at *x* lead to the same destination, then these two paths, starting at any point *y*, lead to the same destination.

Cayley diagrams are a useful way of finding new groups.

Write the table of the groups having the following Cayley diagrams: (REMARK: You may take any point to represent *e*, because there is perfect symmetry in a Cayley diagram. Choose *e*, then label the diagram and proceed.)

**H. Coding Theory: Generator Matrix and Parity-Check Matrix of a Code**

For the reader who does not know the subject, linear algebra will be developed in __Chapter 28__. However, some rudiments of vector and matrix multiplication will be needed in this exercise; they are given here:

A *vector* with *n* components is a sequence of *n* numbers: (*a*_{1}, *a*_{2}, …, *a _{n}*). The

*dot product*of two vectors with

*n*components, say the vectors

**a**= (

*a*

_{1},

*a*

_{2}, …,

*a*) and

_{n}**b**= (

*b*

_{1},

*b*

_{2}, …,

*b*), is defined by

_{n}**a** · **b** = (*a*_{1}, *a*_{2}, …, *a _{n}*) · (

*b*

_{1},

*b*

_{2}, …,

*b*) =

_{n}*a*

_{1}

*b*

_{1}+

*a*

_{2}

*b*

_{2}+ · · · +

*a*

_{n}b_{n}that is, you multiply corresponding components and add. For example,

(1,4, –2, 3) · (6, 2, 4, –2) = 1(6) + 4(2) + (–2)4 + 3(–2) = 0

When **a · b** = 0, as in the last example, we say that **a** and **b** are *orthogonal*.

A *matrix* is a rectangular array of numbers. An “*m* by *n* matrix” (*m* × *n* matrix) has *m* rows and *n* columns. For example,

is a 3 × 4 matrix: It has three rows and four columns. Notice that each row of **B** is a vector with four components, and each column of **B** is a vector with three components.

If **A** is any *m* × *n* matrix, let **a**_{1}, **a**_{2}, …, **a*** _{n}* be the

*columns*of

**A**. (Each column of

**A**is a vector with

*m*components.) If

**x**is any vector with

*m*components,

**xA**denotes the vector

**xA** = (**x**·**a**_{1}, **x**·**a**_{2}, …, **x**·**a*** _{n}*)

That is, the components of **xA** are obtained by dot multiplying **x** by the successive columns of **A**. For example, if *B* is the matrix of the previous paragraph and **x** = (3,1, –2), then the components of **xB** are

that is, **xB** = (−7, 3, −15, 8).

If **A** is an *m* × *n* matrix, let **a**^{(1)}, **a**^{(2)}, …, **a**^{(m)} be the *rows* of *A*. If **y** is any vector with *n* components, **Ay** denotes the vector

**Ay** = (**y** · **a**^{(1)}, **y** · **a**^{(2)}, …, **y · a**^{(m)})

That is, the components of **Ay** are obtained by dot multiplying **y** with the successive *rows* of **A**. (Clearly, **Ay** is not the same as **yA**.) From linear algebra, **A**(**x** + **y**) = **Ax** + **Ay** and (**A** + **B**)**x** = **Ax** + **Bx**.

We shall now continue the discussion of codes begun in __Exercises F__ and __G__ of __Chapter 3__. Recall that is the set of all vectors of length *n* whose entries are 0s and 1s. In __Exercise F__, page 32, it was shown that is a group. A *code* is defined to be any subset *C* of . A code is called a *group code* if *C* is a *subgroup* of . The codes described in __Chapter 3__, as well as all those to be mentioned in this exercise, are group codes.

An *m* × *n* matrix **G** is a *generator matrix* for the code *C* if *C* is the group generated by the rows of **G**. For example, if *C*_{1} is the code given on page 34, its generator matrix is

You may check that all eight codewords of *C*_{1} are sums of the rows of *G*_{1}.

Recall that every codeword consists of information digits and parity-check digits. In the code *C*_{1} the first three digits of every codeword are information digits, and make up the *message;* the last two digits are parity-check digits. *Encoding* a message is the process of adding the parity-check digits to the end of the message. If **x** is a message, then *E*(**x**) denotes the encoded word. For example, recall that in *C*_{1} the parity-check equations are *a*_{4} = *a*_{1} + *a*_{3}and *a*_{5} = *a*_{1} + *a*_{2} + *a*_{3}. Thus, a three-digit message *a*_{1}*a*_{2}*a*_{3} is encoded as follows:

*E*(*a*_{1}, *a*_{2}, *a*_{3}) = (*a*_{1}, *a*_{2}, *a*_{3}, *a*_{1} + *a*_{3}, *a*_{1} + *a*_{2} + *a*_{3})

The two digits added at the end of a word are those dictated by the parity check equations. You may verify that

This is true in all cases: If **G** is the generator matrix of a code and **x** is a message, then *E*(**x**) is equal to the product **xG**. Thus, encoding using the generator matrix is very easy: you simply multiply the message **x** by the generator matrix **G**.

Now, the parity-check equations of *C*_{1} (namely, *a*_{4} = *a*_{1} + *a*_{3} and *a*_{5} = *a*_{1} + *a*_{2} + *a*_{3}) can be written in the form

*a*_{1} + *a*_{3} + *a*_{4} = 0 and *a*_{1} + *a*_{2} + *a*_{3} + *a*_{5} = 0

which is equivalent to

(*a*_{1}, *a*_{2}, *a*_{3}, *a*_{4}, *a*_{5}) · (1, 0, 1, 1, 0) = 0

and

(*a*_{1}, *a*_{2}, *a*_{3}, *a*_{4}, *a*_{5}) · (1, 1, 1, 0, 1) = 0

The last two equations show that a word *a*_{1}*a*_{2}*a*_{3}*a*_{4}*a*_{5} is a codeword (that is, satisfies the parity-check equations) if and only if (*a*_{1}, *a*_{2}, *a*_{3}, *a*_{4}, *a*_{5}) is orthogonal to both rows of the matrix:

**H** is called the *parity-check matrix* of the code *C*_{1}. This conclusion may be stated as a theorem:

**Theorem 1** *Let* **H** *be the parity-check matrix of a code C in* . *A word* **x** *in* *is a codeword if and only if* **Hx** = 0.

(Remember that **Hx** is obtained by dot multiplying *x* by the rows of **H**.)

**1** Find the generator matrix **G**_{2} and the parity-check matrix **H**_{2} of the code *C*_{2} described in __Exercise G2__ of __Chapter 3__.

**2** Let *C*_{3} be the following code in : the first four positions are information positions, and the parity-check equations are *a*_{5} = *a*_{2} + *a*_{3} + *a*_{4}, *a*_{6} = *a*_{1} + *a*_{3} + *a*_{4}, and *a*_{7} = *a*_{1} + *a*_{2} + *a*_{4}. (*C*_{3} is called the *Hamming code*.) Find the generator matrix **G**_{3} and parity-check matrix **H**_{3} of *C*_{3}.

The *weight* of a word **x** is the number of Is in the word and is denoted by *w*(**x**). For example, *w*(11011) = 4. The *minimum weight* of a code *C* is the weight of the nonzero codeword of smallest weight in the code. (See the definitions of “distance” and “minimum distance” on page 34.) Prove the following:

**# 3**

*d*(

**x, y**) =

*w*(

**x**+

**y**).

**4** *w*(**x**) = *d*(**x**, **0**), where **0** is the word whose digits are all 0s.

**5** The minimum distance of a group code *C* is equal to the minimum weight of *C*.

**6** (*a*) If **x** and **y** have even weight, so does **x** + **y**.

(*b*) If **x** and **y** have odd weight, **x** + **y** has even weight.

(*c*) If **x** has odd and **y** has even weight, then **x** + **y** has odd weight.

**7** In any group code, either all the words have even weight, or half the words have even weight and half the words have odd weight. (Use part 6 in your proof.)

**8** **H**(**x** + **y**) = 0 if and only if **Hx** = **Hy**, where **H** denotes the parity-check matrix of a code in and **x** and **y** are any two words in ).