2.40. A large room has three separate entrances, and there is a light switch by

each entrance. Design a circuit that will allow the lights to be turned on

or off by throwing any one switch.

2.41. A voting machine for three people contains three YES“NO switches and

allows current to pass if and only if there is a majority of YES votes.

Design and simplify such a machine.

2.42. Design and simplify a voting machine for ¬ve people.

2.43. Design a circuit for a light that is controlled by two independent switches

A and B and a master switch C. C must always be able to turn the light

on. When C is off, the light should be able to be turned on and off using

A or B.

2.44. A committee consists of a chairman A, and three other members, B, C,

and D. If B, C, and D, are not unanimous in their voting, the chairman

decides the vote. Design a voting machine for this committee and simplify

it as much as possible.

2.45. Verify that the Venn diagram in Figure 2.37 illustrates the 16 atoms for a

boolean expression in four variables. Then use the diagram to simplify the

circuit in Figure 2.37.

C D

A B′

A C A′

A B

B

D A′

Figure 2.37

2.46. Design four series-parallel circuits to multiply two numbers in binary form

that have at most two digits each.

2.47. Design a circuit that will turn an orange light on if exactly one of the four

switches A, B, C, and D is on and a green light when all four are on.

2.48. Five switches are set to correspond to a number in binary form that has at

most ¬ve digits. Design and simplify a circuit that will switch a light on

if and only if the binary number is a perfect square.

2.49. In Chapter 11 we construct a ¬nite ¬eld F = {0, 1, ±, β} whose multipli-

cation table is given in Table 2.19. Writing 00 for 0, 01 for 1, 10 for ±,

and 11 for β, design and simplify circuits to perform this multiplication.

2.50. A swimming pool has four relay switches that open when the water tem-

perature is above the maximum allowable, when the water temperature is

below the minimum, when the water level is too high, and when the level

EXERCISES 45

TABLE 2.19. Multiplication in

a Four-Element Field

· 0 1 ± β

0 0 0 0 0

1 0 1 ± β

0 1

± ± β

0 1

β β ±

is too low. These relays are used to control the valves that add cold water,

that let water out, and that heat the water in the pool. Design and simplify

a circuit that will perform the following tasks. If the temperature is correct

but the level too high, it is to let water out. If the temperature is correct but

the level too low, it is to let in cold water and heat the water. If the pool is

too warm, add cold water and, if the level is also too high, let water out at

the same time. If the pool is too cold but the level correct, heat the water;

if the level is too low, heat the water and add cold water, and, if the level

is too high, just let out the water.

2.51. In a dual fashion to the disjunctive normal form, every boolean expression

in n-variables can be written in its conjunctive normal form. What are the

conjunctive normal forms for A B and A § B ?

Draw poset diagrams for the sets given in Exercises 2.52 to 2.57 with divisi-

bility as the partial order and determine whether the systems are lattices or

boolean algebras.

{1, 2, 3, 4, 5, 6}. 2.53. {2, 4, 6, 12}.

2.52.

2.55. {1, 2, 4, 8}.

D54

2.54.

2.57. {1, 2, 3, 5, 6, 10, 30, 60}.

D42

2.56.

Prove that (Dn , |) is a poset for each n 2, and prove the distributive laws.

2.58.

Let n = p1 p2 · · · pr , where the pi are distinct primes. Describe the atoms

2.59.

in the boolean algebra (Dn , gcd, lcm, ).

2.60. Prove that an element A = 0 in a boolean algebra is an atom if and only

if for each B in the algebra, either A B or A B .

2.61. Suppose that A and B are elements of a boolean algebra. If an element X

in the algebra exists such that A § X = B § X and A ∨ X = B ∨ X, show

that A = B. [Hint: A = A § (A ∨ X).]

2.62. Let K = {x ∈ R|0 x 1} and let x § y and x ∨ y be the smaller and

larger of x and y, respectively. Show that it is not possible to de¬ne a

complement on K so that (K, §, ∨, ) is a boolean algebra. However,

if we de¬ne x = 1 ’ x, which of the properties de¬ned in the section

“Boolean Algebras” and in Proposition 2.13 remain true? This is the kind

of algebraic model that would be required to deal with transistor switching

gates under transient conditions. The voltage or current varies continuously

between the levels 0 and 1, while an AND gate performs the operation

x § y, an OR gate performs x ∨ y, and a NOT gate produces x .

46 2 BOOLEAN ALGEBRAS

2.63. If f is a boolean algebra morphism from K to L, prove that f (0K ) = 0L

and f (1K ) = 1L , where 0K , 0L , 1K , and 1L are the respective zero and

unit elements.

2.64. Write down the tables for the NOR and NAND operations on the set

P ({a, b, c}).

2.65. Can every switching circuit be built out of AND and NOT gates?

2.66. (a) Design a half adder using ¬ve NOR gates.

(b) Design a half adder using ¬ve NAND gates.

2.67. Analyze the effect of the circuit in Figure 2.38.

a

NAND

b

d

NOR

c

Figure 2.38

2.68. Design a NOR circuit that will produce a parity check symbol for four

binary input digits; that is, the circuit must produce a 0 if the inputs contain

an even number of 1™s, and it must produce 1 otherwise.

2.69. One of the basic types of components of a digital computer is a ¬‚ip-¬‚op.

This is a device that can be in one of two states (corresponding to outputs

0 and 1) and it will remain in a particular state Q until an input changes

the state to the next state Q— . One important use of a ¬‚ip-¬‚op is to store

a binary digit. An RS ¬‚ip-¬‚op is a circuit with two inputs, R and S, and

one output, Q, corresponding to the state of the ¬‚ip-¬‚op. An input R = 1

resets the next state Q— to 0, and an input S = 1 sets the next state to 1. If

both R and S are 0, the next state is the same as the previous state Q. It

is assumed that R and S cannot both be 1 simultaneously. Verify that the

NOR circuit in Figure 2.39 is indeed an RS ¬‚ip-¬‚op. To eliminate spurious

effects due to the time it takes a transistor to operate, this circuit should

be controlled by a “clock.” The output Q should be read only when the

clock “ticks,” whereas the inputs are free to change between ticks.

S NOR

Q

NOR

R

Figure 2.39. RS ¬‚ip-¬‚op.

2.70. A JK ¬‚ip-¬‚op is similar to an RS ¬‚ip-¬‚op except that both inputs are

allowed to be 1 simultaneously, and in this case the state Q changes to its

opposite state. Design a JK ¬‚ip-¬‚op using NOR and NAND gates.

3

GROUPS

Symmetries and permutations in nature and in mathematics can be described

conveniently by an algebraic object called a group. In Chapter 5, we use group

theory to determine all the symmetries that can occur in two- or three-dimensional

space. This can be used, for example, to classify all the forms that chemical

crystals can take. If we have a large class of objects, some of which are equiva-

lent under permutations or symmetries, we show, in Chapter 6, how groups can

be used to count the nonequivalent objects. For example, we count the num-

ber of different switching functions of n variables if we allow permutations of

the inputs.

Historically, the basic ideas of group theory arose with the investigation of

permutations of ¬nite sets in the theory of equations. One of the aims of mathe-

maticians at the beginning of the nineteenth century was to ¬nd methods for

solving polynomial equations of degree 5 and higher. Algorithms, involving

the elementary arithmetical operations and the extraction of roots, were already

known for solving all polynomial equations of degree less than 5; the formulas

for solving quadratic equations had been known since Babylonian times, and

cubic and quartic equations had been solved by various Italian mathematicians

in the sixteenth century. However, in 1829, using the rudiments of group theory,

the Norwegian Niels Abel (1802“1829) showed that some equations of the ¬fth

degree could not be solved by any such algorithm. Just before he was mortally

´

wounded in a duel, at the age of 20, the brilliant mathematician Evariste Galois

(1811“1832) developed an entire theory that connected the solvability of an

equation with the permutation group of its roots. This theory, now called Galois

theory, is beyond the scope of this book, but interested students should look at

Stewart [35] after reading Chapter 11.

It was not until the 1880s that the abstract de¬nition of a group that we

use today began to emerge. However, Cayley™s theorem, proved at the end of

this chapter, shows that every abstract group can be considered as a group of

permutations. It was soon discovered that this concept of a group was so universal

that it cropped up in many different branches of mathematics and science.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

47

48 3 GROUPS

GROUPS AND SYMMETRIES

A group (G, ·) is a set G together with a binary operation · satisfying the

following axioms.

(i) G is closed under the operation ·; that is, a · b ∈ G for all a, b ∈ G.

(ii) The operation · is associative; that is, (a · b) · c = a · (b · c) for all

a, b, c ∈ G.

(iii) There is an identity element e ∈ G such that e · a = a · e = a for all

a ∈ G.

(iv) Each element a ∈ G has an inverse element a ’1 ∈ G such that a ’1 · a =

a · a ’1 = e.

The closure axiom is already implied by the de¬nition of a binary operation;

however, it is included because it is often overlooked otherwise.

If the operation is commutative, that is, if a · b = b · a for all a, b ∈ G,

the group is called commutative or abelian, in honor of the mathematician

Niels Abel.

Let G be the set of complex numbers {1, ’1, i, ’i} and let · be the standard

multiplication of complex numbers. Then (G, ·) is an abelian group. The product

of any two of these elements is an element of G; thus G is closed under the

operation. Multiplication is associative and commutative in G because multipli-

cation of complex numbers is always associative and commutative. The identity

element is 1, and the inverse of each element a is the element 1/a. Hence

1’1 = 1, (’1)’1 = ’1, i ’1 = ’i, and (’i)’1 = i. The multiplication of any two

elements of G can be represented by Table 3.1.

The set of all rational numbers, Q, forms an abelian group (Q, +) under addi-

tion. The identity is 0, and the inverse of each element is its negative. Similarly,

(Z, +), (R, +), and (C, +) are all abelian groups under addition.

If Q— , R— , and C— denote the set of nonzero rational, real, and complex

numbers, respectively, (Q— , ·), (R— , ·), and (C— , ·) are all abelian groups under

multiplication.

For any set X, (P (X), ) is an abelian group. The group axioms follow

from Proposition 2.3; the empty set, ˜, is the identity, and each element is its

own inverse.

TABLE 3.1. Group

{1, ’1, i , ’i }

· ’1 ’i

1 i

’1 ’i

1 1 i

’1 ’1 ’i

1 i

’i ’1 1

i i

’i ’i ’1

1

i

GROUPS AND SYMMETRIES 49

Every group must have at least one element, namely, its identity, e. A group

with only this one element is called trivial. A trivial group takes the form ({e}, ·),

where e · e = e.

Many important groups consist of functions. Given functions f : X ’ Y and

g: Y ’ Z, their composite g Ž f : X ’ Z is de¬ned by

(g Ž f )(x) = g(f (x)) for all x ∈ X.

Composition is associative; that is, if h: Z ’ W , then h Ž (g Ž f ) = (h Ž g) Ž f .

Indeed,

(h Ž (g Ž f ))(x) = h(g(f (x))) = ((h Ž g) Ž f )(x)

for all x ∈ X, as is readily veri¬ed. In particular, if X is a set, then Ž is an

associative binary operation on the set of all functions f : X ’ X. Moreover,

this operation has an identity: The identity function 1X : X ’ X is de¬ned by

1X (x) = x for all x ∈ X.

Then 1X Ž f = f = f Ž 1X for all f : X ’ X. Hence, we say that a function

f : X ’ X is an inverse of f : X ’ X if

= 1X and f Ž f = 1X ;

f Žf

equivalently if f (f (x)) = x and f (f (x)) = x for all x ∈ X. This inverse is

unique when it exists. For if f is another inverse of f , then

f =f =f ) = (f = 1X Ž f = f .

Ž 1X Ž (f Ž f Žf)Žf

When it exists (see Theorem 3.3) the inverse of f is denoted f ’1 .

Example 3.1. A translation of the plane R2 in the direction of the vector (a, b)

is a function f : R2 ’ R2 de¬ned by f (x, y) = (x + a, y + b). The composition

of this translation with a translation g in the direction of (c, d) is the function

f Ž g: R2 ’ R2 , where

f Ž g(x, y) = f (g(x, y)) = f (x + c, y + d) = (x + c + a, y + d + b).

This is a translation in the direction of (c + a, d + b). It can easily be veri¬ed

that the set of all translations in R2 forms an abelian group, (T(2), Ž ), under

composition. The identity is the identity transformation 1R2 : R2 ’ R2 , and the

inverse of the translation in the direction (a, b) is the translation in the opposite

direction (’a, ’b).

A function f : X ’ Y is called injective or one-to-one if f (x1 ) = f (x2 )

implies that x1 = x2 . In other words, an injective function never takes two dif-

ferent points to the same point. The function f : X ’ Y is called surjective or

50 3 GROUPS

onto if for any y ∈ Y , there exists x ∈ X with y = f (x), that is, if the image

f (X) is the whole set Y . A bijective function or one-to-one correspondence is

a function that is both injective and surjective. A permutation or symmetry of

a set X is a bijection from X to itself.

Lemma 3.2. If f : X ’ Y and g: Y ’ Z are two functions, then:

(i) If f and g are injective, g Ž f is injective.

(ii) If f and g are surjective, g Ž f is surjective.

(iii) If f and g are bijective, g Ž f is bijective.

Proof. (i) Suppose that (g Ž f )(x1 ) = (g Ž f )(x2 ). Then g(f (x1 )) = g(f (x2 ))

so, since g is injective, f (x1 ) = f (x2 ). Since f is also injective, x1 = x2 , proving

that g Ž f is injective.

(ii) Let z ∈ Z. Since g is surjective, there exists y ∈ Y with g(y) = z, and

since f is also surjective, there exists x ∈ X with f (x) = y. Hence (g Ž f )(x) =

g(f (x)) = g(y) = z, so g Ž f is surjective.

(iii) This follows from parts (i) and (ii).

The following theorem gives a necessary and suf¬cient condition for a function

to have an inverse.

Theorem 3.3. Inversion Theorem. The function f : X ’ Y has an inverse if

and only if f is bijective.

Proof. Suppose that h: Y ’ X is an inverse of f . The function f is injective

because if f (x1 ) = f (x2 ), it follows that (h Ž f )(x1 ) = (h Ž f )(x2 ), and so x1 =

x2 . The function f is surjective because if y is any element of Y and x = h(y),

it follows that f (x) = f (h(y)) = y. Therefore, f is bijective.

Conversely, suppose that f is bijective. We de¬ne the function h: Y ’ X as

follows. For any y ∈ Y , there exists x ∈ X with y = f (x). Since f is injective,

there is only one such element x. De¬ne h(y) = x. This function h is an inverse

to f because f (h(y)) = f (x) = y, and h(f (x)) = h(y) = x.

Theorem 3.4. If S(X) is the set of bijections from any set X to itself, then

(S(X), Ž ) is a group under composition. This group is called the symmetric

group or permutation group of X.

Proof. It follows from Lemma 3.1 that the composition of two bijections is a

bijection; thus S(X) is closed under composition. The composition of functions is

always associative, and the identity of S(X) is the identity function 1X : X ’ X.

The inversion theorem (Theorem 3.3) proves that any bijective function f ∈

S(X) has an inverse f ’1 ∈ S(X). Therefore, (S(X), Ž ) satis¬es all the axioms

for a group.

GROUPS AND SYMMETRIES 51

TABLE 3.2. Symmetry

Group of {a, b}

1X f

Ž

1X 1X f

1X

f f

For example, if X = {a, b} is a two-element set, the only bijections from X to

itself are the identity 1X and the symmetry f : X ’ X, de¬ned by f (a) = b, f (b) =

a, that interchanges the two elements. The use of the term symmetry to describe the

bijection f agrees with one of our everyday uses of the word. In the phrase “the

boolean expression (a § b) ∨ (a § b ) is symmetrical in a and b” we mean that the

expression is unchanged when we interchange a and b. The symmetric group of

X, S(X) = {1X , f } and its group table is given in Table 3.2. The composition f Ž f

interchanges the two elements a and b twice; thus it is the identity.

Since the composition of functions is not generally commutative, S(X) is not

usually an abelian group. Consider the elements f and g in the permutation

group of {1, 2, 3}, where f (1) = 2, f (2) = 3, f (3) = 1 and g(1) = 1, g(2) =

3, g(3) = 2. Then f Ž g(1) = 2, f Ž g(2) = 1, f Ž g(3) = 3, while g Ž f (1) = 3,

g Ž f (2) = 2, g Ž f (3) = 1; hence f Ž g = g Ž f , and S({1, 2, 3}) is not abelian.

A nonsingular linear transformation of the plane is a bijective function of the

form f : R2 ’ R2 , where f (x, y) = (a11 x + a12 y, a21 x + a22 y) with the deter-

minant a11 a22 ’ a12 a21 = 0. It can be veri¬ed that the composition of two such

linear transformations is again of the same type. The set of all nonsingular linear

transformations, L, forms a non-abelian group (L, Ž ).

Besides talking about the symmetries of a distinct set of elements, we often

refer, in everyday language, to a geometric object or ¬gure as being symmetrical.

We now make this notion more mathematically precise.

If F is a ¬gure in the plane or in space, a symmetry of the ¬gure F or

isometry of F is a bijection f : F ’ F which preserves distances; that is, for

all points p, q ∈ F , the distance from f (p) to f (q) must be the same as the

distance from p to q.

One can visualize this operation by imagining F to be a solid object that

can be picked up and turned in some manner so that it assumes a con¬guration

identical to the one it had in its original position. For example, the design on

the left of Figure 3.1 has two symmetries: the identity and a half turn about a

vertical axis, called an axis of symmetry. The design in the center of Figure 3.1

Figure 3.1. Symmetrical designs.

52 3 GROUPS

has three symmetries: the identity and rotations of one-third and two-thirds of a

revolution about its center.

However, both the one-third rotation and interchanging two vertices are sym-

metries of the equilateral triangle on the right in Figure 3.1, but there is a subtle

difference: The rotation can be performed as a physical motion within the plane

of the triangle (and so is called a proper symmetry or a proper rotation),

while the re¬‚ection can only be accomplished as a physical motion by moving

the triangle outside its plane (an improper symmetry or an improper rotation).

The set of all symmetries of a geometric ¬gure forms a group under compo-

sition because the composition and inverse of two distance-preserving functions

is distance preserving.

Example 3.5. Write down the table for the group of symmetries of a rectangle

with unequal sides.

Solution. Label the corners of the rectangle 1, 2, 3, and 4 as in Figure 3.2.

Any symmetry of the rectangle will send corner points to corner points and so

will permute the corners among themselves. Denote the (improper) symmetry

obtained by re¬‚ecting the rectangle in the horizontal axis through the center,

by a; then a(1) = 4, a(2) = 3, a(3) = 2, and a(4) = 1. This symmetry can also

be considered as a rotation of the rectangle through half a revolution about this

horizontal axis. There is a similar symmetry, b, about the vertical axis through

the center. A third (proper) symmetry, c, is obtained by rotating the rectangle in

its plane through half a revolution about its center. Finally, the identity map, e,

is a symmetry. These are the only symmetries because it can be veri¬ed that any

other bijection between the corners will not preserve distances.

The group of symmetries of the rectangle is ({e, a, b, c}, Ž ), and its table, as

shown in Table 3.3, can be calculated as follows. The symmetries a, b, and c

are all half turns, so a Ž a, b Ž b, and c Ž c are full turns and are therefore equal to

the identity. The function a Ž b acts on the corner points by a Ž b(1) = a(b(1)) =

a(2) = 3, a Ž b(2) = 4, a Ž b(3) = 1, and a Ž b(4) = 2. Therefore, a Ž b = c. The

other products can be calculated similarly.

This group of symmetries of a rectangle is sometimes called the Klein 4-

group, after the German geometer Felix Klein (1849“1925).

We have seen that the group operation can be denoted by various symbols, the

most common being multiplication, composition, and addition. It is conventional

b

1 2

a

c

4 3

Figure 3.2. Symmetries of a rectangle.

GROUPS AND SYMMETRIES 53

TABLE 3.3. Symmetry Group of

a Rectangle

e a b c

Ž

e e a b c

a a e c b

b b c e a

c c b a e

to use addition only for abelian groups. Furthermore, the identity under addition

is usually denoted by 0 and the inverse of a by ’a. Hence expressions of the

form a · b’1 and a n = a · · · a, in multiplicative notation, would be written as

a ’ b and na = a + · · · + a, respectively, in additive notation.

In propositions and theorems concerning groups in general, it is conventional

to use multiplicative notation and also to omit the dot in writing a product;

therefore, a · b is just written as ab.

Whenever the operation in a group is clearly understood, we denote the group

just by its underlying set. Therefore, the groups (Z, +), (Q, +), (R, +), and

(C, +) are usually denoted just by Z, Q, R, and C, respectively. This should

cause no confusion because Z, Q, R, and C are not groups under multiplication

(since the element 0 has no multiplicative inverse). The symmetric group of X is

denoted just by S(X), the operation of composition being understood. Moreover,

if we refer to a group G without explicitly de¬ning the group or the operation,

it can be assumed that the operation in G is multiplication.

We now prove two propositions that will enable us to manipulate the elements

of a group more easily. Recall from Proposition 2.10 that the identity of any

binary operation is unique. We ¬rst show that the inverse of any element of a

group is unique.

Proposition 3.6. Let be an associative binary operation on a set S that has

identity e. Then, if an element a has an inverse, this inverse is unique.

Proof. Suppose that b and c are both inverses of a; thus a b = b a = e,

and a c = c a = e. Now, since e is the identity and is associative,

b = b e = b (a c) = (b a) c = e c = c.

Hence the inverse of a is unique.

Note that if ab = e in a group G with identity e, then a ’1 = b and b’1 = a.

Indeed, b has an inverse b’1 in G, so b’1 = eb’1 = (ab)b’1 = ae = a. Simi-

larly, a ’1 = b.

Proposition 3.7. If a, b, and c are elements of a group G, then

(i) (a ’1 )’1 = a.

(ii) (ab)’1 = b’1 a ’1 .

(iii) ab = ac or ba = ca implies that b = c. (cancellation law)

54 3 GROUPS

Proof. (i) The inverse of a ’1 is an element b such that a ’1 b = ba ’1 = e. But

a is such an element, and by Proposition 3.6 we know that the inverse is unique.

Hence (a ’1 )’1 = a.

(ii) Using associativity, we have

(ab)(b’1 a ’1 ) = a((bb’1 )a ’1 ) = a(ea ’1 ) = aa ’1 = e.

Hence b’1 a ’1 is the unique inverse of ab.

(iii) Suppose that ab = ac. Then a ’1 (ab) = a ’1 (ac), so (a ’1 a)b = (a ’1 a)c.

That is, eb = ec and b = c. Similarly, ba = ca implies that b = c.

Notice in part (ii) that the order of multiplication is reversed. This should

be familiar from the particular case of the group of invertible n — n matrices

under multiplication. A more everyday example is the operation of putting on

socks and shoes. To reverse the procedure, the shoes are taken off ¬rst and then

the socks.

If a is an element in any group G, we write a 1 = a, a 2 = aa, a 3 = aaa, and

so on, just as for numbers. Hence, if k 1, we de¬ne a k to be the product of a

with itself k times. Similarly, we de¬ne a ’k = (a ’1 )k for k 1. Finally, we set

a 0 to be the identity, again as for numbers. Thus we have de¬ned a k for every

k ∈ Z, and it is a routine veri¬cation that the laws of exponents hold:

a k a m = a k+m , (a k )m = a k+m for all a ∈ G and all k, m ∈ Z.

Moreover:

If ab = ba in G, then (ab)k = a k bk for all k ∈ Z.

0 ’1

However, this need not hold if ab = ba: For example, if a = and

10

1 ’1

b= in the group of invertible 2 — 2 matrices, then (ab)2 = a 2 b2 .

10

SUBGROUPS

It often happens that some subset of a group will also form a group under the

same operation. Such a group is called a subgroup. For example, (R, +) is a

subgroup of (C, +), and the group of translations of R2 in Example 3.1 is a

subgroup of the group of all isometries of R2 .

If (G, ·) is a group and H is a nonempty subset of G, then (H, ·) is called a

subgroup of (G, ·) if the following conditions hold:

(i) a · b ∈ H for all a, b ∈ H . (closure)

(ii) a ’1 ∈ H for all a ∈ H . (existence of inverses)

SUBGROUPS 55

Proposition 3.8. If H is a subgroup of (G, ·), then (H, ·) is also a group.

Proof. If H is a subgroup of (G, ·), we show that (H, ·) satis¬es all the group

axioms. The de¬nition above implies that H is closed under the operation; that is,

· is a binary operation on H . If a, b, c ∈ H , then (a · b) · c = a · (b · c) in (G, ·)

and hence also in (H, ·). Since H is nonempty, it contains at least one element,

say h. Now h’1 ∈ H and h · h’1 , which is the identity, is in H . The de¬nition

of subgroup implies that (H, ·) contains inverses. Therefore, (H, ·) satis¬es all

the axioms of a group.

Conditions (i) and (ii) are equivalent to the single condition:

(iii) a · b’1 ∈ H for all a, b ∈ H .

However, when H is ¬nite, the following result shows that it is suf¬cient just to

check condition (i).

Proposition 3.9. If H is a nonempty ¬nite subset of a group G and ab ∈ H for

all a, b ∈ H , then H is a subgroup of G.

Proof. We have to show that for each element a ∈ H , its inverse is also

in H . All the elements, a, a 2 = aa, a 3 = aaa, . . . belong to H so, since H is

¬nite, these cannot all be distinct. Therefore, a i = a j for some 1 i < j . By

Proposition 3.7(iii), we can cancel a i from each side to obtain e = a j ’1 , where

j ’ i > 0. Therefore, e ∈ H and this equation can be written as e = a(a j ’i’1 ) =

(a j ’i’1 )a. Hence a ’1 = a j ’i’1 , which belongs to H , since j ’ i ’ 1 0.

In the group ({1, ’1, i, ’i}, ·), the subset {1, ’1} forms a subgroup because

this subset is closed under multiplication. In the group of translations of the plane

(Example 3.1), the set of translations in the horizontal direction forms a subgroup

because compositions and inverses of horizontal translations are still horizontal

translations.

The group Z is a subgroup of Q, Q is a subgroup of R, and R is a subgroup

of C. (Remember that addition is the operation in all these groups.)

However, the set N = {0, 1, 2, . . .} of nonnegative integers is a subset of Z but

not a subgroup, because the inverse of 1, namely, ’1, is not in N. This example

shows that Proposition 3.9 is false if we drop the condition that H be ¬nite.

The relation of being a subgroup is transitive. In fact, for any group G, the

inclusion relation between the subgroups of G is a partial order relation.

Example 3.10. Draw the poset diagram of the subgroups of the group of sym-

metries of a rectangle.

Solution. By looking at the table of this group in Table 3.3, we see that Ž is

a binary operation on {e, a}; thus {e, a} is a subgroup. Also, {e, b} and {e, c} are

subgroups. If a subgroup contains a and b, it must contain a Ž b = c, so it is the

56 3 GROUPS

{e, a, b, c}

{e, a} {e, c}

{e, b}

{e}

Figure 3.3. Subgroups of the group of symmetries of a rectangle.

whole group. Similarly, subgroups containing a and c or b and c must be the

whole group. The poset diagram of subgroups is given in Figure 3.3.

CYCLIC GROUPS AND DIHEDRAL GROUPS

The number of elements in a group G is written |G| and is called the order of

the group. G is called a ¬nite group if |G| is ¬nite, and G is called an in¬nite

group otherwise.

An important class of groups consists of those for which every element can be

written as a power (positive or negative) of some ¬xed element. More precisely,

a group (G, ·) is called cyclic if there exists an element g ∈ G such that G =

{g n |n ∈ Z}. The element g is called a generator of the cyclic group.

Every cyclic group is abelian because g r · g s = g r+s = g s · g r .

The group ({1, ’1, i, ’i}, ·) is a cyclic group of order 4 generated by i because

i = 1, i 1 = i, i 2 = ’1, i 3 = ’i, i 4 = 1, i 5 = i, and so on. Hence the group can

0

be written as ({1, i, i 2 , i 3 }, ·).

In additive notation, the group (G, +) is cyclic if G = {ng|n ∈ Z} for some

g ∈ G. The group (Z, +) is an in¬nite cyclic group with generator 1 (or ’1).

The order of an element g in a group (G, ·) is the least positive integer r

such that g r = e. If no such r exists, the order of the element is said to be in¬nite.

Note the difference between the order of an element and the order of a group.

We are going to ¬nd connections between these two orders and later prove

Lagrange™s theorem, which implies that in a ¬nite group, the order of every

element divides the order of the group.

For example, in ({1, ’1, i, ’i}, ·), the identity 1 has order 1, ’1 has order 2

because (’1)2 = 1, whereas i and ’i both have order 4. The group has order 4.

Let Q— = Q ’ {0} be the set of nonzero rational numbers. Then (Q— , ·) is a

group under multiplication. The order of the identity element 1 is 1, and the

order of ’1 is 2. The order of every other element is in¬nite, because the only

solutions to q r = 1 with q ∈ Q— , r 1 are q = ±1. The group has in¬nite order.

However, it is not cyclic, because there is no rational number r such that every

nonzero rational can be written as r n for some n ∈ Z.

The next two results show how the division algorithm for integers (see Appen-

dix 2) is used in group theory.

Proposition 3.11. Let a be an element of order r in a group G. Then for k ∈

Z, g k = e if and only if r divides k.

CYCLIC GROUPS AND DIHEDRAL GROUPS 57

Proof. If k = rm, m ∈ Z, then a k = (a r )m = em = e. Conversely, if a k = e,

write k = qr + s, where q and s are in Z and 0 s < r. Then a s = a k’qr =

a k (a r )’q = e · e’q = e. Since 0 s < r and r is the smallest positive integer

such that a r = e, it follows that s = 0. But then k = qr, as required.

Proposition 3.12. Every subgroup of a cyclic group is cyclic.

Proof. Suppose that G is cyclic with generator g and that H ⊆ G is a sub-

group. If H = {e}, it is cyclic with generator e. Otherwise, let g k ∈ H with

k = 0. Since g ’k = (g k )’1 is in H , we have g m ∈ H for some m > 0, and we

choose m to be the smallest such positive integer. Write h = g m ; we claim that

h generates H . Certainly, hk ∈ H for every k ∈ Z because h ∈ H ; we must

show that every element a in H is a power of h. Since a ∈ G we have a =

g s , s ∈ Z. By the division algorithm, write s = qm + r, where 0 r < m. Then

a r = g s’qm = g s (g m )’q = a · h’q ∈ H , so r = 0 by the choice of m. Hence

a = g s = g qm = (g m )q = hq , as we wanted.

For any element g in a group (G, ·) we can look at all the powers of this

element, namely, {g r |r ∈ Z}. This may not be the whole group, but it will be

a subgroup.

Proposition 3.13. If g is any element of order k in a group (G, ·), then H =

{g r |r ∈ Z} is a subgroup of order k in (G, ·). This is called the cyclic subgroup

generated by g.

Proof. We ¬rst check that H is a subgroup of (G, ·). This follows from the

fact that g r · g s = g r+s ∈ H and (g r )’1 = g ’r ∈ H for all r, s ∈ Z.

If the order of the element g is in¬nite, we show that the elements g r are

all distinct. Suppose that g r = g s , where r > s. Then g r’s = e with r ’ s > 0,

which contradicts the fact that g has in¬nite order. In this case, |H | is in¬nite.

If the order of the element g is k, which is ¬nite, we show that H = {g 0 =

e, g 1 , g 2 , . . . , g k’1 }. Suppose that g r = g s , where 0 s < r k ’ 1. Multiply

both sides by g ’s so that g r’s = e with 0 < r ’ s < k. This contradicts the fact

that k is the order of g. Hence the elements g 0 , g 1 , g 2 , . . . , g k’1 are all distinct.

For any other element, g t , we can write t = qk + r, where 0 r < k by the

division algorithm. Hence

g t = g qk+r = (g k )q (g r ) = (eq )(g r ) = g r .

Hence H = {g 0 , g 1 , g 2 , . . . , g k’1 } and |H | = k.

For example, in (Z, +), the subgroup generated by 3 is {. . . , ’3, 0, 3, 6, 9, . . .},

an in¬nite subgroup that we write as 3Z = {3r|r ∈ Z}.

Theorem 3.14. If the ¬nite group G is of order n and has an element g of order

n, then G is a cyclic group generated by g.

58 3 GROUPS

Proof. From the previous proposition we know that H , the subgroup of G

generated by g, has order n. Therefore, H is a subset of the ¬nite set G with

the same number of elements. Hence G = H and G is a cyclic group gener-

ated by g.

Example 3.15. Show that the Klein 4-group of symmetries of a rectangle, descri-

bed in Example 3.5, is not cyclic.

Solution. In the Klein 4-group, the identity has order 1, whereas all the other

elements have order 2. As it has no element of order 4, it cannot be cyclic.

All the elements of the Klein 4-group can be written in terms of a and b. We

therefore say that this group can be generated by the two elements a and b.

Example 3.16. Show that the group of proper rotations of a regular n-gon in the

plane is a cyclic group of order n generated by a rotation of 2π/n radians. This

group is denoted by Cn .

Solution. This is the group of those symmetries of the regular n-gon that can

be performed in the plane, that is, without turning the n-gon over.

Label the vertices 1 through n as in Figure 3.4. Under any symmetry, the

center must be ¬xed, and the vertex 1 can be taken to any of the n vertices. The

image of 1 determines the rotation; hence the group is of order n.

Let g be the counterclockwise rotation of the n-gon through 2π/n. Then

g has order n, and by Theorem 3.14, the group is cyclic of order n. Hence

Cn = {e, g, g 2 , . . . , g n’1 }.

Let us now consider the group of all symmetries (both proper and improper

rotations) of the regular n-gon. We call this group the dihedral group and denote

it by Dn .

Example 3.17. Show that the dihedral group, Dn , is of order 2n and is not cyclic.

Solution. Label the vertices 1 to n in a counterclockwise direction around

the n-gon. Let g be a counterclockwise rotation through 2π/n, and let h be the

improper rotation of the n-gon about an axis through the center and vertex 1, as

indicated in Figure 3.5. The element g generates the group Cn , which is a cyclic

subgroup of Dn . The element h has order 2 and generates a subgroup {e, h}.

3 3

g2

2 2

g

g

h

1 1

n n

n’1 n’1

Figure 3.4. Elements of Cn . Figure 3.5. Elements of Dn .

CYCLIC GROUPS AND DIHEDRAL GROUPS 59

Any symmetry will ¬x the origin and is determined by the image of two

adjacent vertices, say 1 and 2. The vertex 1 can be taken to any of the n vertices,

and then 2 must be taken to one of the two vertices adjacent to the image of 1.

Hence Dn has order 2n.

If the image of 1 is r + 1, the image of 2 must be r + 2 or r. If the image

of 2 is r + 2, the symmetry is g r . If the image of 2 is r, the symmetry is g r h.

Figure 3.6 shows that the symmetries g r h and hg ’r have the same effect and

therefore imply the relation g r h = hg ’r = hg n’r .

Hence the dihedral group is

Dn = {e, g, g 2 , . . . , g n’1 , h, gh, g 2 h, . . . , g n’1 h}.

Note that if n 3, then gh = hg; thus Dn is a noncommutative group. There-

fore, this group cannot be cyclic.

D2 can be de¬ned as the symmetries of the ¬gure in Figure 3.7. Hence D2 =

{e, g, h, gh}, and each nonidentity element has order 2.

Example 3.18. Draw the group table for C4 and D4 .

Solution. D4 is the group of symmetries of the square, and its table, which

is calculated using the relation g r h = hg 4’r , is given in Table 3.4. For example,

(g 2 h)(gh) = g 2 (hg)h = g 2 (g 3 h)h = g 5 h2 = g. Since C4 is a subgroup of D4 ,

the table for C4 appears inside the dashed lines in the top left corner.

Note that the order of each of the elements h, gh, g 2 h, and g 3 h in D4 is 2.

In general, the element g r h in Dn is a re¬‚ection in the line through the center

2

g ’r

1

n’r

n’r+1

n

n’r+2

h h

r

r+1

2

gr r+2

1

n

Relation g r h = hg ’r in Dn .

Figure 3.6.

2 1 h

g

Figure 3.7. Symmetries of a 2-gon.

60 3 GROUPS

TABLE 3.4. Group D4

g2 g3 g2h g 3h

e g h gh

•

g2 g3 g2h g 3h

e e g h gh

g2 g3 g2h g 3h

g g e gh h

g2 g2 g3 g2h g 3h

e g h gh

g3 g3 g2 g3h g2h

e g h gh

g 3h g 2h g3 g2

h h gh e g

g 3h g 2h g3 g2

gh gh h g e

g2h g2h g 3h g2 g3

gh h g e

g3h g3h g 2h g3 g2

gh h g e

of the n-gon bisecting the angle between vertices 1 and r + 1. Therefore, g r h

always has order 2.

MORPHISMS

Recall that a morphism between two algebraic structures is a function that pre-

serves their operations. For instance, in Example 3.5, each element of the group

K of symmetries of the rectangle induces a permutation of the vertices 1, 2, 3,

4. This de¬nes a function f : K ’ S({1, 2, 3, 4}) with the property that the com-

position of two symmetries of the rectangle corresponds to the composition of

permutations of the set {1, 2, 3, 4}. Since this function preserves the operations,

it is a morphism of groups.

Two groups are isomorphic if their structures are essentially the same. For

example, the group tables of the cyclic group C4 and ({1, ’1, i, ’i}, ·) would be

identical if we replaced a rotation through nπ/2 by i n . We would therefore say

that (C4 , Ž ) and ({1, ’1, i, ’1}, ·) are isomorphic.

If (G, ·) and (H, ·) are two groups, the function f : G ’ H is called a group

morphism if

f (a · b) = f (a) · f (b) for all a, b ∈ G.

If the groups have different operations, say they are (G, ·) and (H, ), the con-

dition would be written as

f (a · b) = f (a) f (b).

We often use the notation f : (G, ·) ’ (H, ) for such a morphism. Many authors

use homomorphism instead of morphism but we prefer the simpler terminology.

A group isomorphism is a bijective group morphism. If there is an isomor-

phism between the groups (G, ·) and (H, ), we say that (G, ·) and (H, ) are

isomorphic and write (G, ·) ∼ (H, ).

=

If G and H are any two groups, the trivial function that maps every element

of G to the identity of H is always a morphism. If i: Z ’ Q is the inclusion

map, i is a group morphism from (Z, +) to (Q, +). In fact, if H is a subgroup

of G, the inclusion map H ’ G is always a group morphism.

MORPHISMS 61

Let f : Z ’ {1, ’1} be the function de¬ned by f (n) = 1 if n is even, and

f (n) = ’1 if n is odd. Then it can be veri¬ed that f (m + n) = f (m) · f (n) for

any m, n ∈ Z, so this de¬nes a group morphism f : (Z, +) ’ ({1, ’1}, ·).

Let GL(2, R) be the set of 2 — 2 invertible real matrices. The one-to-one

correspondence between the set, L, of invertible linear transformations of the

plane and the 2 — 2 coef¬cient matrices is an isomorphism between the groups

(L, Ž ) and (GL(2, R), ·).

Isomorphic groups share exactly the same properties, and we sometimes iden-

tify the groups via the isomorphism and give them the same name. If f : G ’ H

is an isomorphism between ¬nite groups, the group table of H is the same as

that of G, when each element g ∈ G is replaced by f (g) ∈ H .

Besides preserving the operations of a group, the following result shows that

morphisms also preserve the identity and inverses.

Proposition 3.19. Let f : G ’ H be a group morphism, and let eG and eH be

the identities of G and H , respectively. Then

(i) f (eG ) = eH .

(ii) f (a ’1 ) = f (a)’1 for all a ∈ G.

Proof. (i) Since f is a morphism, f (eG )f (eG ) = f (eG · eG ) = f (eG ) =

f (eG )eH . Hence (i) follows by cancellation in H (Proposition 3.7).

(ii) f (a) · f (a ’1 ) = f (a · a ’1 ) = f (eG ) = eH by (i). Hence f (a ’1 ) is the

unique inverse of f (a); that is f (a ’1 ) = f (a)’1 .

Theorem 3.20. Cyclic groups of the same order are isomorphic.

Proof. Let G = {g r |r ∈ Z} and H = {hr |r ∈ Z} be cyclic groups. If G and

H are in¬nite, then g has in¬nite order, so for r, s ∈ Z, g r = g s if and only if

r = s (see Proposition 3.13). Hence the function f : G ’ H de¬ned by f (g r ) =

hr , r ∈ Z, is a bijection, and

f (g r g s ) = f (g r+s ) = hr+s = hr hs = f (g r )f (g s )

for all r, s ∈ Z, so f is a group isomorphism.

If |G| = n = |H |, then G = {e, g, g 2 , . . . , g n’1 }, where these powers of

g are all distinct (see the proof of Proposition 3.13). Similarly, H =

{e, h, h2 , . . . , hn’1 }. Then the function f : G ’ H de¬ned by f (g r ) = hr , is

again a bijection. To see that it is a morphism, suppose that 0 r, s n ’ 1,

and let r + s = kn + l, where 0 l n ’ 1. Then

f (g r · g s ) = f (g r+s ) = f (g kn+l ) = f ((g n )k · g l ) = f (ek · g l ) = f (g l ) = hl

and

f (g r ) · f (g s ) = hr · hs = hr+s = hkn+l = (hn )k · hl = ek · hl = hl ,

so f is an isomorphism.

62 3 GROUPS

Hence every cyclic group is isomorphic to either (Z, +) or (Cn , ·) for some n.

In the next chapter, we see that another important class of cyclic groups consists

of the integers modulo n, (Zn , +). Of course, the theorem above implies that

(Zn , +) ∼ (Cn , ·).

=

Any morphism, f : G ’ H , from a cyclic group G to any group H is deter-

mined just by the image of a generator. If g generates G and f (g) = h, it follows

from the de¬nition of a morphism that f (g r ) = f (g)r = hr for all r ∈ Z.

Proposition 3.21. Corresponding elements under a group isomorphism have the

same order.

Proof. Let f : G ’ H be an isomorphism, and let f (g) = h. Suppose that g

and h have orders m and n, respectively, where m is ¬nite. Then hm = f (g)m =

f (g m ) = f (e) = e. So n is also ¬nite, and n m, since n is the least positive

integer with the property hn = e.

On the other hand, if n is ¬nite then f (g n ) = f (g)n = hn = e = f (e). Since

f is bijective, g n = e, and hence m is ¬nite and m n.

Therefore, either m and n are both ¬nite and m = n, or m and n are both

in¬nite.

Example 3.22. Is D2 isomorphic to C4 or the Klein 4-group of symmetries of

a rectangle?

Solution. Compare the orders of the elements given in Table 3.5. By Propo-

sition 3.21 we see that D2 cannot be isomorphic to C4 but could possibly be

isomorphic to the Klein 4-group.

In the Klein 4-group we can write c = a Ž b and we can obtain a bijection, f ,

from D2 to the Klein 4-group, by de¬ning f (g) = a and f (h) = b. Table 3.6

for the two groups show that this is an isomorphism.

TABLE 3.5

Klein 4-Group

D2 C4

Element Order Element Order Element Order

1 1 1

e e e

2 4 2

g g a

g2

2 2 2

h b

g3

gh 2 4 2

c

TABLE 3.6. Isomorphic Groups

Group D2 Klein 4-Group

· gh

e g h e ab c

Ž

gh

e e g h e e ab c

gh

g g e h a a e c b

gh

h h e g b b c e a

gh gh h g e c c ba e

PERMUTATION GROUPS 63

PERMUTATION GROUPS

A permutation of n elements is a bijective function from the set of the n elements

to itself. The permutation groups of two sets, with the same number of elements,

are isomorphic. We denote the permutation group of X = {1, 2, 3, . . . , n} by

(Sn , Ž ) and call it the symmetric group on n elements. Hence Sn ∼ S(Y ) for

=

any n element set Y .

Proposition 3.23. |Sn | = n!

Proof. The order of Sn is the number of bijections from {1, 2, . . . , n} to itself.

There are n possible choices for the image of 1 under a bijection. Once the

image of 1 has been chosen, there are n ’ 1 choices for the image of 2. Then

there are n ’ 2 choices for the image of 3. Continuing in this way, we see that

|Sn | = n(n ’ 1)(n ’ 2) · · · 2 · 1 = n!

If π: {1, 2, . . . , n} ’ {1, 2, . . . , n} is a permutation, we denote it by

···

1 2 n

.

· · · π(n)

π(1) π(2)

For example, the permutation of {1, 2, 3} that interchanges 1 and 3 is written

123

. We think of this as

321

®

123

°“ “ “».

321

12 12

We can write S2 = , which has two elements and

,

12 21

1 23 123 123

S3 = , , ,

1 23 312 231

123 123 12 3

, , ,

132 213 32 1

which is of order 3! = 6.

If π, ρ ∈ Sn are two permutations, their product π Ž ρ is the permutation obtai-

ned by applying ρ ¬rst and then π. This agrees with our notion of composition of

functions because (π Ž ρ)(x) = π(ρ(x)). (However, the reader should be aware

that some authors use the opposite convention in which π is applied ¬rst and

then ρ.)

123 123

Example 3.24. If π = and ρ = are two elements of

312 321

S3 , calculate π Ž ρ and ρ Ž π.

64 3 GROUPS

123Ž123

Solution. π Ž ρ = . To calculate this, we start at

312 321

the right and trace the image of each element under the composition.

123 12 3 12 3

=

“ °“ “

312 32 1 2

Under ρ, 1 is mapped to 3, and under π, 3 is mapped to 2; thus under π Ž ρ, 1

is mapped to 2. Tracing the images of 2 and 3, we see that

123 123 12 3

π Žρ = = .

Ž

312 321 21 3

In a similar way we can show that

123 123 12 3

ρ Žπ = = .

Ž

321 312 13 2

Note that π Ž ρ = ρ Ž π and so S3 is not commutative.

123

The permutation π = has the effect of moving the elements

312

around in a cycle. This is called a cycle of length 3, and we write this as

1 3 2 . We think of this as (1 ’ 3 ’ 2 ) . The permutation π could

also be written as 3 2 1 or 2 1 3 in cycle notation.

In general, if a1 , a2 , . . . , ar are distinct elements of {1, 2, 3, . . . , n}, the per-

mutation π ∈ Sn , de¬ned by

π(a1 ) = a2 , π(a2 ) = a3 , . . . , π(ar’1 ) = ar , π(ar ) = a1

and π(x) = x if x ∈ {a1 , a2 , . . . , ar }, is called a cycle of length r or an r-cycle.

/

We denote it by (a1 a2 · · · ar ).

Note that the value of n does not appear in the cycle notation.

1234

= 1 3 4 2 , is a 4-cycle in S4 ,

For example,

3142

123456

= 1 3 4 2 is a 4-cycle in S6 , and

whereas

314256

123456

= 2 5 4 , is a 3-cycle in S6 .

153246

Proposition 3.25. An r-cycle in Sn has order r.

Proof. If π = (a1 a2 · · · ar ) is an r-cycle in Sn , then π(a1 ) = a2 , π 2 (a1 ) =

a3 , π 3 (a1 ) = a4 , . . . and π r (a1 ) = a1 . Similarly, π r (ai ) = ai for i = 1, 2, . . . , r.

PERMUTATION GROUPS 65

Since π r ¬xes all the other elements, it is the identity permutation. But none

of the permutations π, π 2 , . . . , π r’1 equal the identity permutation because they

all move the element a1 . Hence the order of π is r.

Example 3.26. Write down π = 1 3 4 2 , ρ = 1 3 , and σ =

1 2 Ž 3 4 as permutations in S4 . Calculate π Ž ρ Ž σ .

Solution.

1 234 123 4

42= 13=

13 , ,

3 142 321 4

1 234

34=

12 .

Ž

2 143

We can either calculate a product of cycles from the permutation representation

or we can use the cycle representation directly. Let us calculate π Ž ρ Ž σ from

their cycles. Remember that a cycle in S4 is a bijection from {1, 2, 3, 4} to itself,

and a product of cycles is a composition of functions. In calculating such a

composition, we begin at the right and work our way left. Consider the effect of

π Ž ρ Ž σ on each of the elements 1, 2, 3, and 4.

π Žρ Žσ = 1 3 42 13 12 3 4

Ž Ž Ž

1 ←’ ’ ’

’ ’ ’’ ←’ 2 ←’ 1 ←’ 1

2

4 ←’ ’ ’

’ ’ ’’ ←’ 1 ←’ 2 ←’ 2

3

2 ←’ ’ ’

’ ’ ’’ ←’ 4 ←’ 4 ←’ 3

4

3 ←’ ’ ’

’ ’ ’’ ←’ 3 ←’ 3 ←’ 4

1

For example, 2 is left unchanged by 3 4 ; then 2 is sent to 1 under 1 2 ,

1 is sent to 3 under 1 3 , and ¬nally, 3 is sent to 4 under 1 3 4 2 .

Hence π Ž ρ Ž σ sends 2 to 4. The permutation π Ž ρ Ž σ also sends 4 to 3, 3 to 2,

and ¬xes 1. Therefore, π Ž ρ Ž σ = 2 4 3 .

Permutations that are not cycles can be split up into two or more cycles as

follows. If π is a permutation in Sn and a ∈ {1, 2, 3, . . . , n}, the orbit of a

under π consists of the distinct elements a, π(a), π 2 (a), π 3 (a), . . .. We can split

a permutation up into its different orbits, and each orbit will give rise to a cycle.

12345678

Consider the permutation π = ∈ S8 . Here

32815764

π(1) = 3, π 2 (1) = π(3) = 8, π 3 (1) = 4, and π 4 (1) = 1; thus the orbit of 1 is

{1, 3, 8, 4}. This is also the orbit of 3, 4, and 8. This orbit gives rise to the cycle

1 3 8 4 . Since π leaves 2 and 5 ¬xed, their orbits are {2} and {5}. The

orbit of 6 and 7 is {6, 7}, which gives rise to the 2-cycle 6 7 . We can picture

the orbits and their corresponding cycles as in Figure 3.8.

66 3 GROUPS

1

6

2 5

4 3

7

8

Figure 3.8. Disjoint cycle decomposition.

It can be veri¬ed that π = 1 3 8 4 Ž (2) Ž (5) Ž 6 7 . Since no num-

ber is in two different cycles, these cycles are called disjoint. If a permutation

is written as a product of disjoint cycles, it does not matter in which order

we write the cycles. We could write π = (5) Ž 6 7 Ž (2) Ž 1 3 8 4 .

When writing down a product of cycles, we often omit the 1-cycles and write

π = 1 3 8 4 Ž 6 7 . The identity permutation is usually just written

as (1).

Proposition 3.27. Every permutation can be written as a product of disjoint

cycles.

Proof. Let π be a permutation and let γ1 , . . . , γk be the cycles obtained as

described above from the orbits of π. Let a1 be any number in the domain

of π, and let π(a1 ) = a2 . If γi is the cycle containing a1 , we can write γi =

(a1 a2 · · · ar ); the other cycles will not contain any of the elements a1 , a2 , . . . , ar

and hence will leave them all ¬xed. Therefore, the product γ1 Ž γ2 Ž · · · Ž γk

will map a1 to a2 , because the only cycle to move a1 or a2 is γi . Hence

π = γ1 Ž γ2 Ž · · · Ž γk , because they both have the same effect on all the numbers

in the domain of π.

Corollary 3.28. The order of a permutation is the least common multiple of the

lengths of its disjoint cycles.

Proof. If π is written in terms of disjoint cycles as γ1 Ž γ2 Ž · · · Ž γk , the order

of the cycles can be changed because they are disjoint. Therefore, for any integer

m, γ m = γ1m Ž γ2m Ž · · · Ž γkm . Because the cycles are disjoint, this is the identity

if and only if γim is the identity for each i. The least such integer is the least

common multiple of the orders of the cycles.

Example 3.29. Find the order of the permutation

1 2345 678

π= .

3 5871 462

Solution. We can write this permutation in terms of disjoint cycles as

π= 1 3 8 25 4 7 6.

Ž

Hence the order of π is lcm (5, 3) = 15. Of course, we could calculate

π 2 , π 3 , π 4 , . . . until we obtained the identity, but this would take much

longer.

EVEN AND ODD PERMUTATIONS 67

1 1 1

2 3 2 3 2 3

1 2 3 = (1) = e 1 2 3 = (1 2 3) = g 1 2 3 = (1 3 2) = g 2

123 231 312

1 1 1

2 3 2 3 2 3

1 2 3 = (2 3) = h 1 2 3 = (1 2) = gh 1 2 3 = (1 3) = g 2h

132 213 321

Figure 3.9. Symmetries of an equilateral triangle.

TABLE 3.7. Group S3

(1) (123) (132) (23) (12) (13)

Ž

(1) (1) (123) (132) (23) (12) (13)

(123) (123) (132) (1) (12) (13) (23)

(132) (132) (1) (123) (13) (23) (12)

(23) (23) (13) (12) (1) (132) (123)

(12) (12) (23) (13) (123) (1) (132)

(13) (13) (12) (23) (132) (123) (1)

Example 3.30. Show that D3 is isomorphic to S3 and write out the table for the

latter group.

Solution. D3 is the group of symmetries of an equilateral triangle, and any

symmetry induces a permutation of the vertices. This de¬nes a function f : D3 ’

S3 . If σ, „ ∈ D3 , then f (σ Ž „ ) is the induced permutation on the vertices, which

is the same as f (σ ) Ž f („ ). Hence f is a morphism. Figure 3.9 illustrates the six

elements of D3 and their corresponding permutations. We shade the underside

of the triangle and mark the corner near vertex 1 to illustrate how the triangle

moves. To visualize this, imagine a triangular jigsaw puzzle piece and consider

all possible ways of ¬tting this piece into a triangular hole. Any proper rotation

will leave the white side uppermost, whereas an improper rotation will leave the

shaded side uppermost.

The six permutations are all distinct; thus f is a bijection and an isomorphism

between D3 and S3 . The group table for S3 is given in Table 3.7.

EVEN AND ODD PERMUTATIONS

We are going to show that every permutation can be given a parity, even or

odd. The de¬nition derives from an action of each permutation σ in Sn on a

68 3 GROUPS

polynomial f (x1 , x2 , . . . , xn ) in n variables by permuting the variables:

σf (x1 , x2 , . . . , xn ) = f (xσ 1 , xσ 2 , . . . , xσ n ).

For example, if σ = 1 2 3 in S4 and f (x1 , x2 , x3 , x4 ) = 2x1 x4 ’ 3x2 + 2

x2 x3 , then σf = 2x2 x4 ’ 3x3 + x3 x1 .

3 3

2

Our use of this action involves a particular polynomial D = D(x1 , x2 , . . . , xn )

called the discriminant, de¬ned to be the product of all terms (xi ’ xj ), where

i < j . More formally,

D= (xi ’ xj ).

0 i<j n

For example, if n = 3, then D = (x1 ’ x2 )(x1 ’ x3 )(x2 ’ x3 ). Given a permuta-

tion σ ∈ Sn , we have

σD = (xσ i ’ xσj ).

0 i<j n

Thus if n = 3 and σ = (12) ∈ S3 , then σ D = (x2 ’ x1 )(x2 ’ x3 )(x1 ’ x3 ) =

’D. In fact, σ D = ±D for every σ ∈ Sn , and we say that

σ is even if σ D = D σ is odd if σ D = ’D.

and

We are going to determine an easy method for deciding which is the case. A 2-

cycle is called a transposition, and surprisingly, much of the discussion centers

around determining the parity of these transpositions. We are going to show that

every transposition is odd.

Let D denote the discriminant in n variables x1 , x2 , . . . , xn , and de¬ne

Dk/m = the product of all terms in D involving xk , except (xk ’ xm )

Dk,m = the product of all terms in D involving neither xk nor xm .

For example, if n = 5, we have

D2/4 = (x1 ’ x2 )(x2 ’ x3 )(x2 ’ x5 )

D4/2 = (x1 ’ x4 )(x3 ’ x4 )(x4 ’ x5 )

D2,4 = (x1 ’ x3 )(x1 ’ x5 )(x3 ’ x5 ).

Then D factors as follows:

D = (xk ’ xm )Dk/m Dm/k Dk,m .

Now ¬x a transposition „ = (k m) in Sn , where k < m. Since „ interchanges k

and m, we see that

„ Dk/m = uDm/k where u = 1 or u = ’1.

EVEN AND ODD PERMUTATIONS 69

Since „ 2 is the identity permutation, we have

Dk/m = „ 2 Dk/m = „ („ Dk/m ) = „ (uDm/k ) = u(„ Dm/k ).

Because u2 = 1, it follows that

„ Dm/k = uDk/m .

Since „ Dk,m = Dk,m , applying „ to D gives

„ D = „ (xk ’ xm ) · „ Dk/m · „ Dm/k · „ Dk,m

= (xm ’ xk ) · uDm/k · uDk/m · Dk,m

= ’D

because u2 = 1. Hence „ is odd, and we have proved:

Proposition 3.31. Every transposition is odd.

With this we can determine the parity of an arbitrary permutation σ in Sn . The

idea is to factor σ as a product of transpositions, and we begin with the cycles.

The proof of the next result is a straightforward veri¬cation.

Proposition 3.32. Every r-cycle is a product of r ’ 1 transpositions (not neces-

sarily disjoint); in fact,

· · · ar = a1 ···

a1 a2 a2 a2 a3 ar’1 ar .

Ž Ž Ž

Since every permutation σ is a product of disjoint cycles by Proposition 3.27, it

follows that σ is a product of transpositions. This gives us the desired parity test.

Theorem 3.33. Parity Theorem. Every permutation σ ∈ Sn is a product of

transpositions. Moreover, if σ is a product of m transpositions in any way at

all, the parity of σ equals the parity of m. That is, σ is even if m is even, and σ

is odd if m is odd.

Proof. Write σ = „1 „2 · · · „m , where the „i are transpositions. If D is the

discriminant in n variables, then „i D = ’D for each i by Proposition 3.31.

Hence the effect of σ = „1 „2 · · · „m on D is to change the sign m times. Thus

σ D = (’1)m D, and the result follows.

The following result is now a consequence of Proposition 3.32.

Corollary 3.34. An n-cycle is an even permutation if n is odd and an odd per-

mutation if n is even.

70 3 GROUPS

Example 3.35. Write the permutation

123 456 78

π=

418 273 65

as a product of disjoint cycles and determine its order and parity.

Solution. As disjoint cycles π = 1 4 2 Ž 3 8 5 7 6 . Hence the

order of π is lcm (3, 5) = 15. The parity of the 3-cycle 1 4 2 is even, and

the parity of the 5-cycle 3 8 5 7 6 is even; therefore, the parity of π is

(even ) Ž (even ) = even.

Denote the set of even permutations on n elements by An . It follows from

Theorem 3.33 that An is a subgroup of Sn , called the alternating group on n

elements. For example,

±

(1 2) Ž (3 4),

(1 2 3), (1 2 4), (1 3 4), (2 3 4),

A4 = (1 3) Ž (2 4),

(1), ,

(2 4 3),

(1 3 2), (1 4 2), (1 4 3),

(1 4) Ž (2 3),

a group of 12 elements. In fact, we have

Theorem 3.36. |An | = 1 n! for every n 2.

2

Proof. Let On denote the set of odd permutations in Sn , so that Sn = An ∪ On

and An © On = ˜. Hence n! = |Sn | = |An | + |On |, so it suf¬ces to show that

|An | = |On |. We do this by ¬nding a bijection f : An ’ On . To this end, write

„ = 1 2 and de¬ne f by f (σ ) = „ Ž σ for all σ in An („ Ž σ is odd because

σ is even and „ is odd). Then f is injective because f (σ ) = f (σ1 ) implies that