<<

. 3
( 13)



>>



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

<<

. 3
( 13)



>>