Redirection
Redirection
APPLIED
ABSTRACT ALGEBRA
Ellis Horwood Series
MATHEMATICS AND ITS APPLICATIONS
Series Editor: Professor G. M. BELL,
Chelsea College, University of London
Operational Research Editor:
Professor B. W. CONOLLY,
Chelsea College, University of London
                                               KI HANG KIM
                                      Professor of Mathematics
                                                               and
                                           FRED W. ROUSH
                           Assistant Professor of Mathematics
both of Mathematics Research Group, Alabama State University
                                Montgomery, Alabama, USA
Distributors
Australia, New Zealand, South-east Asia:
JAcaranda-Wiley Ltd., Jacaranda Press
JOHN WILEY & SONS INC.,
GPO Box 859, Brisbane, Queensland 40001, Australia
Canada:
JOHN WILEY & SONS CANADA LIMITED
22 Worcester Road, Rexdale, Ontario, Canada
Europe, Africa:
JOHN WILEY & SONS LIMITED
Baffins Lane, Chichester, West Sussex, England
North and South America and the rest of the world:
Halsted Press: a division of
JOHN WILEY & SONS
605 Third Avenue, New York, NY 10016, USA
All rights reserved. No part of this publication may be reproduced, stored in a retrieval
system, or transmitted, in any form or by any means, electronic, mechanical, photocopying,
recording or otherwise, without the permission of Ellis Horwood Limited, Market Cross
House, Cooper Street, Chichester, West Sussex, England.
Table of Contents
Preface.... ..7
Chapter 4. Rings.163
           4.1 The Integers and Divisibility.164
           4.2 Euclidean Domains and Factorization.168
           4.3 Ideals and Congruences.173
           4.4 Structure of Zn.176
           4.5 Simple and Semisimple Rings.179
Open Problems.253
References.259
Index                                                          261
Preface
     We have put in exercises immediately after each section, divided into three
levels. It is strongly recommended that each student go through all the Level 1
exercises. Level 2 exercises require some experience in proving theorems, and
develop this skill. Level 3 exercises are in many cases very challenging, and
include important theorems not in the text itself. They are for the student
who is deeply interested in mathematics and wants to go beyond the material
presented in the text itself.
     The authors are happy to acknowledge an unknown official referee for
numerous very constructive criticisms and suggestions. Also, both authors are
grateful to Mrs Kay Roush for her diligent and accurate proofreading.
In this chapter we cover the most basic types of algebraic structures: binary
relations on sets. We first review material on the theory of sets itself.
     In contrast to binary operations like addition and multiplication from
two things yield a third, sum or product, a binary relation only compares two
quantities, as x < y or x = y.
     There are three kinds of binary relations we consider at greater length. A
function y = f(x) expresses the fact that x determines y, as a cause determines
its effect. Functions are of importance in many branches of mathematics. By
means of functions different structures can be compared.
     Equivalence relations like the geometric idea of similarity express the idea
that two elements are the same in some respect.
     Order relations like ‘greater than’ or lX is a subset of Y ’ establish a com¬
parison of lesser to greater. The key property of order relations is transitivity, if
x <y and y < z then jc <z. There are many varieties of order relations such
as semiorders, preorders (quasiorders) and weak orders.
     Finally we prove a well-known theorem in social choice theory using those
results. The preferences of any individual of a group over a list of possible
actions of the group can be represented by an order relation. A group choice
method can be taken as a certain type of function. The theorem shows certain
kinds of group choice methods are possible only if there are no more than two
alternatives.
1.1 SETS
In application of quantitative mathematics such as arithmetic, algebra, geometry,
calculus, differential and integral equations, and linear algebra, objects are
represented by numbers or n-tuples of numbers, which are measurements of that
object. Relationships among objects such as joint motion under gravitational or
electromagnetic forces, are represented by relationships among numbers such as
functions or equations or by relationships among functions.
10                           Sets and Binary Relations                         [Ch. 1
DEFINITION 1.1.1. Let F be a family (set) of sets. Then the union of the
members of F, denoted
             U A        or    V)   A
            AEF                F
              n   A     or    n    A
            AEF               F
is the set of all objects which are members of every set of F.
     For two sets A, B the union and intersection are written A U B and A n B.
     The set A is contained in the set B if all members of A are also members of
B. This is denoted A C B (or B D A) and it can also be said that A is a subset
of B. To prove a statement that one set (A) is contained in another (5), the
straightforward approach is to let x E A and then prove x E B.
     If A and B have exactly the same members, we say A = B. To prove a
statement that A - B one can first prove AC B and then B D A. Or one can
show A — C and C = B for some other set C. If A C B but Ai= B then A is
called a proper subset of B. Occasionally it is possible to show directly that
x EA if and only if x EB.
     Suppose we are considering subsets of a fixed set. We call this set the
universal set or universe of discourse. We denote this set by (J. If we are con¬
sidering plane geometric figures, U could be the set of all points of the plane.
Sec. 1.1]                               Sets                                      11
(1) Commutativity
    AV B = BV A,                               AC\B — BOA
(2) Associativity
    A U (B U C) = (A U B) U C,                 An(BnC) = (AnB)nC
(3) Distributive Laws
    dn(fiuc) = (A n b) u (A n c) au(bhc) = (A u b) n (A u c)
(4) de Morgan’s Law
    AUB = AOB,                                 ATVB = AUB
(5) Idempotency
    AU A = A,                                  An A = A
(6) Double Negative
    A = A
     These laws generalize from operations with just two sets to unions and
intersections of arbitrary families of sets.
DEFINITION 1.1.4. Two sets A, B are disjoint if and only if their intersection
is the null set.
The following laws apply to the null set and the universal set U = 0:
A U 0 = A, An 0 = 0
A U U = U, An u = A
     Instead sets are built from specific other sets. For example, for a set A we
may define the set of all objects of A having property P. This is a subset of A
for any property P. Sets can also be constructed by unions, intersections, taking
the set of all subsets of another set, and two processes considered later: Cartesian
product and the axiom of choice.
EXERCISES
Level 1
For sets U = {positive integers less than 8]-, A = {1,3,5,7}, B = {3,4,6,7},
C = {4,5,6,7}, compute the following: '
 1. AUB.
 2. AC B.
 3. iu(snc).
 4. dn(fiuc).
 5. (dn£)\(/in c).
 6. Give additional examples of sets.
Level 2
 1. Verify the associative law for union for a specific example (such as that
    above).
 2. Verify the distributive law A O (B U C) — (A n B) U (A n C) for a specific
    set.
 3. Which laws of sets are valid for arithmetic if one replaces U by +, n by X,
    0 by 0, and U by 1?
 4. Give examples to show the other laws of sets fail for arithmetic.
 5. Prove if A C B and B C C then ACC.
 6. Prove A~U B = AC\ B.
Level 3
 1.   Prove the distributive law A U (B n C) = (A U B) n (A U C).
 2.   Deduce the other distributive law from this using de Morgan’s law.
 3.   How many subsets does a set of n elements have?
 4.   When is |.4 UZ?| = |y4| + |fi|?
 5.   Give a formula for \A U B\ if \A n B\ =£ 0.
 6.   Explain why the method of Venn diagrams provides adequate proofs of
      equations involving at most 3 sets. (There are 8 classes of elements x in any
      such 3 sets according as x £ A or not, xC B or not, x E C or not).
 7. Show we can test any law for 3 sets by considering the example used in
    Level 1 above.
Sec.1.2]                          Binary Relations                                 13
The Cartesian product of n sets is the set of ordered n-tuples from them,
meaning things like (1, 2, 3,4,7) with entries. It is used in a number of mathe¬
matical constructions. The Cartesian product of the real numbers with itself is
the set of pairs (x, j) of coordinates in geometry, and is the basis for the name
(Cartesian geometry, after Ren<£ Descartes).
EXAMPLE 1.2.1. {a, b, c} X {a, b\ = {(a, a), (a, b), (b, a), (b, b), (c, a), (c, b)\.
     The Cartesian product of finite sets AltA2,...,An has \At\\A2\ ... \An\
elements. It has other properties related to products, such as the distributive
laws (A U B) X C = (A X C) U (B X C) and C X (A U B) = (C X A) U (C X B).
They occur in defining binary operations like addition and multiplication, and
in studying binary relations like = and <. A message or sequence of n symbols
each chosen from a set A, like the alphabet, is equivalent to an element of the
set AXAX...XA=An.
EXAMPLE 1.2.3. The relation x=y has these three properties. For all x,
x = x. If x — y then y — x. If x = y and y = z then x = z. It is an equivalence
relation.
            (1)    U A = X
                  AE F
EXAMPLE 1.2.4. The set {1,2, 3,4, 5} can be partitioned into the subsets
{1,3}, {2, 5}, {4}.
EXERCISES
Level 1
 1. Write out all partitions of {1,2}. There are two: one with a single 2-element
    subset and one with two 1-element subsets.
Sec.1.2]                          Binary Relations                                  15
2. Write out all partitions of {1,2,3}. There are one with a 3-element set,
   three with a 2-element set and a 1-element set, and one with three 1-element
   sets.
3. Let R be the binary relation on real numbers that x, y have the same sign
   or are both zero. Is this an equivalence relation? Give examples of the three
   properties.
4. What is the equivalence class of 1 in this relation? It will be -[x : x, 1 have the
   same sign}. What is this?
5. What are the equivalence classes of —1 and of 0?
6. What partition of the real numbers corresponds to this relation?
7. List 16 binary relations (not all equivalence relations) on {1, 2}. Simply list
   the possible sets of ordered pairs, such as {(1,1), (1,2), (2, 2)}.
Level 2
 1. Show that if R is an equivalence relation on S and T C S then R gives an
    equivalence relation on T.
 2. What are the equivalence classes of T1
 3. Show that on a Cartesian product AX B the relation (alf bf) R (a2, b2) if
    and only if ax — a2 is an equivalence relation. What are the equivalence
    classes?
 4. Show the relation x2(l — x2) = y2(l — y2) is an equivalence relation.
    Generalize this.
 5. What are the equivalence classes of the relation in the above exercise?
 6. Show the universal relation (J = {(x,y): xGRjGR} is an equivalence
    relation.
Level 3
 1. Let S(n, k) denote the number of partitions of {1, 2, ..., n}, or any
    ^-element set having exactly k distinct members. This is the same as the
    number of equivalence classes on an n-element set having k members. What
    are S(n, n) and S(n, 1)? The S(n, k) are called Stirling’s numbers of the
    second kind.
 2. Find a formula for S(n, n — 1). Describe all partitions with n — 1 classes.
 3. Find a formula for S(n, 2). Describe all partitions with 2 classes.
 4. Tell why S(n + 1, k) = kS(n, k) + S(n, k —1). (Add an element to any
    existing equivalence class or make it a new class.)
 5. Compute S(n, k) for n < 5 using this formula laid out in a table
           2    1     1
           3    13         1
   Each time to get an entry in a lower row in column k, add the entry to
   upper left of it and k times the entry just above it.
6. How many symmetric, reflexive binary relations are there on an ^-element
   set? The number of transitive relations is an unsolved problem.
16                          Sets and Binary Relations                      [Ch. 1
1.3 FUNCTIONS
A function is a relationship in which a quantity uniquely determines a second
quantity. For instance x uniquely determines x2 + x + 1 but it does not
determine y if the relation is x < y.
EXAMPLE 1.3.1. On the real numbers 1/x is a partial function with domain
{x : x =£ 0}.
     A partial function differs from a function only in that it may not be defined
for all x. The following are situations in which some quantity can be regarded as
a function.
EXAMPLE 1.3.3. The output of a machine is a function of its input and its
internal state.
     For a function f and element x & S, f(x) denotes the unique number $uch
that (x, /(x)) G f.
     There is a method of obtaining a product of functions on general sets called
composition. The second function is applied to the result of the first function.
In algebraic terms, the first function is substituted into the second.
DEFINITION 1.3.4. The identity function i from a set to itself is the function
defined by i(x) = x for every x.
 18                             Sets and Binary Relations                      [Ch. 1
Proof (ls o f) (x) = /(t5(x)) = /(x) and (/ o ir) (x) = iT(f(x)) = f(x). □
EXAMPLE 1.3.15. There is a function from the positive integers into itself
which is 1-1 but not onto, given by /(x) = x + 1.
      For finite sets any two of these conditions implies the third: / is 1-1,/ is
 onto, |S| = ir|.
EXERCISES
Level 1
 1. Is this binary relation a function on {1,2, 3} : {(1,1), (3, 3)}?
 2. Is this binary relation a function on {1, 2, 3} : {(1, 1), (1,2), (2, 1), (3, 3)}?
 3. Write the composition of / with itself where /(1) = 2, /(2) = 3, /(3) = 1.
 4. Give an example of a function from {1,2, 3} to {1,2, 3, 4} which is 1-1 but
    not onto.
 5. Can a function from {1, 2\ to {1, 2, 3} be onto?
 6. Can a function from {1,2, 3, 4} to {1, 2, 3} be 1-1?
Level 2
 1.   Write out the functions from the set {1, 2, 3} to the set {1, 2} .
 2.   Show by an example that fog^gofin general.
 3.   What is the composition of xn and xml
 4.   What is the inverse function to x"?
 5.   Prove a composition of 1-1 functions is 1-1.
 6.   Prove a composition of onto functions is onto.
Level 3
 1.   How many functions exist from a set of n elements to a set of n elements?
 2.   What is the inverse function toy = x2 + x + l?
 3.   What is the inverse function toy = x + l/x?
 4.   Find a 1-1 correspondence from positive integers to all integers.
 5.   Show this is a 1-1 correspondence from pairs of positive integers to positive
      integers:
                           (n + m)(n + m — 1)
              f(n, m)      -1- m
                                      2
                            Sets and Binary Relations                          [Ch. 1
20
EXAMPLE 1.4.2. The relation < is a strict partial order, but < is not a strict
partial order.
Proof. Let P be a strict partial order. Let aPb, bPa. Then aPa by transi¬
tivity. This is a contradiction. So PUi is antisymmetric. Let (a, i)GPUt,
(b, c) E P U l. If both are in P, so is (a, c). If a = b or b = c then (a, c) = (b, c)
or (a, b) which belong to P. Thus P U i is transitive. Since i C P U i, P U i is
reflexive. So P U i is a partial order.
     If P is a partial order, i C P by reflexivity. The relation P\i is irreflexive
since i is removed. Let (a,i)eP\i, (i,c)GP\i. Then (a, c) G P. Suppose
(a, c) Ei. Then (a, b) E P, (b, a) E P, a b. This contradicts antisymmetry. □
Sec. 1.4]                        Order Relations                                21
EXAMPLE 1.4.3. The relation that one triangle has area at least as large as
another is a preorder.
     Every partial order is a preorder, but some preorders are not partial orders.
However, every preorder can be reduced to a partial order on certain equivalence
classes.
EXAMPLE 1.4.4. In the preceding example 2d would be the relation that two
triangles have equal areas, 2s that the area of one exceeds the area of the other.
    Partial orders on a finite set must have maximal elements, that is elements
such that no other is greater. However, these elements may not be greater than
every other.
22                          Sets and Binary Relations                       [Ch. 1
EXAMPLE 1.4.6. In the set {1,2, 3} order <, 3 is maximal since 3 ^ x for
x    3, and 1 is minimal.
     The names maximal and minimal may be reversed according to the situation.
Maximal means x < y is false.
EXAMPLE 1.4.7. Among subsets of {1,2} the sets {1} and {2} are not
comparable. They form the only incomparable pair.
THEOREM 1.4.3. Let P be a partial order on a finite set S. Then P has at least
one maximal element and at least one minimal element. In fact for u E P there
is at least one maximal element x such that (u, x) E P.
Proof. For |S|= 1, the element is both maximal and minimal. Suppose this
theorem holds for ISI = k. Let |S| = k 4-1. Let u, y E S, u ¥= y. Let Q be
P with y removed. By induction assumption Q has a maximal element x,
(u, x) E P. If (x, y) ^ P then x is maximal in P also. If (x, >»)£? then y is
maximal in P, else if (y, z) E P, z ^ >>,then z E S\{y}, (x, z) E Q contradicting
maximally of x in Q. Moreover by transitivity (u, y) E P. The proof for a
minimal element is similar.                                                     □
    This shows that for a finite partially ordered set (poset) any element is
< some maximal element.
EXAMPLE 1.4.8. {(1,1), (2, 2), (3, 3), (1,2), (1,3)}. The set has two maximal
elements 2,3. Neither is greater than the other: they are incomparable.
EXAMPLE 1.4.9. The set of positive integers is not finite, and has no maximal
element.
    To obtain a result analogous to this theorem for infinite sets, and to further
obtain results on partial order, the idea of a linear order is needed. A linear
order is a partial order satisfying trichotomy: x > y, y < x or y = x.
EXAMPLE 1.4.11. The relation < on subsets of the real numbers is a linear
order. The relation C is not in general.
EXAMPLE 1.4.12. This is not true for infinite linearly ordered sets. The set
of negative integers under < is not isomorphic to the set of positive integers
under <.
AXIOM OF CHOICE. For any indexed family Fa of nonempty sets there exists
an indexed family xa such that xa G Fa for each a.
     The Hausdorff maximal principle and its equivalents are quite important in
abstract algebra, for infinite sets. An example is as follows.
Proof. Let P be a partial order on S. Consider the family of all partial orders
on S containing P. It is itself a poset under inclusion. Take a maximal chain
C in that set. The union U of its members will also be a partial order on S.
For example take x, y, z G S. Let (x, y) G U, (y, z) G U. Then (x, y) G Pu
(y, z) G P2 for some Ply P2 in C. By definition of chain, Px C P2 or P2 C Px.
Assume the latter. Then (x, y), (y, z) G Px so (x, z) G Pv So (x, z) G U. This
proves U is transitive. Proofs of reflexivity and antisymmetry are similar.
Since C is maximal, U is not contained in any other partial order on S else that
would give a larger chain. This will be used to get a contradiction if U is not
a linear order. Suppose not. Then for some x =£ y, (x, y) £ U, (y, x) ^ U. Then
let T — U together with {(w, z): (w, x) G U and (y, z) G U}. Then T properly
contains U since (x, y) G T. It can be shown that T is a partial order, by
checking various cases. For example let (w, z) G T\U, (z, s) G U. Then
(w, x) G U, (y, z) G U. Then (w, x) G U, (y, s) G U. So (w, s) G T. Let
(w1( Zj) G T\U, (zi, z2) G T\U. Then (y, zx) G U, (zlt x) G U so (y, x) G U.
This is false. The other cases of transitivity and antisymmetry are proved in a
similar way. This gives a contradiction.                                      □
EXERCISES
Level 1
 1. Prove that the identity relation on any set is a partial order. Is any
    equivalence relation a preorder (quasiorder)?
 2. What are the maximal and minimal elements of this strict partial order:
    {(1, 3), (1,4), (2, 3), (2, 4)}? There are two of each.
 3. What are the maximal and minimal elements of this strict partial order:
    {(1, 3), (2, 3)}?
 4. Finite posets are represented by diagrams called Masse diagrams. To draw
    one, first find the minimal elements and label them as separate points at the
    bottom level. Then for all points z such that (m, z) G P for minimal m but
Sec.1.4]                            Order Relations                             25
2 3
Level 2
 1. Draw the Hasse diagram of {(1, 2), (2, 3), (1, 3)}.
 2. Draw all possible Hasse diagrams for 3 elements (there are 5). Two are as
    follows:
                                                           o
             o              o                o             o
                 Identity                        {(2,3)}
Level 3
 1. Draw all possible Hasse diagrams (19) for 4 elements.
 2. Prove that every partial order P on a set S is an intersection of linear
    orders on S. It suffices to show that if (y, x) ^ P then there exists a linear
26                          Sets and Binary Relations                         [Ch. 1
     order L such that (y, x)     L but P C L.(P will then be the intersection of
     all these L.) The proof is similar to the proof of Theorem 1.4.5, with C
     being the family of all partial orders containing P but not (y, x). The same
     T will do.
3. Represent the strict partial order {(1, 2), (1,3)} as an intersection of
   linear orders.
4. A semiorder is a binary relation R such that (1) R is irreflexive, (2) if
   (x, y) G R and (z, w) G R then (x, w) E R or (z, y) G R, (3) if (x, y) G R
   and (y, z) G R then for all w either (x, w) E R or (w, z) G R. Prove a
   semiorder is transitive, and is therefore a strict partial order.
5. Every 3-element partial order is a semiorder. Find two 4-element partial
   orders which respectively violate (2), (3) of the above definition and are not
   semiorders.
6. Suppose S' is a finite set and / a function f:S-+T and e > 0. Then show
   {(x, y): /(y) > /(x) + e} is a semiorder. This leads to the interpretation
   that ‘x is distinguishably greater than y ’ is a semiorder. The converse of this
   result is also true. See Scott and Suppes (1958), Luce (1956), Rabinovitch
   (1977), Scott (1964), Suppes and Zinnes (1963).
7. Prove for a semiorder R that the sets Lx = {y: (x, y) G P} and the sets
   Lx = {y - (y, x) G P\ are each linearly ordered under inclusion and that
   Lx ^ Ly, Lx ^ Ly cannot happen.
(except for 1 + l,the same as for ordinary addition and multiplication.) However,
it has this difference, B obeys the rules of set intersection and union, rather than
those of arithmetic. For example,
x + 0 = x + x = x, x • 1 = x • x = x, x • 0 = 0, x • 1 = x
EXAMPLE 1.5.1. Logic can be studied using B. In this case, ‘1’ is ‘true’, ‘0’ is
‘false’,‘+’ is ‘or’,‘X’is‘and’,‘C’is‘not’. So (p or q) and not r would be translated
            (P + q)rc
Statement jc implies y if and only if x <y.
     Boolean algebras are also used in the study of computer and other switching
circuits.
'0 1 0~
_0 1 0.
     The following operations are simply taken entry by entry for Boolean
matrices A = (fly), B — (by).
             Complement:        Ac = (af/c)
     Inequality is also defined entry wise: A < B if and only if for all i, j,
atj < by. This is a partial order. The strict partial order A < B means ay < by
for at least one i, j and ay < by for all i, j.
28                                            Sets and Binary Relations                                   [Ch. 1
EXAMPLE 1.5.5.
     (a)                     +
           .1    0.                  _0            0_            .1       0.
     (b)                     ©
           .1    0.                  _0            0.            .0       0.
                         c                              -
           '1    o   '                '0            1
     (c)
           _0    0.                   _1            1
           '1    o   '                1            f
     (d)                     <
           .0    1.                  .0            1.
Inequality means the places where 1 occurs in one matrix is a subset of the places
where 0 occurs. The operation +, ©, C, and the relation < obey all the laws stated
earlier for 8-
     There are two other operations on Boolean matrices: transposes and matrix
multiplication.
Transpose: Ar = (a,,)
EXAMPLE 1.5.6.
                 0“ ■i                                                                               ■1
                                                                      +
                                                                      o
                                                                      o
                                                            1_
           -1                              r                                          l* l + o- r
                                                                 •
                                                                                                          r
     (b)
           -1    1-          .0               1.            .1 • 1+ 1 • 0             l • l + i-1.   .1   l.
                                 r                                            'i      i   r
                                      1_
                                      o
0 0
(c) 1 0 0 0 0 1 = 0 1 0
            0    1               i.       .1            i        i.           _i      i   i.
The transpose changes the (z, /)-entry to location j, i. Rows of A become
columns of AJ, and vice versa.
     The matrix product is the same as the product of ordinary matrices except
that operations are Boolean, so that 1 + 1 = 1. The (z, /)-entry may be calculated
Sec.1.5]                    Boolean Matrices and Graphs                            29
EXAMPLE 1.5.7. To form the product of Example 1.5.6. (c), Aj*: a13 = 1
take B3* = (1 1 1). A2* '■ a21 = 1 take Bx* = (0 1 0). A3*: a32 = a33 = 1 take
B2* + B3* = (0 0 1) + (1 1 1) = (1 1 1).
(A + B)t = At + Bt
(A 0 B)t = At © Bt
(Ac)t = (At)c
(AB)t = btat
       Boolean matrix products obey these laws (as ordinary nonnegative matrices
do):
              (AB)C = (AB)C
Proof. The proof is straightforward but lengthy. The matrix entries determine
precisely which pairs are in R. And for any matrix A we can define a relation by
30                            Sets and Binary Relations                        [Ch. 1
{Of,   Xj):   di) = 1} which goes to it. This proves the mapping of relations to
matrices is 1-1 and onto.
    We verify the statement about matrix products. Take a third set
Z = {z1( z2,..., zq} and a second relation P with matrix B. Let C = AB. Then
Cy = 1 if and only if 'Zaikbkj = 1, i.e., for some k, aikbkj = 1 if and only if
for some k, aik = 1 and bkj = 1 if and only if for some k, (xityk) E R and
(yk, Zj) G P if and only if (xit Zj) E R o P.
       Proofs for other operations are similar.                                    Q
EXAMPLE 1.5.8. The relation {(1, 1), (1,2), (2, 2)} has this graph.
                   Q->Q
                   1              2
EXAMPLE 1.5.9. The relation {(1,5), (2, 3), (3, 4), (2, 4)]- has this graph.
5 3
      First the correct number of points should be drawn. Then they can be
labelled. Then for each pair in the binary relation, a directed segment is drawn
between the vertices having the same labels. Two-way arrows (or edges without
arrows) may be used if (x, y) and (y, x) are in R.
      Graphs are useful in studying questions related to powers of a binary relation
under composition R o R o ... o R. In graph theory questions of connectedness,
existence of various types of paths, and families of subsets such that no point
joins another of the same subset are studied.
      The graph of an n X n Boolean matrix can be drawn. Vertices are drawn
and labelled 1, 2,..., n. An arrow is drawn from i to / for each entry atj which
is 1.
Sec.1.5]                               Boolean Matrices and Graphs            31
EXERCISES
Level 1
 1. Compute (1 + lc) • (0 + 0C) in Boolean arithmetic.
 2. Prove the dual distributive law x + yz = (x + y) (x 4- z) in Boolean algebra
    by considering three cases (1) x = 1,(2) y = z = 1,(3) x = 0 and y or z is 0.
 3. When is xy equal to 1? How is this like a statement ‘x and y’l
 4. Add
           ‘1          1   o       '        '0   0   r
            0          1       1       ©     0   1   0
           .1          1   0_               _1   0   0.
“0 1 0 "
1 0 1
.0 1 0.
Level 2
 1. Prove x + y = x if and only if x > y in a Boolean algebra.
 2. Prove addition of Boolean matrices is associative (assuming addition is
    associative in 8).
 3. Prove the distributive law for Boolean matrix products (assuming the laws
    for 8).
 4. Multiply
           "l      0           1       o"
                10             10
            0      10                  1
0 10 1
   times itself.
32                            Sets and Binary Relations                     [Ch. 1
0 1 0 0~
0 0 10
0 0 0 1
_1 i 0 0_
Level 3
 1. Suppose 8 is replaced by any system in which +, X are defined. Can Boolean
    matrix multiplication be defined?
 2. A Boolean row vector v is a 1 X n matrix. Prove that A = B if and only if
    vA = vB for all row vectors v. (Choose v with 1 entry.)
 3. Prove {At*)B is the ith row of AB.
 4. Prove that if / < A, v < vA and that if v = vA then v — vA1 for all i > 0.
    Here / is an identity matrix.
 5. Use (2), (3), (4) to prove that for A > I, An~x equals all powers Ak, k>n— 1.
 6. A row basis is the set of vectors formed by rows of A which are not sums
    of other, lesser rows of A. The row rank pr of a Boolean matrix is the
    number of vectors in a row basis. Prove that pT(AB) < pr(^4). Must
    pT(AB)< pr(5)?Try 4 X 4 Boolean matrices with 3 nonzero rows.
 7. Prove that in a graph every point is accessible from every other by a directed
    sequence of edges if and only if (/ 4- A)n has all ones in it.
 8. Prove (/ + A)n is the Boolean matrix of a preorder. This relation is called
    reachability. What is its graph-theoretic interpretation?
Also two voters prefer b to c and two voters prefer c to a. Thus for any chosen
alternative, a majority will prefer some other alternative.
     Can a more complicated voting procedure avoid this paradox? Kenneth
Arrow in 1950 proved there is no voting procedure satisfying five basic condi¬
tions. (However, voting procedures can exist satisfying all but one, called
independence of irrelevant alternatives.)
     Let X be a set of alternatives which the group N of voters, represented as
{1, 2 ..., n] will choose. The preferences of individual i will be expressed as a
binary relation /?,• where xR(y is interpreted as the voter liking x at least as well
as y, for xjGl. If the voter is rational, the relation should be transitive: if
he likes y at least as well as x, and z at least as well as y, he will like z at least
as well as y. Moreover it should be complete: either he likes x at least as well as
y or he likes y better than y.
     Here we will assume that no voter is exactly indifferent between any two
alternatives, so that /?,- is a linear order.
     For the linear order /?,• of preferences of voter i, let Pt denote the
corresponding strict partial order.
     The group preference is expressed as a social welfare function
       R2, ...,Rn). Here |F is the function which assigns to the individual
preference relations Ru R2, ..., Rn the group preference relation in this case.
The group preference relation gives the set of pairs (x, y) of alternatives such
that group either chooses x over y or is indifferent about them. The binary
relations Rlr R2,..., Rn He in a set of binary relations called the domain.
   The first two assumptions on the social welfare function are universal
domain and weak ordering.
    Thus every individual preference which is a linear order can occur (weak
orders are frequently used instead).
EXAMPLE 1.6.3. Majority rule satisfies this condition: if every one prefers x
to y then a majority does.
Proof. Pareto optimality means that if the (i, /)-entries of R(i) are 1 and the
(j, i)-entries are zero (each of which implies the other for linear orders), then
fij = 1, fji = 0. So if all Rt have a 1 entry |F is 1. This is |F > R{ 1) © R{2) © ...
© R(n) in the (/, /)-entry. And if all R(i) have a 0 entry, |F is 0. This is
\V<R(l)+ R(2)+ ... + R(n).                                                         □
EXAMPLE 1.6.5. Majority voting and any dictatorial social welfare function
are independent of irrelevant alternatives.
     This condition means that if preferences of each individual i over x, y are
the same in profiles R, Q (a profile is an n-tuple of preferences) then the group
preference is the same in R, Q regarding x, y. The remaining assumptions are
these.
Proof.      Being   a function means, that if for all i, rjk(i) — Qjk(i) then
fjk(Ri,R2,, Rn)= fjkiQu Qi.Qn)- But for linear orders’ rik = rkjC so
rk.(i) = qk].{i) also. Now the assertion follows directly from the definition. □
Proof. Write /yOi, a2,..., an) to express ftj as a function of the (i, /)-entries
ofRu R2,... ,Rn by Proposition 1.6.3. By completeness for i 4= j,
fij( l,1.1) = 1
fij( 0,0,...,0) = 0
     Let aha2,..., an, bx,b2,..., bn, cltc2,...,cn be such that 0/h, < ct < at + bt
for all i. We will construct a profile Rf such that for any three fixed alternatives
x, y, z, x R( y if and only if a,- = 1, y R{ z if and only if bt = 1, x Rt z if and
only if ct = 1. To do this use this table:
a,- b( ct Preference
                0 0 0                    ,zyx
                1 0 0                     zxy
                010                       yzx
                101                       xzy
                0 1 1                     yxz
                111                       xyz
EXERCISES
Level 1
 1. For only two alternatives, name a social welfare function satisfying
    assumptions 1-5.
 2. What assumption does majority rule fail to satisfy in general?
 3. Which assumptions does a dictatorial social welfare function satisfy?
 4. Suppose we count point totals as follows: an alternative receives m — 1
    points for being first choice of anyone, m — 2 for being second, etc., where
Sec.1.6]                   Arrow’s Impossibility Theorem                           37
Py P2
              xyz    xyz
              yzx    yxz
              zxy    xyz
Level 3
 1. Prove Arrow’s Impossibility Theorem for the domain |D of all weak orders
    (nondictatorial must be weakened so that just if voter k strictly prefers any
    x to y so does the group. If he is indifferent, the group choice may differ).
 2. Explain why the number of weak orders on a set of m elements is
    2 S(n, k)k\. Use the classification of preorders. The partial order involved
    must be a weak order.
38                         Sets and Binary Relations                        [Ch. 1]
In this chapter we take up systems having a single binary operation, such as multi¬
plication. Most systems of interest satisfy the associative property (ab)c = a(bc)
or a related property. In them the commutative property ba = ab is not always
true (for instance matrix multiplication). A system with the associative property
is called a semigroup. Semigroups can be studied in several ways. One is to find
generators and relations. A set of elements is a set of generators if all elements of
the system are products of a sequence from the set. For instance —1,1 generate
the integers as a semigroup under addition since every interger is a sum of copies
of —1,1. Relations tell when two products of generators are the same, for
instance 1 + 1 — 1 = 1.
     Another method is to study subsemigroups, ideals, and quotient semigroups.
A subsemigroup is a subset which forms a semigroup by itself under the product.
An ideal is a subsemigroup such that every product of an element in it and an
element outside it is in it. For instance an even integer times any integer is even.
A quotient semigroup is a semigroup made up of equivalence classes of some
equivalence relation under the same product.
     Green’s relations are defined from the ideals and enable any semigroup to
be expressed as the union of equivalence classes. They to some degree express
the relation between semigroups and groups.
     Any set of binary relations generates a semigroup. Binary relations such
as ‘x associates with y’ have been studied in particular groups of people by
sociologists.
     For any machine, such as a computer, there is a semigroup associated with
the transitions from one internal state to another determined by inputs. This is
a semigroup of functions under composition.
     An abstract concept of finite-state machine has been defined involving a
set of inputs, a set of outputs and a set of internal states. Such machines can
accomplish various theoretical tasks such as adding numbers or recognizing a
programming language. Programming languages themselves can be represented in
terms of free semigroups.
40                          Semigroups and Groups                          [Ch. 2
2.1 SEMIGROUPS
A semigroup is about the simplest and most general mathematical structure of
wide significance.
            x o (y o z) = (xoj')oz,
Sec.2.1]                             Semigroups                                   41
EXAMPLE 2.1.2. The following are semigroups, on any set S: all binary
relations on S, all transformations on S, all onto transformations, all 1-to-l onto
transformations, all transformations sending a given subset T into itself, all
transformations, having an image of at most k elements.
     More generally all transformations on a set preserving some structure such as
a partial order or a binary operation, form a semigroup.
    Another class of operations giving rise to semigroups are least upper bound
and greatest lower bound of two elements, provided these are unique.
EXAMPLE 2.1.3. For any subset of the real numbers, the operations sup{x, y}
(the larger of x, y) and inf (x, y} (the smaller of x, y) are associative.
DEFINITION 2.1.3. A lattice is a partially ordered set S in which for any two
elements a, b there exist unique elements a A b, a V b such that (l)«A6<a,
a A b < b, (2) a V b > a, a V b > b, (3) if c > a, c > b then c > aV b,( 4) if
c < a, c < b then c < a A b. The elements a V b, a A b are called the least
upper bound and greatest lower bound of a, b, also the join and meet of a, b.
    Not all posets are lattices, but many of the most important ones are.
42                              Semigroups and Groups                               [Ch. 2
EXAMPLE 2.1.4. The following are lattices: the real numbers, any linearly
ordered set, the set of all subsets of a set, the set of all partitions of a set, the set
of all lines and planes through the origin in        together with {0} and          itself.
Here      is 3-dimensional space, and the partial order is inclusion in the last three
examples.
{(1, 1), (2, 2)}, {(1, 1), (2, 2), (3, 3), (3,1), (3, 2)}.
Commutativity: a V b = b V a
Idempotence: a V a = a
The last property is not true for semigroups obtained by addition or multiplica¬
tion of integers or real numbers, and indicates something of the variety of
semigroups that exist.
    Finite lattices can in fact be described as finite idempotent commutative
semigroups with identity.
    A different type of semigroup is made up of sequences of symbols called
words. The product of two words is obtained by writing one word directly after
another. For instance (xyz) (xxzy) = xyzxxzy. Associativity follows from
(wi w2)w3 = wi w2 w3 = wi(w2 w3).
    The importance of free semigroups comes from the fact that every semi¬
group is the image of a free semigroup under an onto function / such that
f{xy) — f(x)f(y).
EXAMPLE 2.1.6. The free semigroup generated by x,y has as its 5 elements
  y, xy, yx, xx, yy, xyx, xxx, yyx, xyy, xxy, yyy, yxy, yxx and so on.
     A free semigroup on one generator is commutative, but not free semigroups
on more than one generator. All free semigroups on at least one free generator
are infinite.
EXERCISES
Level 1
 1. Give 3 additional examples of semigroups (what about complex numbers?).
 2. Let /^onI = (1,2,3} be given by/(l) = 2,/(2) = 3, /(3) = 3, ^(1) = 3,
    g(2) = 1, g(3) = 3. Calculate / o g and g o f.
 3. If h is given by fc(l) = 2, h{2) = 3, h(3) = 1 verify the associative law for
    (/ o g) o h. Here f and g are the same as in the above exercise.
 4. What is 2 V 3? 3 A 2?
 5. Prove in any lattice that a l\ a — a, a\! a = a, a f\ b — b f\ a, a \J b — b V a.
44                          Semigroups and Groups                         [Ch. 2
 6. What is the product (xyzz) (zyz)? Give examples to illustrate the fact that
    free semigroups are associative but not commutative.
Level 2
 1. Consider all transformations on real numbers of the form ax + b. Prove this
    is a semigroup (i.e. prove closure) and give a formula for the composition of
    ax + b and cx + d.
 2. What are A, V in the lattice of subsets of a set?
 3. Prove that if (S, o) is a semigroup then another semigroup can be defined as
    (S, *) where x * y — y ox. This is called the opposite semigroup.
 4. Write down all transformations on the set {1,2, 3}.
 5. Compute the composition of all transformations on {1,2, 3} having at most
    two elements in their image.
 6. Prove that transformations having image size < k form a subsemigroup, and
    even more, an ideal: if / does so do / o g and g o f for all g.
 7. Write out all words of length exactly 4 in the free semigroup on 2 letters
       y.
Level 3
 1. How can the semigroup of n X n matrices over R be regarded as a semigroup
    of transformations?
 2. Let S be a finite commutative, idempotent semigroup with an identity e
    such that ex = xe = x. Define a partial order such that xy = x Vy. Prove
    it is a partial order.
 3. Define A in the situation of the last example. Prove this gives a lattice.
 4. How many transformations are there on a set of n elements?
 5. Describe free semigroups on one generator. Give an isomorphism from such
    a free semigroup to the positive integers.
 6. When will two elements of a free semigroup commute?
abed
            d     c     d      c     d
Sec. 2.2]                      Generators and Relations                            45
      For the positive integers under addition {1} is a generating set since every
positive integer has the form 1 + 1 + ... + 1. A free semigroup on 2 generators
illustrates the fact that a finite set of generators can generate an infinite
semigroup.
      In terms of transformations a generating set is a set from which all
transformations of the semigroup can be produced. A generating set for the
transformations on Rubik’s cube has 6 elements, a quarter-turn clockwise
for each face.
                           3-1 = 3,     2 • 3 = 3 • 2.
46                             Semigroups and Groups                          [Ch. 2
I2 3
12 3 3
2 3 3 3
3 3 3 3
Proof. Straightforward.
DEFINITION 2.2.5. The semigroup with generating set C and defining relations
W; = vt is the quotient semigroup associated with the congruence E(Vj = wf) on
the free semigroup generated by C.
EXAMPLE 2.2.6. The semigroup with generating set x and defining relation
x - x4, has 3 distinct elements x, x2, x3. (We have x4 = x, xs = x, x4 — xx = x2,
x6 = x4x2, and so on.) Products are given by the table below.
x x2 x3
x2 x3 x
x3 x x2
x3 x x2 x3
relations which imply every, relation. For any set of relations in a semigroup S,
the next proposition shows there is a homomorphism of the semigroup defined
by those relations, onto S. This will be an isomorphism if the set of relations is
complete.
Proof. Straightforward.
    To check that a complete set of relations has been found, it may be necessary
to determine the semigroup determined by a set of relations vt — w{ in certain
generators. First deduce some consequences of these relations. Then use these to
show that every word is equal to a word from a list of words S. (The set S
should be such that no two words are equal under the relations. If not, delete
one of the equal words.)
    Compute products in S by taking the products of powers of words and
reducing them to elements of S by means of the relations. If products are
associative and the relations vt = wt are satisfied then the semigroup determined
by the given relation has been found.
     For many elementary semigroups this procedure can readily be carried out.
However, it can be very difficult. In fact, it has been proved that the problem
of deciding whether or not two words are equal, in a semigroup specified by
generators and relations, can be undecidable.
     There is a different method for studying semigroups, without generators and
relations, taken up in the next section.
EXERCISES
Level 1
 1. A more general rectangular band can be definied on any nonempty Cartesian
    product set S X T by the multiplication (z, /) (n, m) = (z, m). Prove this is
    associative.
Sec. 2.2]                      Generators and Relations                           49
e x
Level 2
 1. Consider the transformations fit i = \,2,... ,n — \ on {1, 2,..., n} such
      that fi(i) = i + 1, fi(i + 1) = / and /,-(*) = x for other x. Prove /} o ft = e
      where e(x) = x for all x.
 2.   Prove fi o fj = fj o fa whenever / A i ± 1.
 3.   Prove (/} o /m)2 = fi+1 o ft for i = 1, 2, ...,n- 2.
 4.   Describe all homomorphisms from the positive integers under addition to
      itself.
 5.   Write out the set of transformations from {1,2} into itself. Let x be the
      transposition interchanging 1, 2 and y the constant transformation y(i) = 1
      for i = 1, 2. Prove the other two can be expressed as products of x, y.
 6.   Give as far as you can, a complete set of relations on x, y in the above
      exercise.
 7.   Describe the semigroup with generators x, y and defining relation xy = yx.
Level 3
 1. What semigroup is defined by these relations on x, y: xy = yx, xxy = x,
    yxy = yl
 2. Consider the semigroup defined by these relations: xx=yyy, xxx = x,
    yyyy = y, xyx = yy. How many elements does it have? What is xx = yyy ?
 3. Classify homomorphisms from a free semigroup into itself.
50                           Semigroups and Groups                          [Ch. 2
 4. Show that for any set C any semigroup S and any function f:C-+S there
    exists a unique homomorphism g from the free semigroup generated by C
    into S such that /(c) = g(c) for c E C. This is the ‘universal property’’ of
    free semigroups.
 5. Show that if a semigroup has the property of the above exercise it is
     isomorphic to a free semigroup.
 6. Consider the semigroup of all transformations f(x) — ax + b where a = ±1
     and b is an integer. Find a set of generators for this semigroup, and some
     relations among them.
 7. Give some homomorphisms from the semigroup of n X n matrices under
     addition to the real numbers.
EXAMPLE 2.3.3. The set ofnXn singular matrices over a field has the ideal
consisting of all singular matrices, since if X has determinant 0, so does YXZ.
EXAMPLE 2.3.4. The set of positive integers under multiplication has an ideal
Im consisting of all multiples of m for a positive integer m. This is true because
if x is a multiple of m so is yxz.
EXAMPLE 2.3.5. The two-sided ideal generated by* in the additive semigroup
of positive real numbers is all real numbers y>x.
DEFINITION 2.3.6. Two elements x,y are H-equivalent if and only if they
are both R and L-equivalent. They are D-equivalent if and only if there exists z
such that xRz and z L y.
     Thus H is the intersection relation RflL and D is the composition R o L.
In a commutative semigroup all 5 relations coincide. In a group any two elements
are equivalent under each relation.
EXAMPLE 2.3.8. Two matrices over a field are J (D)-equivalent if and only
if they have the same rank. They are R (L)-equivalent if and only if their row
(column) spaces are identical. They are H-equivalent if and only if their rows
span the same space and their columns span the same space.
THEOREM 2.3.1. The Green’s relations are equivalence relations. The relations
R, L, J can alternatively be defined as follows, in a semigroup S:
Proof. First (1) will be proved. Suppose a L b. Then Sla = S1b. So a G Svb
and b G S1a. So a = yb, b — xa for some rjGS1.
    Suppose a = yb, b = xa. Then a G Slb and b G S1a. Thus
S'a C S'iS'b) = (S'Sfyb = S'b. And S'b C Sla. So a L b. This proves (1).
    The proofs of (2) and (3) are similar.                               □
THEOREM 2.3.3. For any finite semigroup the relations J and D coincide.
     Within a D-class the elements can be arranged in R and L-classes like bottles
in a crate (this is called the egg box picture). Let R 1( R2,..., Rn be the R -classes
contained in D and Li,L2,..., Lm the L-classes contained in D. Then the
H-classes are
Ri Cl L\ R\ C Li2 ■,.. R\ C Lm
Rn H Zj Rn C L2 . .. Rn n Lm
     These H-classes all have the same size, and there is an explict isomorphism
 between any two. For details on this and succeeding results, see Clifford and
 Preston (1964).
      Regularity is a concept related to existence of certain weak inverses of an
 element.
    Proofs of all but (3) can be found directly in Clifford and Preston (1964)
and (3) follows from their Lemma 2.17 by reasoning similar to the proof of
Theorem 2.3.3.
EXERCISES
Level 1
  1. Prove that in the additive group of integers any two elements are
     R-equivalent.
  2. Prove that R = L = J in a commutative semigroup.
  3. Let S be a semigroup with identity e with a partial order > such that if
     x> y then ax > ay. Show the elements a > e form a subsemigroup T.
  4. Let T be as in the above exercise. Prove that in T if x J y then x = y.
  5. Prove that if x R y then x D y and x J y.
  6. Show the subsets of a semigroup form a semigroup under the product AB.
  7. Prove that every element of a group is regular.
  8. What are the 5 relations in a rectangular band S X T with product
     (r, s)(t, u) = (r, u)l
Sec. 2.4]                           Blockmodels                                    55
Level 2
 1. Let the rank of a transformation on {1, 2,be the number of elements
    in its image set. Prove rank (fg) < rank (/) and rank (fg) < rank (g).
 2. Let A, B be subsets of {1, 2,...,«} having the same number of elements.
    Define a transformation / on {1,2, ..., n) such that f(A)=B.
 3. Prove that two L-equivalent transformations /, g on {1,2,..., n} must have
    the same image set.
 4. Prove two R-equivalent transformations on {1,2,...,«} have the same
    partition.
 5. Prove two J-equivalent transformations have the same rank.
 6. Show that the non-square matrix [1 1] has a generalized inverse.
 7. For transformation / on {1,2,            construct g as follows. For each
    a G Image (/) choose ca such that f(ca) = a. Let g(a) = ca for
    a G Image (/). For x £ Image (/) let g be any fixed element ca. Prove g is
    a generalized inverse of f. Therefore the semigroup of transformations is
    regular.
 8. What is the relation R in a lattice?
Level 3
 1. Prove that if a semigroup has no left ideals except S and no right ideals
    except S then it is a group.
 2. Prove that the relation x <y if and only if x = ayb for some a, b in S
    gives a quasi-order on S and gives a partial order on J-classes. Show this
    partial order is isomorphic to the set of two-sided principal ideals under
    inclusion.
 3. Construct an infinite semigroup for which J =£ D (use generators and
    relations).
 4. A rectangular band of groups uses of nonempty sets S, T a group G,
    elements gstE G for s G S, t G T (sandwich matrix). The product on
    S X G X T is given by (r, x, t) (s, y, u) = (r, xgsty, u). Prove this is
    associative. What are the 5 Green’s relations?
 5. Prove that two transformations with the same image set are L-equivalent.
 6. Prove two transformations with the same partition are R-equivalent.
 7. Prove two transformations of the same rank are D-equivalent.
2.4 BLOCKMODELS
Sociologists have studied groups of people in terms of various relationships that
exist on the group: friendship, respect, influence, frequent contact, dislike. Each
gives rise to a binary relation, as {(x, y): x is a friend of y}. Each binary relation
may then be represented by a Boolean matrix, whose (i,/)-entry is 1 if the
56                            Semigroups and Groups                           [Ch.2
relation exists between persons i and /, and whose (/, /)-entry is 0 if the relation
does not exist. This gives a set of Boolean matrices for analysis.
     One method of analysis is to try to find significant subsets of the group.
An early method of R. D. Luce and A. D. Perry was to try to find cliques.
subsets of at least 3 members, and as large as possible, in which every person has
the relation to every other. There are several hindrances: cliques are difficult
to find by computer, and are usually approximate and not exact. R. D. Luce
considered cliques in the square (or higher power) of a binary relation as a means
of dealing with the second. However, some power of most binary relations is the
Boolean matrix all of whose entries are 1.
     Methods of finding subgroups of a binary relation which are approximate
(in any sense) cliques are known as cluster analysis. There are many methods:
clusters can be built up from single individuals or the group may be repeatedly
split in two so as to maximize some clustering index. Generalized components of
a graph may be studied. Powers of a Boolean matrix may be taken.
     In the method of blockmodels of H. C. White, S. A. Boorman, and R. L.
Breiger, the individuals are to be grouped in blocks. Every individual in one
block is to have the relation to every individual in another block, or else no
individual in the former block is to have the relation to any individual in the
second block. In practice, a few exceptions must be allowed.
    This means we are searching for a congruence on the individuals with
respect to the given relations. To group the individuals, a method, CONCOR, of
R. L. Breiger, S. A. Boorman, and P. Arabie works well, although other clustering
methods can be used. CONCOR repeats a step of passing from a Boolean matrix
M to the Boolean matrix of correlations among rows of M, until this sequence
of Boolean matrices converges.
     To display a block pattern it is convenient to relabel the individuals so that
those in the same block are adjacent. The relationships Of the different blocks
can be represented by a smaller Boolean matrix whose rows and columns cor¬
respond to blocks of individuals, that is, row i represents block i. To obtain it,
consider each submatrix Ay of the original Boolean matrix A, partitioned by
blocks. Replance Ay by a single 0 entry if Ay is a zero matrix and replace it by a
single 1 matrix if Ay is not a zero matrix. This smaller Boolean matrix is called
the image.
EXAMPLE 2.4.1. Griffith, Maier, and Miller (1976) studied a set of biomedical
researchers. On of the relationships between researchers was that a pair of
researchers had mutual contact with one another. Griffith, Maier, and Miller
considered 107 men. White, Boorman, and Breiger investigated a random sample
of 28 of these men.
     When the group of men are suitably ordered, the matrix looks like this:
Sec. 2.4]                                 Blockmodels                      57
Mutual Contact
             9     XXXX               X            X
            26   X   XX XX            X      XX            XX
            23   X                    X
             4   XX                   X                X
             1   XX                   X            X
            12  X     XX                      X             X
             7  X    X X                     XX
             6       XX                       XX
             2 xxxxx                               XX
            24
            19
            14   X             X
            28   X            XXX
            11                   X
            10 X          X           X
            18        X               X
            22   X
            15   X            X
            16
            20
            17
             5
             8
            13
            21
            27
            25
             3
    When the zero submatrices are replaced by 0 and the nonzero submatrices
by l,we obtain the following image:
                 1110
                 1110
                 110              0
             0    0       0       0
     A hypothesis about the image matrix and a partitioning of the group which
will produce this image is called a blockmodel. G.H. Heil developed a computer
algorithm, which for any given blockmodel, finds all partitions of the set of
people which yield the blockmodel as image.
58                                 Semigroups and Groups                   [Ch. 2
EXERCISES
Level 1
 1. Describe the blocks and give the image for these Boolean matrices.
               1   1   0       0
               1   1   0       0
     (a)
           0       0       1   1
0 0 1 1
1 1 0
     (b)       1   1   0
            1      1    1
1 1 0 1
            1      1   0       1
     (c)
            1      1    1      0
0 0 0 1
1 0 1
(a) 0 0 0
           1       0   1
Sec. 2.4]                        Blockmodels                                59
1 0 1 0
            0    1     0   1
    (b)
            1    0     1   0
0 1 0 1
Level 2
 1. Explain the names of these blockmodels.
                                        1     0
    Deference:
                                        1     1
Hierarchy: 1 0
-1 0.
                                        1     f
    Center-periphery:
                                       J      o_
                                        1     0~
    Multiple caucus:
                                       .0     1.
Level 3
 1. Suppose we consider Boolean matrices with a fixed partitioning, and
    square diagonal blocks. Let im (^4) denote the image matrix. Prove
    im (v4 + B) = im (A) + im (B). The matrix addition is Boolean.
 2. Prove that if all nonzero blocks in A, B have at least one nonzero row,
    im (AB) = im (A) im (B). Here the matrix multiplication is Boolean.
 3. Find all 2 X 2 Boolean matrices which equal their own correlation matrices.
 4. Suppose a Boolean matrix is partitioned into 4 submatrices An, A12, A21,
    A22 and each Ay is a scalar multiple of the Boolean matrix having all
    entries 1. Suppose A equals its own correlation matrix. What possibilities
    are there for A?
 5. Give an example of a binary relation on 5 elements such that a union of
    cliques contains a different clique.
 6. Suggest an idea for a clustering method.
60                                  Semigroups and Groups                       [Ch. 2
at bi c 8
                 0 0 0 0
                 0 0 11
                 0 10  1
                 0 110
                 10  0 1
                 10  10
                 110   0
                 1111
Sec. 2.5]                     Finite State Machines                            61
     These are some questions considered in the theory of automata (of which
finite machines are the simplest kind):
 1. What is the machine having the fewest number of states which can
    accomplish a given task?
 2. How can machines efficiently compute products in semigroups?
 3. How can machines be decomposed into simpler machines?
 4. What machine languages can machines recognize?
     The theory of automata more generally includes not only finite state
machines but various types of machines with infinite memory: push-down
automata and Turing machines. The latter can perform any calculation which can
be done completely systematically. To show that a task cannot be performed by
a Turing machine is considered equivalent to showing that no algorithm exists
for it. This has been shown for a number of purely mathematical problems,
for instance solving Diophantine equations (equations where the solutions are
required to be whole numbers) in n variables.
     We conclude this section by a result showing that no finite state machine
can multiply two numbers of arbitrary length. This is contrary to the case for
addition, where Example 2.5.1 constructs such a machine.
Proof. Suppose M is a machine which can perform this task, having n states.
Suppose we multiply the two numbers a = 2n+1, b = 2n+1. Let the initial state
be s0. The first n + 1 inputs are (0, 0). The next input is (1,1). Let Sj be the
state after this input. The next n + 1 inputs are (0, 0). The state after i of these
is (si)/(o,o)!. i ~ 0 to n. But some two of the states (si)/(0>o)Z must be equal,
since they lie in a set of n elements. Say (si)/(o,o/ = (si)/(o,o/ where i < j.
Then (si)/(o,o)”+1-^/-^ = (si)/(o,o)”+1, since the inputs and states are equal,
the outputs at these times must be equal. But the output from the latter is the
unique 1 digit of the answer, and the output from the former is 0. This proves
the theorem.                                                                  □
EXERCISES
In these exercises S is the set of states, X the set of inputs, Z the set of outputs,
v(s, x) is the next state from state s and input x and 5(s, x) is the output from
state s and input x. For brevity v and 5 are written for v(s, x) and 5(s, x).
Sec. 2.6]   Recognition of Machine Languages by Finite State Machines            63
Level 1
 1. Consider a machine that will count to 100 (and then go back to 0). The
    output and the internal state are the number counted. How many internal
    states are needed?
 2. The inputs will be either 0 or 1 as something is to be counted or not. Write
    S, X, Z.
 3. The next state will be the same as the last if no input is received else it
    will be greater (orIf the last is 100 the next is 0). Write the function v(s, x)
    describing the next state.
 4. Write the function 6 giving the output.
 5. Suppose the output were only to signify whether 100 is reached or not and
    after 100 is reached the state remains there. Write a machine for this.
 6. Write a machine to test whether all digits of a binary number are zero.
Level 2
 1. Consider a machine that will add three numbers in base 10, digit by digit.
    What possible internal states (carries) must be allowed for? Write S, X, Z.
 2. Write v, 5 for a machine that adds two numbers in base 10.
 3. Write a machine that adds three numbers in base 2.
 4. Write a machine that multiplies any number in base 10 by 3.
 5. Write a machine that divides any number in base 10 by 2. The digits must be
    put in left-to-right in contrast with previous examples.
 6. Write a machine given two binary numbers a, b digit by digit to test whether
    a = b.
 7. Write a machine given two numbers a, b in base 10 to decide whether a — b,
    a < b or a > b.
Level 3
 1. For any monoid S, any set X, and any mapping h : X -*■ S construct a
    machine with semigroup S such that h is the mapping h(x) = fx.
 2. Write a machine that divides any number in base 10 by 11.
 3. Can a finite state machine take the square of a number of arbitrary length
    input digit by digit right-to-left?
 4. What tasks could be accomplished by a machine which has no memory, i.e.
    only one internal state? which remembers only the last input?
 5. Show that some finite state machine can handle any task involving only a
    bounded number of inputs.
EXAMPLE 2.6.1. If X is {a, b}, X* is {e, a, b, aa, ab, ba, bb, aaa,...}.
     1.   o
     2.   Variable =   Expression
     3.   Variable =   Expression   +   Expression
     4.   Variable =   Expression   +   Expression + Expression
     5.   Variable =   Expression   +   Expression + w
     6.   Variable =   Expression   +   z +w
     7.   Variable =   y + z +w
     8.   x = y + z    +w
DEFINITION 2.6.5. A grammar is context-free if and only if for all (a, b)E P
we have a E N, and b =£ e.
EXAMPLE 2.6.5. If x and y (but not x_y) were members of N and (xy, z)E P
then the grammar would not be context-free.
DEFINITION 2.6.6. A grammar is regular if and only if for all (a, b)E P we
have a E N, b = tN where t ET and n E N or n = e.
     Being regular means that the productions are filled in with terminals one per
step, going left to right and that at each stage there is a string of terminals
followed by a single nonterminal.
EXAMPLE 2.6.6. Let P = {(a, w), (w, xw), (w, yw), (w, jc)} and T — {x, y}.
Then L(G) is all sequences in x, y ending in x. This is a regular grammar.
DEFINITION 2.6.7. A machine accepts L(G) if and only if the machine can
tell whether or not any given sequence of inputs is in L(G}.
EXAMPLE 2.6.7. The following machine accepts the last language. The internal
states are {0,1}. Outputs are {Yes, No} (meaning all symbols so far do or do not
constitute a valid expression).
v(s, x) 8(s, x)
                s      x                          s       x
               0x0                                 1      x       Yes
               0       y        0               other             No
               0     other      0
                lxl
                i      y        1
                1    other      0
Proof Let L(G) be accepted by a finite state machine. Outputs will be ‘Yes,
No’ as in Example 2.6.7, meaning ‘all symbols so far are a valid expression’ or
‘all symbols so far are not a valid expression’. The set T will be as in L(G) but
we will construct a new grammar based on the machine.
      Let the set of nonterminals be o together with the rest of internal states of
the machine. Let the set of productions be the set of pairs (nlt xn2) such that
if the machine is in state «x and x is input then state n2 results, together with
the set of (nh x) such that in state nx if x is the next input the machine declares
the sentence to be valid.
      Let xxx2...xfc be an expression the machine recognizes as valid by a
succession of internal states nx, n2,..., nk before these inputs. Then we have
a derivation xx x2 ... xrnr -*■ xxx2 ... xr+l nr+i in the language.
      Conversely if xxx2 ... x„ is derivable in the language and the sequence at
time r is xxx2... xrnr then nr will be the state of the machine at time r for
these inputs and the machine will recognize the sentence when the last input
xk is put in. This proves that if L(G) is acceptable it arises from a regular
grammar.
      Conversely let L(G) arise from a regular grammar. Let outputs for a
machine be ‘Yes, No’ as above, and inputs be symbols of T. Let internal states
be in 1-1 correspondence with all sets of nonterminals. Let the initial state be 0.
If the state at time r is a set U of nonterminals let the state at time r + 1 be the
set of all nonterminals z such that (u, xz) £ P for some u £ U. Let the output
be ‘Yes’ if and only if for some u £ U, (u, x) £ P. Then if we have any derivation
xxx2 ... xrnr -*■ xx... xr xr+1nr+1 then nr will belong to U at time r and when
xk is put in the machine will print out ‘Yes’. Conversely if the machine prints
‘Yes’ then there must have been a sequence of elements of the sets U making up
a valid derivation.                                                                □
EXERCISES
In these exercises N is the set of nonterminals, T the set of terminals, P the set
t)f productions, o the starting symbols, L(G) the language generated by grammar
G, 5(s, x) the output from state s and input x and v(s, x) the next state from
state s and input x.
Level 1
 1. In the grammar T = {+, 1}, N — {a}, P = (a, 1), (a, a + a)} derive the
    expression 1 + 1 + 1.
 2. What are the elements of L(G)1
Sec. 2.7]                            Groups                                    67
Level 2
 1. What is L(G) for this grammar {(a, 1), (a, 1 + a)} where N, T are as in
    Exercise 1 of Level 1.
 2. Is the above grammar regular?
 3. Do you think a regular grammar exists for L(G) as in Exercise 5 of Level 1?
 4. Find a regular grammar which generates L(G) = {all sequences in x of
    length (am + Z?)} where a, b are fixed. Here T = {x}, and it is only necessary
    to find P, N.
 5. Give a grammar to obtain a union L(Gj) U L(G2).
 6. Let S be any finite subset of T* for fixed T. Does there exist a regular
    grammar yielding S as L(G)?
Level 3
 1. Two machines (S, X, Z, v, 6), (T, X, Z, p, co) have the same behavior if
    there exists a binary relation R from S to T such that R and RT are onto
    and if (s, t)€E R and the machines are initially in states s, t, then for any
    sequence of inputs the machines give the same sequence of outputs. Show
    this is an equivalence relation.
 2. Two states sh s2 of machine (S, X, Z, v, 5) are equivalent if and only
    if for any sequence x1x2...x„ of inputs 8((si)fXlfX2... fXn_v xn) =
    5((s2)fx1fx2--- fxn_v xn)• Show this is an equivalence relation.
 3. For any machine M show there exists a machine M having the same
    behavior whose states are equivalence classes of states of M.
 4. Show that if M and N have the same behavior there exists a homomorphism
    of machines from M to N which is 1-1 on states of M. Here a homo¬
    morphism of machines from (5, X, Z, v, 5) to (T, X, Z, n, w) is a function
    /: S -+T such that for all s G S, x E S, 5(s, x) = tx) and f(v(s, x)) =
    M(/0), x).                                                            _
 5. Tell why the preceding exercises show that for any machine M, M is a
    machine having the same behavior with the least number of states.
2.7 GROUPS
A group is a semigroup in which multiplication by any element is a 1-to-l onto
function.
     (1) (x o y) o z = x o (y o z)
     (2) there exists e G G such that for allxGC,roe = eor = r, where e
         is called an identity element
     (3) for all x G G there exists x_1 G G such that x o x_1 = x-1 o x = e,
         where x_1 is called the inverse of x.
    The presence of inverses x_1 makes group theory very different from
semigroup theory. Every multiplication is reversible and cancellation holds.
EXAMPLE 2.7.1. Under addition, the following are groups: the integers Z, the
    Positive integers, rationals, or reals do not form a group, lacking the identity
0 and the negative elements which are inverses.
EXAMPLE 2.7.2. Under multiplication these are groups: rationals r/s such
that r, s have among their divisors a fixed set S of primes, nonzero rational
numbers, nonzero real numbers, nonzero complex numbers, complex numbers
of absolute value 1, nonsingular nX n matrices over C.
    For groups there is a result similar to the result about semigroups being
isomorphic to semigroups of transformations.
DEFINITION 2.7.3. The group Syi of permutations on the set {1, 2,..., n} is
called the symmetric group of degree n (or symmetric group on n letters).
EXAMPLE 2.7.4. The symmetric group on {1, 2} has two elements e, x where
x(l) = 2, x(2) = 1 and multiplication e2 = e, ex = xe = x, x2 = e.
EXAMPLE 2.7.5. The element 1 generates the integers as a group (but in the
semigroup sense it would generate only the positive integers).
    An equivalent statement is that no group which is a proper subset of G
contains C.
EXAMPLE 2.7.6. The additive integers are a subgroup of the additive rationals
which are a subgroup of the additive real numbers which are a subgroup of the
additive complex numbers.
EXAMPLE 2.7.7. The free group on generators x,y has these words of length
at most 2: e,x,y,xy~\ x2, y2, x~2, y ~2, xy, x~ly   xy _1, x~ly, yx,y _1x
yx~\ y~lx. The product of x2yx~x and xy"2 is x2yx~1xy~2 = x2yy~2 = x2y~1
after cancelling x_1x and yy-1.
    The simplest nontrivial groups are those having one generator. For instance,
they are always commutative.
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
EXAMPLE 2.7.10. Any 1-element group has this structure: {e} where e * e = e.
We will call this Zx-
EXERCISES
Level 1
 1. Prove that any group of order 2 is isomorphic to Z2.
 2. Prove that these cancellation properties hold in groups: if xy — xz then
    y — z, if yx = zx then y = z (multiply by the x~l on left or right).
 3. Write out the addition table of Z4.
 4. Write out the addition table of Z2 X Z2.
 5. Prove Z4 is not isomorphic to Z2 X Z2.
 6. Prove the symmetric group on (1, 2, 3} is not commutative. Let /
    interchange 1, 2 and g interchange 2, 3. Prove (/ o g)0)*(g o /)(i).
 7. Prove the identity element of a group is unique.
 8. Prove inverses are unique.
Level 2
 1. Write out the multiplication tables of Z2, Z3, Z2 X Z3.
 2. Show Z2 X Z3 is cyclic. Show Z2 X Z3 is isomorphic to Z6.
 3. Can you suggest a generalization of the above exercise about products of
    certain cyclic groups being cyclic?
 4. Find all subgroups of Z6 (they are cyclic).
 5. Prove the inverse of xy is y~lx~x. Describe the inverse any word xxx2 .... xn
    in a free group.
 6. Let f(vlt..., vn) be any function from n-tuples of vectors to the real
    numbers. Prove the set of invertible matrices A such that f(v i, v2,..., vn) =
    f(Avlt Av2, ..., Avn) is a group. For instance the set of all matrices A such
    that \v\2 = \Av\2 is a group called the orthogonal group. Its members
    preserve distances \x — y\2 and are made up of totations and reflections in
    n-dimensional space.
Level 3
 1. Consider the group of transformations of a square into itself including all
    rotations by multiples of 90° and all reflections through a line inclined at a
    multiple of 45° through the origin. Write out its multiplication table. This
    is the dihedral group of order 8.
 2. Show there exists an onto homomorphism /: Zm-*Zn if and only if n
    divides m. Show the set of x such that f(x) = e is a subgroup.
 3. Show that if n divides m, Zm has a subgroup of order n.
 4. Prove that any finite group is isomorphic to a group of matrices. Use
    Proposal 2.4.1 and prove that the symmetric group on {1,2,...,«} is
    isomorphic to a set of (0,1)-matrices with exactly one 1 in each row and
    column.
 5. Suppose there exist homomorphisms     : G -*■ Gi and f2 : G -+
    Construct a homomorphism /: G -* Gx X G2. Use this to prove Znm is
72                          Semigroups and Groups                           [Ch. 2
2.8 SUBGROUPS
It has already been mentioned that a subgroup of a group is a nonempty subset
closed under multiplication and inversion.
EXAMPLE 2.8.1. A set of positive rational numbers {*!, x2,..., x*.} generates
the multiplicative subgroup of rational numbers of the form x”1 x”2 ... x”k.
    For any subgroup H we can divide a group into equivalence classes called
cosets. The cosets are sets which are ‘parallel’ to the subgroup in the sense
y = x + 1 is parallel to y = x. All the lines y = x + c partition the plane.
    As before, AB means the set of all products {ab: a G A, b G B}. We have
(AB)C = A(BC)= {abc: a G A, b G B, c G C}.
Proof. The left cosets of G are the equivalence classes of the equivalence
relations {(x, y): x = yh for some h E H}. The first assertion follows from this.
The mapping H -*■ xH which sends h to xh is 1-to-l and onto. This implies the
second statement. The first two statements imply \G\ is \H\ times the number
of cosets. If H is normal then xHyH = x{yH)H = xyHH. But HH = H since
H is a subgroup. So the operation is well defined. The proof of associativity is
(xHyH)zH = (xyH)zH = (xy)zH = x(yz)H = xHyzH = xH(yHzH). And
x~lH = (xH)~1 and eH = H is an identity element. This proves the last
statement.                                                         □
e a b X y z
e e a b X y z
a a b e y z X
b b e a z X y
X X z y e b a
y y X z a e b
z z y X b a e
The set H = {e, a, b] is a subgroup. There are two different left cosets of H,
eH = {e, a, b} and xH = {xe, xa, xb} = {x, y, z}. All other cosets equal one
of these two. These two cosets form a partition of G. The subgroup H is normal.
As can be seen from the distribution of symbols e, a, b, x, y, z in the table,
multiplication of cosets is described by
eH xH
eH eH xH
            xH          xH       eH
74                           Semigroups and Groups                           [Ch. 2
     For a normal subgroup TV, the order of G is given by |TV| |G/TV| since there
are |G/TV| cosets. Many other properties of G can be studied in terms of the
simpler groups TV, G/N if a proper nontrivial normal subgroup exists. In fact all
groups G such that G/N = H can be classified by means of extension theory.
One such group is the direct product N X G/N.
     Groups having no normal subgroups can be studied in terms of other types
of subgroups. If pm is the highest power of a prime p such that pm divides \G\
for m > 1, a subgroup of G of order pm is called a Sylowp subgroup. For any
p dividing |G| there exists a Sylow p subgroup of G and any two Sylow p
subgroups for the same p are isomorphic, in fact for such subgroups Hx, H2
there exists xE G with xHiX~l = H2.
     Groups of order pm for prime p have a special structure. For instance, there
always exists a nontrivial center.
EXAMPLE 2.8.6. The center of a symmetric group of order > 2 is the identity
element only.
Thus the center is the set of elements commuting with every element of G.
     It is reported as of 1982 that all finite simple groups have been classified
(the proof being some five thousand pages of research done by many group
theorists). These include finite analogues of the groups in the last example, other
matrix groups, subgroups of the symmetric group called alternating groups
defined later, and certain other groups.
Sec. 2.8]                           Subgroups                                   75
EXERCISES
Level 1
 1. Prove the center of a group is closed under products and inverses (so is a
    semigroup).
 2. Prove the center is a normal subgroup.
 3. Find three subgroups of order 2 of the symmetric group of degree 3 from the
    multiplication table given in Example 2.5.3 (these will be {{e, g]: g2 = e}).
 4. Show none of the subgroups in the last exercise is normal.
 5. Find all cosets of the subgroup {e, x} in the symmetric group of degree 3.
    (How many will there be, by Theorem 2.5.1?)
 6. Find two elements of the symmetric group of order 3 which generate the
    entire group. (Many pairs will do.)
 7. What are some Sylow 2 and 3 subgroups of the symmetric group of degree 3?
Level 2
 1. Prove that a group G of prime order p has no subgroup H except G, {e}
    from the fact that \H\ divides |G|.
 2. Prove that if x ± e in a group G of order p then the cyclic subgroup
    generated by x is all of G.
 3. Using the last two exercises and a theorem in the last section prove a group
    of prime order p is isomorphic to Zp.
 4. Prove that in a direct product G X H the sets {(e, g) : g G G] and {(e, h):
    h& H} are normal subgroups.
 5. Prove that if H is a subgroup of G and \G | / \H\ = 2 then H is normal. For
    x £ H show xH = G — H and Hx = G — H. For x E H, xH = Hx = H.
 6. Prove that if H, K are subgroups so is H Pi K.
 7. What are the quotient groups for the normal subgroups in Exercise 4?
Level 3
 1. What are all subgroups of Zp X Zp (note that except for G, {e} they have
    order p and by Exercise 3 above are cyclic)?
 2. Prove for subgroups H, K the set HK is a subgroup if and only if HK = KH.
 3. Prove that if H is a subgroup and N is a normal subgroup HN = NH.
 4. The quaternion group of order 8 has elements ±1, ±i, ±j, ±k with multi¬
    plication if = k, ji = —k, kj = —i, ki — j, ik — —signs treated as usual
    in algebra, and 1 the identity. Write out the multiplication table and find the
    center and all subgroups. They must have orders 1, 2, 4, 8. Orders 1, 8 are
    {e}, G. The order 2 subgroups are cyclic since 2 is prime. The order 4
    subgroups are normal by Exercise 5 above.
 5. Do the same for the dihedral group of order 8 which is the group of rota¬
    tions and reflections of a square. It can also be represented by generators
    x (90° rotation) and y (reflection) with x4 = e, y2 = e, yx = x3y. The
76                          Semigroups and Groups                         [Ch.2
    elements are e, x, x2, x3, y, xy, x2y, x3y and products follow directly from
    these relations. Show that there exists a noncyclic subgroup of order 4
    so that the dihedral and quaternion groups are not isomorphic. What is the
    quotient of this group by its center?
 6. For any prime p there exists a nonabelian group of order p3 with generators
    x, y, z and defining relations xp = 1, yp = 1, zp = 1, xy = yxz, zx = xz,
    zy = yz. All elements have the form xnymzr and products are given by
    xnymzrxaybzc = xa+nyb+mzr+b+am. Find the center. Show every
    subgroup containing the center is normal. Find some normal subgroups of
    order p2. What is the quotient of this group by its center?
2.9 HOMOMORPHISMS
A homomorphism of groups is a function preserving products.
     As was earlier remarked homomorphisms that are not 1-to-l can simplify
the structure of a group. One-to-one homomorphisms can represent a group in
terms of some other structure: a group can be regarded as a group of matrices
or permutations.
EXAMPLE 2.9.5. For any commutative group and integer n the mapping
x  xn is a homomorphism of the group into itself since (xy)” = x”y” holds.
Proof We have f(e)f(e) — f(ee) = fie) = ef(e). Multiply by/_1(e) on the right,
we have /(e) = e. We have /(x)/(x_1) =/(xx_1) = /(e) = e = /(x)/-1(-*)-
Apply /_1(x) on the left. This completes the proof.                         □
    Two of the most important aspects of homomorphisms are the kernel and
image.
PROPOSITION 2.9.2. The image is always a subgroup and the kernel is always
a normal subgroup.
EXAMPLE 2.9.8. The function |x| is a homomorphism from the nonzero real
numbers under multiplication to the positive real numbers under multiplication.
The kernel is ±1. This gives an isomorphism from R\{0}/{x: |x| = 1} onto R+
where R+ denotes the positive real numbers.
EXERCISES
Level 1
 1. What is the image of the determinant map on nonsingular matrices? Give
    examples of elements of its kernel.
 2. Consider the homomorphism G X H -*■ H such that /(g. h) is h. What are
    its kernel and image?
 3. The map in the above exercise gives an isomorphism between (G XH)/(G X e)
    and what group, by the theorem? How does this partly justify the reason
    for the name “quotient group’? (The order of the quotient group is another
    reason, as well as the division into cosets.)
 5. Find a monomorphism from Zm into the multiplicative group of complex
    numbers C (consider mth roots of unity).
Level 2
 1. Prove any group homomorphism is the composition of an epimorphism and
    a monomorphism, using the theorem.
 2. Show any group homomorphism f:G~*H is the composition of a mono-
    morphism and an epimorphism. Take as monomorphism fx: G -*■ G X H
    where fx(g) = (g, /(g)).
 3. For any complex number x. define a multiplicative homomorphism /from
    the real numbers under addition into the complex numbers under addition,
    such that f(l) = x.
 4. Let / from nonzero rationals under multiplication to the additive integers
    be defined as the power of 2 occurring in the rational number. Give the
    miage and kernel of /.
 5. Prove the intersection of two normal subgroups is normal.
 6. Let /i: G -+Hx and f2: G~*H2 be homomorphisms with kernels Nx, N2.
    Let /(x) = (/i(x),/2(x)) E Hx X H2. Show / is a homomorphism. What is
    its kernel?
Sec. 1.10]                       Permutation Groups                            79
Level 3
                 1       2 ...   n
              \/(l)/(2) .../(„)/
That is, the top row is always 1, 2, ... n. Underneath each number x is the value
 fix).
              1    2    3     4\/l       2
              2    3    4     1/   \4    3
              12        3     4
              3    2     14
DEFINITION 2.10.1. For distinct x,-, (xxx2 ••• xk) is the permutation f such
that f(x0 = x2, f(x2) = x3, in general /(*,) = xi+1, and f(xk) = xv For
x ^ {^x, x2,..., xfc), /(x) = x. Such a permutation is called a cycle or k-cycle.
              1    2     3
              2    3     1
    Two cycles are disjoint if and only if the sets {x1( x2.x*.} are disjoint.
The notation (x) represents the identity permutation and is sometimes called
a 1-cycle.
     Cycle notation is more compact and tells more about the permutation than
the double-row notation. But multiplication of cycles is less simple.
Proof Let p be a permutation on (1,2,..., n). Consider the relation {(x, y):
x ~ (y)pl for some integer /}. This is an equivalence relation since x = (x)p°
and if x = {y)pl then (x)p~l = y and if x = (y)pl and y = (.z)p> then
Zpi+l = ypl -    jo each equivalence class we will associate a cycle of p.
Namely for an integer x, let n be the least positive integer such that (x)pn = x.
Sec. 2.10]                      Permutation Groups                              81
Then for 0 < s < t < n, if (x)ps = (x)pf then (x) = (x)psp~s = (x)ptp~s =
(x)pt~s. This contradicts the assumption on n. So x, (x)p, (x)p2,..., (x)p”_1
are distinct. We have a cycle (x (x)p (x)p2 ... (x)p"_1). The product of all such
cycles is p. This proves the first assertion.
     Let /, g be two disjoint cycles. Then for all x either (x)/ = x or (x)g- = x.
Moreover if x =A(x)/ then (x)/ ^ (x)/2. Suppose x =£ (x)/ Then {x)g = x and
(O)f)g = (x)f So (x)gf = (x)f and (x)fg = (x)f. Likewise if xi=(x)g,
Cx)gf = (x)fg. Suppose x = (x)/ and x = (x)g. Thus (x)gf = x = (x)fg. This
proves the last statement.                                                      □
EXAMPLE 2.10.4. If
             123456789
             457923618
This is (1243).
is 3.
    The order of an element is the same as the order of the cyclic subgroup it
generates, since that subgroup is {e, x, x2,..., x”-1}. Thus the order of any
element of a group divides the order of the group, since the order of a subgroup
divides the order of a group.
Proof. If / is a fc-cycle, it can be seen that xfk — x and that if x is in the cycle,
k is the lowest power with this property. So the order of / is k.
     Let / be a product Z\Z2...zr of disjoint cycles. Then since the cycles
commute, fm = z™z™... z™. This will be the identity if and only if z™ = e,
z™ = e,..., z™ = e, that is, if m is divisible by the order of each cycle. The last
statement of the proposition follows from this.                                    □
EXAMPLE 2.10.7. The order of (1467) (2398510) is the least common multiple
of 4, 6, that is, 12.
Proof Under pzp~l the element p_1(x,-) is sent to xt then to x,-+1 then to
p_1(x,-+1). So yt -> y,-+1. Also y^-* y2. And elements v not of the form p_1(xf)
have v -*■ p(v) -*■ p(v) -*■ v.                                               □
   For products of cycles pzp~l can be computed in the same way since
pxp~lpyp~x = pxyp~l. Here p'1 was defined after Proposition 1.3.3.
EXERCISES
Level 1
 1. Multiply
            (1        2   3   4\/l       2    3     4
            \2        3   4   1/ \3      1    4     2
            /I        2   3   4    5\
            \2        3   1   5    4/
 3. Write
            (1        2   3   4    5\
            \2        3   1   5    4/
     in cycle form.
 4. Write the multiplication of the set of permutations e, (12) (34), (13) (24),
    (14) (23). Show it fonns a commutative subgroup. It is called the Klein
    4-group.
 5. What is (12) (23)? (12) (23) (34)?
Sec. 2.11]   Systems of Distinct Representatives and Flows on Networks          83
Level 2
 1. Find a permutation of degree 7 but of order 10. (It will have a 5-cycle and
    a 2-cycle.) What is the largest order for degree 8?
 2. What is the product (xy) (yz)? Here x, y, z are distinct.
 3. What is the general product (*iX2) (*2 *3) ••• (xk_txk)l Here all xt are
    distinct. Tell why this implies that 2-cycles, called transpositions, generate
    the symmetric group.
 4. Can a power of a cycle have more than one cycle? When? Consider (1234)
    and (12345).
 5. Tell how to obtain the inverse of a permutation written in cycle form.
Level 3
 1. Find (12 ... n) (23) (12 ... n)~l. Note (12 ... n)”1 = (n ... 21). Note
    for x =£ 1, 2, n\ x-*x + l-+x+l-*x, 1 -*■ 2 -*■ 3 -> 2, 2 -> 3 -»■ 2 -> 1,
    n -»■ 1 -*■ 1 ->•«.
 2. Find (12 ... n) (i + 1 / + 2) (12 ... «)_1 for i = 1, 2, ..., n — 2.
 3. Generalize the formula (54) (43) (32) (12) (23) (34) (45) = (15). Thus
    show all transpositions are products of (/ / 4-1).
 4. Combine the answers to 2, 3 of Level 3 and 3 of Level 2 to find two
    permutations x, y which generate the entire symmetric group.
 5. Show that all transformations are generated by the two permutations
    in the above exercise together with the transformation f(x) = x, x =£ 1,
    /(1) = 2. First obtain all transformations with image size n— 1 as pfq
    for permutations p, q. Then show any transformation with image size
    k, k < n — 1 can be factored as a product of transformations with image
    size k + 1.
             12              3       4
             2   3           14
is
             0       10                  0
             0       0           10
             10                  0       0
            _0       0           0       1_
Proof. A permutation matrix has a 1 on place (i)ir in row i and place (/)7r_1 in
column /. Conversely if A has exactly one 1 in each row and column, define n by
ai(i)n ~ 1- Then n must be a 1-to-l else some column would have two ones. So it
is a permutation.                                                             □
                         0           1       1
            A            1           0       0
                         1           0       0
    Hall matrices will here be considered usually as Boolean matrices, since they
form a semigroup under Boolean matrix multiplication. Treatment as a Boolean
Sec. 2.11]   Systems of Distinct Representatives and Flows on Networks        85
matrix makes no difference except that the operations are Boolean, but for
a (0,1)-matrix they are the usual arithmetic operations in the real number field.
     For a system of distinct representatives we form a matrix A. Let \U\ = m
and label the elements of U as U\, u2,, um. Form an n X m matrix A by
aij = 0 if Uj (f. Ui and ay — 1 if Uj E U(. Thus the zth row of A has ones for
precisely those places corresponding to the members of
                  1    0     f
              0   0     11
              10        10
              1   o    o     i_
             'o   1    0
              1   1    1
             0    1    0_
             "l    0       1   l"
              0    111
              10           11
              1    1       1   0_
and either (1) there exists an edge from a point u E Sk_i to x which is not
flowing at full capacity c(e) or (2) there exists an edge from x to a point
u E Sk_! having positive flow. Continue as long as possible. If z belongs to some
Sk then we can increase the flow by one unit. Trace a path x0, xh x2,..., z,
where x( E S(. This can be done going backwards. For each edge of type (1) in
the path increase the flow by one. For each edge of type (2) reduce the flow by
one. This in effect adds 1 unit of flow along the path from x0 to z so it increases
the flow by 1.
EXAMPLE 2.11.9. For the preceding network start with a flow of zero. Now
form sets 51 = {a, b}, S2 = {z}. Thus we can increase the flow by 1. One path
from x0 to z is x0 -*■ b -* z. So increase the flow along this path.
                                         a
                                         n
:o z
                                         o
                                         b
Now repeat. This time Sy = {a}, S2 = {b, z). So increase the flow by 1 along the
path x0 to a to z.
                                         a
                                         o
:o z
                                        o
                                         b
88                            Semigroups and Groups                             [Ch. 2
Repeat once more Sx = {a}, S2 = {b}, S3 = {z}. Increase the flow by 1 along this
path
                                          a
     Finally again increase the flow by 1 along the same path. This gives the flow
of the previous example.
                                          a
This is maximal since all edges from {jc0, a} to {b, z} are at full capacity.
                                           a
Sec. 2.11]   Systems of Distinct Representatives and Flows on Networks           89
existed and it is desired to increase this flow by 1. Then form St = {a}, S2 = {b},
S3 = {z}. This is an example where an edge of type (2) is used. Increase the flow
by 1 unit from x0 to a, reduce it by 1 from a to b, increase it by 1 from b to z.
Proof. The value of the flow cannot exceed the total capacity of edges from U
to U since, intuitively speaking all material flowing from x to z must go through
one of these edges. In fact it can be shown that the value of the flow equals the
amount flowing from U to U.
     Suppose the flow is maximal. Then in the algorithm the sets Sk do not
include z. Let U = U 5). Then x0GU, z^lU. Moreover there exists no edge
from U to U not at full capacity and no positive flow from U to U or there
would be an additional set Sk. So the total capacity from U to U equals the
amount actually flowing which is v.                                            □
90                           Semigroups and Groups                           [Ch.2
              1111
              110            0
              110            0
              110            0
EXERCISES
Level 1
 1. Find an SDR for Ux = (1,3}, U2 = {2, 3), U3 = {2, 4), U4 = {1,4}.
 2. Find a permutation matrix P < A.
             0     10         f
             0     0    10
             0     111
              10        10
Sec. 2.11]    Systems of Distinct Representatives and Flows on Networks   91
             ~0    1   1    r
              10       0    1
              10       10
             _1   1    0    0
lllll"
              0   10        0    0
              0   0    10        0
              11110
             0    0    10        0
             _1   1    1    0    1_
 5. Find a maximal flow in this network.
Level 2
 1. Find all SDRs for this system {{1,2}, {2,3}, {3,4}, {4,5}, {1,5}}.
    Generalize to any n.
 2. Suppose a (0, 1)-matrix has at least k rows with at most k ones for each
    k < n. Show the system has at most one SDR.
 3. Find all permutation matrices P less than or equal to this matrix.
             "oiiif
              1   0    0    0    1
              10       0    10
              10       10        0
              110           0    0
92                           Semigroups and Groups                          [Ch. 2
     These are known to be the upper and lower bounds (the latter, the
     van der Waerden conjecture, was proved only recently).
Level 3
 1. Show a square matrix having exactly k ones in each row and column
    must be a Hall matrix (show that an R X S rectangle of zeros with
    |/?| 4- | S| = n + 1 would make this row and column sum condition false).
 2. A Boolean matrix is k-decomposable if and only if it has a rectangle of
    zeros with r + s = n — k + \. Else it is called k-indecomposable. Show a
    Boolean matrix A is k-indecomposable if and only if for every Boolean
    vector v =£ 0 either vA has no zeros or has at least k zeros fewer than v.
 3. Using Exercise 2 show the Boolean product of a k-indecomposable and a
    p-indecomposable matrix is at least (p + &)-indecomposable. Thus for
    k > 0 the set of k-indecomposable matrices forms a semigroup.
 4. Prove a Boolean matrix A is a Hall matrix if and only if MA has no more
    zeros than M, for any Boolean matrix M. Exercise 2 may be used row by
    row.
 5. Vertices jcj of a directed graph are said to lie in the same k-connected
    component if there exist flows of value k from x to y and from y to x.
    Here any ingoing edges to the source and any outgoing edges to the sink are
    disregarded. All edges have capacity one. Using the theorems of this section
    prove this is an equivalence relation.
THEOREM 2.12.1.
   (1) Cg(xy)=Cg(x)Cg(y).
   (2) CgCh(x) — Cgh(x).
   (3) Cg is an isomorphism G -*■ G.
   (4) Conjugacy is an equivalence relation.
THEOREM 2.12.2. Two permutations are in the same conjugacy class if and
only if for k = 1 to n they have the same number of k-cycles when expressed
as products of disjoint cycles.
     This means that the number of conjugacy classes of the symmetric group of
degree n equals the number of partitions of the integer n, that is the number
of distinct sets of positive integers whose sum is n.
94                           Semigroups and Groups                            [Ch. 2
3 = 13-1 + 1
3 + 2+1
3 = 3
EXAMPLE 2.12.5. The cyclic group generated by (12) (34) is not transitive,
since (l)g = 3 never holds.
EXAMPLE 2.12.6. The cyclic group generated by (1234) is transitive, but not
primitive, since it preserves the partition {{1,3}, {2, 4}}. That is the set {1,3} is
either mapped to itself or to {2,4), never to some set that overlaps both.
Sec. 2.12]                    Orbits and Conjugations                             95
     If a group is not transitive there will be more than one subset, called an
orbit,, restricted to which it is transitive.
     The idea is that under the group action any element stays within its own
orbit, eventually reaching all points of the orbit, but does not go outside that
orbit.
EXAMPLE 2.12.8. The group e, (12) (34) has two orbits {1,2} and {3,4}.
The isotropy subgroup of 1 is {e}. Under the action 1 -* 2 -> 1 and 3 -» 4 -*■ 3. The
number 1 will never be sent to 3.
The orbits of a cyclic group are the sets for the cycles of its generator.
EXAMPLE 2.12.9. The set of permutations e, (12) (34), (13) (24), (14) (23),
(1324), (1423), (12), (34) consists of all permutations which preserve the equi¬
valence relation with partition {{1,2}, (3, 4}}. It follows that it is a group. It is
transitive since 1 -»• 1, 1 —> 2, 1 -> 3, 1 -> 4 under different elements of the group,
but is not primitive. The isotropy group of 1 is e, (34). So |(7| = 8 = \H\ \Ox\ —
2X4.
    The formula \G\ — \H\ \Ox\ is used to prove many combinatorial results,
where some set related to a group must be enumerated. An example in group
theory itself is the size of conjugacy classes.
EXERCISES
Level 1
 1. Give representatives of all conjugacy classes in S4.
 2. For g = (12) describe Cg on any permutation written on cyclic form. Try
    (1345) and (243) as examples. Use the last result of Section 2.7.
 3. In S4 list the number of elements in each conjugacy class.
 4. What group is generated by x = (12) and y = (45) in the symmetric group
     of degree 5. What are its orbits? Find all distinct products xlyf
  5. What group is generated by x = (123) and y = (45) in the symmetric group
     of order 5. What are its orbits? Find all products xlyf Is this group cyclic?
Level 2
  1. Show a subgroup is normal if and only if it is a union of conjugacy classes.
  2. Prove a group of order pn for p prime has at least p conjugacy classes of
     one element. Note that the sizes of all conjugacy classes C;- are pm for
     m> 0 and that pn = 2 |C;-1. Thus
               pn   =     2       \q\ + P     2      ^
                        191 = 1             \Cj\ — pr
                                            r> 0
        Thus
                   2 I Cj |
               |C/I = 1
is a multiple of p, being
                                    icyi
Sec. 2.12]                   Orbits and Conjugations                           97
Level 3
 1. Show a group is simple (has no normal subgroups) if and only if any
    non-identity conjugacy class generates the entire group.
 2. Every permutation either preserves the sign of the product
             d = n (xi — xi)
                   i<i
    Under (12) this goes to (x2 — xx) (xx — x3)(x2 — x3) = —D. Prove any
    transposition reverses the sign of D.
 3. Prove there is a homomorphism h from the symmetric group onto {±1} by
    sending x to ±1 according as x preserves or reverses the sign of D. Here D is
    the same as in the above exercise.
 4. The kernel of n is a normal subgroup of the symmetric group called the
    alternating group Ay\. Prove every product of an even number of trans¬
    positions is in An but no product of an odd number of transpositions is.
 5. Prove that A5 is simple by showing each of its 3 non-identity conjugacy
    classes generates it. It is the smallest noncommutative simple group.
98                          Semigroups and Groups                          [Ch.2
2.13 SYMMETRIES
A symmetry of some object is a 1-to-l onto mapping from the object to
itself which preserves some of the structure of the object. One of the most
characteristic mathematical methods is to look for the symmetries in a problem.
EXAMPLE 2.13.5. Suppose we want to show that the edges of the figure
below (called a Petersen graph) cannot be 3-colored so that edges of all 3 colors
Sec. 2.13]                         Symmetries                                 99
meet at each vertex. We can reason as follows. Note that the entire figure has
a pentagonal symmetry. Any 3-coloration of a pentagon uses all 3 colors since
a pentagon cannot be 2-colored. There are symmetries of such a graph coloring
problem which permute the colors in any way. That is, if we have one coloring
we may obtain another by recoloring all 1 edges as 2, all 2 edges as 3, and all
3 edges as 1, for instance. In a pentagon not all 3 colors can appear on 2 edges.
So assume color 3 occurs only on 1 edge. No color may appear on 3 edges of a
pentagon because some two of the three will meet. So each of colors 1, 2 appear
on 2 edges. If we remove the edge colored 3 the other colors must alternate.
So we may say that any edge coloring on a pentagon, up to symmetry is
So we may suppose that the outer edges of the Petersen graph are colored in
this way. The edges between the outer and inner edges are determined by this.
We have
Evidently now no inside edges can be colored 3. But the inner 5 edges form a
pentagon. So one of them must be colored 3. This proves the impossibility of
3-coloring a Petersen graph. This problem is related to the 4-color problem, see
Gardner (1976).
100                          Semigroups and Groups                          [Ch.2
     The 4-color theorem asserts that any map in the plane can be colored with
4 colors in such a way that no two regions of the same color have an extended
common boundary larger than a point. This can be reduced to the case of maps
such that no more than three regions meet at a point, called trivalent maps.
A trivalent map can be 4-colored if and only if its edges can be 3-colored. The
Petersen graph (which, however, is not planar) is the smallest trivalent graph
which cannot be 3-colored and is ‘bridgeless’. Tutte has conjectured that every
bridgeless trivalent graph which cannot be 3-colored contains a topological copy
of the Petersen graph.
EXAMPLE 2.13.6. The set of n X n matrices has the symmetry X -*■ XT, the
transpose of X. This means that for any theorem about the columns of a matrix
there is a corresponding theorem about the rows of a matrix.
EXAMPLE 2.13.7. For any partial order there is another partial order
obtained by replacing < by >. This means for any theorem about > there is a
corresponding theorem about <.
x4 — ax2 + b — 0.
Roots occur in symmetrical pairs ±r. Now suppose a small nonsymmetric term
is added
             x4 — ax2 + 0.001 ax + b = 0.
Then the roots will still probably come in pairs which are almost but not quite
equal in absolute value. This is analogous to particles having nearly but not
quite the same mass, like the proton and neutron.
                      v•w
             cos 0 = -
                     \v\ |w|
EXAMPLE 2.13.9. For any (au a2,..., a„), the mapping (xlt x2,..., xn) -»■
    + flj, x2 + a2,..., xn + an) is an isometry called a translation. A translation
moves the plane a distance \Ja\ + a\ + ... + a„ in the direction of the vector
(ai, a2,..., an). It does not alter the directions of lines.
EXAMPLE 2.13.11. The reflection in the x, y plane sends (x, y, z) to (x, y, —z).
Proof. Let t be the translation which takes (0,0, ...,0) to /_1(0, 0,..., 0).
Then tf = g fixes (0, 0,..., 0).
     Later we will take up matrices in more detail, but for the present we will
state some facts without proof.
                                 a 12
                                        =   0
                     a 2i   z    a22
     Orthogonal 3X3 real matrices have the following forms. All eigenvalues of
an orthogonal matrix have absolute value 1, and satisfy a cubic equation with
real coefficients, "ftius either all three are real (and must be ±1) or two are
complex and one is real.
Eigenvalues Operation
  1,1,1         Identity
-1,1,1          Reflection in plane of last two eigenvectors
-1,-1,1         180° rotation about axis of last eigenvector
-1.-1.-1        —I, reflection through origin
  1, z, z       Rotation about axis of first eigenvector
—1,Z,z          Combined rotation about axis of first eigenvector and reflection
                in the plane of last two eigenvectors
EXAMPLE 2.13.14. The group of all symmetries of the line segment [—1, 1] is
the group consisting of the identity function and the function f(x) = —x.
Proof. Assume the polygon has its center at the origin, that the distance from
its center to a vertex is 1, and that a vertex vx is located at the point (1,0).
All isometries of En preserve convex combinations since both multiplication by
isometries and translations do. The center is the vector ^(vx + v2 + ... + vn) if
vn are the vertices, so the center is preserved. Thus all isometries are rotations
and reflections about the origin. Any rotation is determined by the position
of V\. Thus there are exactly n rotations, which send vx to vx, v2,, vn. Let z
be the rotation sending vx to v2. Then the others are z, z2,..., z"-1 and zn = e.
     The rotations are the isometries in the kernel of the homomorphism det (A)
to the group {±1}. Thus they form a normal subgroup K. Let y be the reflection
(x,.y)->(x, —y). Then y is a symmetry of the polygon. Any reflection would
satisfy the rule y2 = e. And yzy sends vx to vn. Its determinant is (—1) (1) (—1)
so it is a rotation. So yzy = z~l. By the properties of conjugation yz]y —
yz’y~l = z~K So yz1 — z~]y Finally we must observe that no other isometries
exist. The subgroup K has two cosets by Theorem 2.5.1 since the image under
det (A) is the subgroup {±1}. Each coset has n elements, so the group has order
precisely 2n. This completes the proof.                                         □
                          27-      2/
                    cos   —     sin —
                          n         n            “l   o'
            z1 =                         . y =
                      .   2/       27-           _0 -1_
                   — sin—       cos —
                        n           n
EXERCISES
Level 1
 1. What is a symmetry of the function sin x?
 2. The equation x4 + x3 + x2 + x + 1 = 0 can be written as x2 + x + 1 +
         -f x"2 = 0. Show that replacing x by x_1 is a symmetry of this.
 3. Use this symmetry to reduce x2 + x + 1 + x_1 + x-2 to a quadratic in
    z = x + x_1. Note that z2 + x2 + x-2 + 2. Write the function as a
    quadratic expression z2 + az + b. Find its roots in z.
 4. A nonsquare rectangle has a symmetry group consisting of e, one rotation
    and two reflections. Describe the rotation and reflections.
 5. Draw a 3-coloring of the edges of a cube. How many different 3-colorings
    exist? How many coincide under a symmetry of the cube or a permutation
    of the colors?
 6. Write out the multiplication table of the dihedral group of order 10, using
    the description in Theorem 2.13.2.
Sec. 2.13]                               Symmetries                                     105
Level 2
 1. Color the faces of a cube with as few colors as possible so that no two faces
    of the same color have an edge in common.
 2. Every finite partial order has a maximum element. What is the dual to this
    theorem?
 3. Write out the Kronecker product of this matrix with itself (which will be a
      4X4 matrix) (62i+fc-2,2/+m-2) = (0i/0fcm), where                      range over 1, 2.
      To find brs put in all values for i, j, k, m successively. If i   =   k = j = m = 1,
      ^2 + 1 —2,2 + 1 —2 = 011011 SO   bn = aji =   l2 = 1.
                      1     2
              A =
                      3     5
      Show the Kronecker product of its square is the square of its Kronecker
      product.
 4.   Prove the Kronecker product El is multiplicative in that (A El B) (C El D) =
      (AB E CD),where (A E B)ni+k_n>ni+m_n = aijbkm, B is n X n.
 5.   Prove that any two translations commute. Show the group of translations in
       En is isomorphic to R X R X ... X R where R is the additive real numbers.
 6.   Show that the group of translations and rotations in the plane is isomorphic
      to the group of transformations az + b on complex numbers, where a, b
      are complex numbers and |a| = 1. What operation corresponds to reflection
      in the x-axis?
 7.   The only rotations that can occur in symmetries of crystals are multiples of
      60° and 90°. This can be shown as follows. The atoms in a plane section
      form a regular structure of points called a lattice. If one atom is fixed as
      (0, 0) all atoms will be a set L of points (x, y) such that if (x, y) E L and
      (w, z)Gf then (x + w, y 4- z) E L and (— x, —y) E L. That is, it will be a
      subgroup of R X R. In order for atoms to be a finite distance apart in
      2-dimensions the lattice must have 2 generators, z, w. If A is the matrix
      of the rotation, ^4z = HjZ 4- n2w, Aw = n3z + n4w, nx, n2, n3, «4 G Z.
      Thus the trace (sum of diagonal entries in any basis) is nx + n4, an integer.
      The trace is independent of basis. For a standard basis a rotation will be
      represented as
                 cos d     sin 6
                —sin 6    cos d_
      with trace 2 cos 0. Thus 2 cos d = nx + «4, an integer. Show this implies 6
      is a multiple of 60° or 90°. Give examples of lattices (or regular tilings)
      with 60° and 90° symmetry.
106                           Semigroups and Groups                        [Ch. 2
Level 3
 1. The linear system
              y' = ay + bz
               z' = bz + ay
B 0"
A /.
EXAMPLE 2.14.1. Consider all labellings of the vertices of a square with {0,1}.
There exist 24 = 16 such labellings since each vertex can be labelled 2 ways no
matter how previous vertices have been labelled. But if we consider symmetry
there are precisely 6 distinct labellings:
                               1
i_
                                                          1   o'
                                                 o
             o
                           5                         >
                               _1
_1
                                                              -1
                                                          o
             ot
                                                 o
                      I
             'l       f        ‘i      r
                      1_
                           9
                  o
i i_
Proof Let S = {(jc, #): £(x) = jc}. For each element g G G we have fg members
of S. So |S| = 2 fg. On the other hand for a fixed X the number of elements g
such that £•(*)= x equals the isotropy group of x. This has size |G| IChJ"1 by
Theorem 2.12.3. So any orbit contributes in all
EXAMPLE 2.14.2. Suppose G is the symmetric group. Then two labellings are
equivalent if each label occurs the same number of times.
108                           Semigroups and Groups                            [Ch.2
            — 2 \L\c(g)
            \G\
where L is the set of labels and c(g) is the number of cycles of G.
PG(otx +a2 + ... + am, ai2 + a22 + ... + am2,... + oc2k + ... + amk)
Proof. We apply Lemma 2.14.1 to the set S of labellings in which a,- occurs
exactly «,• times. By the lemma the number of equivalence classes equals
                     ~ 2 |s E S : (s)g = s |
                     |G[ g
 Suppose g has c^g) orbits of length g. Then it suffices to show
Is E G : (s)# = s |
Choose representatives Xy of all /-cycles. Let S,- = (jc,y}. The the labellings of
X invariant under g are the same as labellings of these representatives. The
condition on the number of labels is equivalent to saying that the number of
occurrences of oq in St plus twice the number of occurrences in S2, and so on,
equals n(. Note that c,-Qr) — |5,-|. Thus the number of choices mentioned equals
the number of ways to choose a term from each of the following
Ci(g) times
ck(g) times
in the product. □
             |(12+ 2(2)) = 2.
    The two labellings are
                                            _1
                                1
             "l         f
                            >
             -0 -1.              _-i            i_
EXERCISES
Level 1
 1. Work out the labellings of a square by {0,1} using Polya’s method. Imitate
    the last example but use only a0, ax.
110                         Semigroups and Groups                         [Ch. 2
Level 2
 1. In switching circuits designers are concerned with functions on n Boolean
    variables. Thus we have a set of 2” elements (all values of xh x2,..., xn)
    acted on by the permutations of      x2,..., xn. These are labelled with 0,1.
    Use Polya’s theory to compute the number of nonequivalent functions of
    this kind for n = 2. Example: the following are distinct.
            0    0    0           0    0    1            0    0    1
            0    1    0           0    1    0            0    1    1
            1    0    0           1    0    0            1    0    0
            1    1    0           1    1    0            1    1    0
    The group has two elements, the identity and (12). The latter acts with a
    2-cycle and 2 1-cycles.
 2. Consider switching circuits with a larger group generated by both permuta¬
    tion and complementation of input variables. For the group has n ! 2”
    elements for n variables. For « = 2we have
                1                 4    0    0    0
                2                 10  0          1
                3                 0 2 0          0
                2                 2 10           0
    (In fact it is the symmetry group of a square.)
 3. Write out the functions for Exercise 2.
 4. Do Exercise 2 for three variables. The group will be the symmetry group of
    a cube, of order 48.
 5. Find a general formula for the number of ‘necklaces’ of black and white
    beads. This is the same problem as labelling a regular rc-gon with {0,1}. The
Sec. 2.15]                         Kinship Systems                               111
    group is the dihedral group of order 2n and has the following elements for
    n odd (consider only this case here), where d is any divisor of n: <p(d)
rotations having n/d c?-cycles and n reflections having 1 1-cycle and —-—
Level 3
 1. Solve the switching circuits problem for n = 4 with complementation (see
    Exercise 2 of Level 2).
 2. Solve the necklace problem for n even (see Exercise 5 of Level 2).
 3. How many distinct molecules can have this configuration
x-y-u
                    vl
    where each letter represents one of three given atoms?
 4. Compute the number of distinct cyclic strings of 0, 1 of length n. Two are
    equivalent if they can be made to coincide by taking the last element. This
    is like the necklace problem except there are no reflections.
 5. Compute the number of ways to color the vertices of a cube with 4 colors
    such that each color occurs twice.
KS7.   Every person has some relative by marriage and descent in each other
       clan.
KS8.   Whether two people who are related by marriage and descent are in the
       same clan depends only on their relationship, not on which clan either
       belongs to.
     Let the clans be numbered 1,2,...,n. Let w be the function such that
w(z) is the clan of the wife of a person in clan i. By 1, 2 there is such a function.
By (KS3) it is a permutation. Let d be the function such that d(i) is the clan of
the children of a man in clan i and a woman, necessarily in clan w(i). By (KS4),
d exists, and by (KS5) it is a permutation. (KS7) states that the group G of
permutations generated by w, d is transitive. (KS8) states that if for some i and
some element g of the group G,(i)g^i then (f)g = j for all /. (KS7) now
implies that w is not the identity. Moreover any permutations w, d satisfying
these conditions give a possible kinship system.
     We will now relate this to a theorem in group theory.
            fe    a   b   x   y   z
            \x   y    z   e   a   b
Proof. We first show the regular representation satisfies these conditions. For
any x,y let g = x~xy. Then (x)fg = xg —              = y. Thus the representation
is transitive. Suppose (x)fg = x. Then xg = x so g = e.
      Now suppose G satisfies (1), (2). We number the elements of G as follows:
for any element g, number it (l)g. By condition (2) these numbers are distinct
and by Condition (1) they include all of 1, 2,..., n. Now r(h) is the permutation
which takes (l)g to (1 )gh. But that is precisely the effect of the permutation h.
So r(h) = h. So G is the regular representation of itself, if its elements are
propertly numbered. This proves the theorem.                                    □
EXAMPLE 2.15.2. The Kariera tribe of Australia has been associated with this
marriage system although some regard it as an oversimplification.
Banaka-Burung
Palyeri-Karimera
Horizontal lines denote the tribe of a husband or wife, vertical ones those of a
parent or child.
EXAMPLE 2.15.3. The Arunta tribe of Australia has been associated with this
marriage system, where horizontal and vertical lines denote spouse and lines at a
45° angle, parent or child.
Panunga■ Purula
Appungerta" Kumara
Umbitchana Bultara
Ungalla Uknaria"
EXERCISES
Level 1
 1. Graph the kinship structure corresponding to {Z4, 1,3}. Vertices are clans
    and edges are labelled d or w from one clan to another.
 2. Graph all kinship structures with group Z2.
114                          Semigroups and Groups                          [Ch.2
Level 2
 1. What is the condition that the clans of children be distinct from those of
    their mother?
 2. What is the condition that mothers, fathers, and children belong to three
      different clans?
 3.   Find the smallest examples of the Exercise 1.
 4.   Find the smallest examples of the Exercise 2.
 5.   Work out Example 2.15.2. as a regular representation.
 6.   Do the same for Example 2.15.3.
Level 3
 1. What is the condition that first-cousin marriages be impossible? There are
    four cases: the mothers are sisters, the fathers are brothers, the father of
    one is the brother of the mother of the other. Show the first two cannot
    happen.
 2. Find the smallest example for which the first exercise of this level holds.
 3. Prove a group of order p2 is commutative. By an earlier exercise, the center
    must be at least Zp.
 4. Show for any subgroup H of a group G, G acts as permutations of the
    cosets of H by (Hx)g — H(xg).
 5. Show every transitive permutation representation arises as in the above
    exercise where H is the isotropy group of an arbitrary chosen point.
In this section we briefly describe some results about lattices of normal sub¬
groups of a group. This theory also applies to modules,vector spaces, and ideals
in rings.
    Recall a lattice is a partially ordered set in which every pair of elements have
a least upper bound {join, denoted V) and a greatest lower bound {meet,
denoted A). Any linearly ordered set, the subsets of any set, any Cartesian
product of lattices forms a lattice. For intersection and union of sets (and for
any linearly ordered set), the distributive laws hold. Any lattice in which they
hold is called distributive.
Sec. 2.16]                       Lattices of Subgroups                          115
a A (b V c) = (a A b) V (a A c)
aV(JAc) = (aVi)A(aVc)
EXAMPLE 2.16.1.
The first lattice is distributive. The second is modular, but not distributive. The
third is not modular. The matrices of the three partial orders are
    1    0     0    0    0        1   0    0    0    o’       1   0   0   0    0
    1    1     0    0    0        1   1    0    0    0        1   1   0   0    0
    1    1     1    0    0   J
                                  1   0    1    0    0    >
                                                              1   0   1   0    0
    1    1     0    1    0        1   0    0    1    0        1   0   1   1    0
    1    1     1    1    1        1   1    1    1    1        1   1   1   1    1
The latter two lattices are known as a diamond and a pentagon.
EXAMPLE 2.16.2. Most subspaces of Vn are not sublattices, because they are
not closed under products of vectors. However, the subspace {(0, 0), (0,1), (1,1)}
is a sublattice.
     Every sublattice of a modular lattice is modular and every sublattice of a
distributive lattice is distributive.
bvc
3a(6vc)
(a Ah)vc
follows from the diagram. The other relations follow from these and the diagram.
This completes the proof.                                                     □
EXERCISES
Level 1
 1. Why is a linearly ordered set a lattice?
 2. Prove a linearly ordered set is distributive (consider six cases for the
    distributive laws: a < Z? < c, a < c <    < c < a, c < Z> < a, b  a ^ c,
    c<a<b).
 3. Draw the lattice of (0, 1}.
 4. Do the same for subsets of (0,1, 2}.
 5. Draw the lattice of subgroups of Z3 X Z3. Write out the elements. All
    subgroups except e, Z3 X Z3 are cyclic of order 3.
 6. Draw the lattice of subgroups of Z8. (They are all cyclic.)
118                          Semigroups and Groups                             [Ch. 2]
 7. Draw the lattice of subgroups of Z6. Use the multiplication table. (All
    subgroups are cyclic.)
 8. Show a finite lattice has a smallest element 0, and that 0 V x = x for all x.
Level 2
 1. Find an example of an infinite lattice with no smallest element.
 2. A basis is a minimum generating set under V of the nonzero elements of
    a lattice, i.e. a set of generators such that no proper subset generates the
    lattice. Prove any finite lattice has a basis. Show the set of integers has no
    basis.
 3. Show V is associative in any lattice.
 4. The positive integers form a lattice under the relation n divides m, although
    this cannot be proved without some number theory. What is 6 V 10? What
    is 10 A 6? Do you think this lattice is distributive?
 5. Show that the family of all subgroups of a group (not necessarily normal)
    is a lattice under inclusion. What are the operations?
 6. Show that if L is any finite partially ordered set in which A always exists,
    and L has an element 1 larger than any other, L is a lattice. Define V by
    a V b = A z.
             z>a,b
 7. Prove the dual of the above exercise that any subset of a finite lattice
    containing 0 and closed under V is a lattice under the partial order. Give an
    example for L = subsets of (1, 2, 3} where it is not a sublattice.
Level 3
 1. Show that if a lattice is modular but not distributive, it contains a diamond.
 2. Show that the basis for any finite lattice is unique and consists of all x such
    that if x = y + z then x = y or x = z.
 3. Let B be the basis for a finite distributive lattice L regarded as a partially
    ordered set. Show that B determines the structure of L. Specifically show
    that L is isomorphic to the lattice of subsets S in B such that if x G S,y<x
    then y E S, that a specific isomorphism is given by sending S to V x.
                                                                       *e ,s
 4. Prove any distributive lattice with basis B is isomorphic to a sublattice of the
    lattice of subsets of a set. Show in particular L is isomorphic to a sublattice
    of the subsets of itself by the 1-to-l map sending x to {y e B : y < x}. No
    similar result is known for modular lattices.
 5. Prove that if a A (b V c) = (a A b) V {a A c) for all a, b, c in a lattice, that
    a V (b A c) = (a V b) A (a V c).
 6. For     a modular lattice, prove (x V y) A (y V z) A (z V jc) =
     (x A (y V z)) V (y A (z V x)). (This identity can be found in Birkhoff
     (1967).)
CHAPTER 3
Vector spaces
 In this chapter we review a number of the most important facts about matrices
 and linear algebra, some of which are needed in later chapters. A field is a
system such as the rational, real, or complex numbers, in which addition, multi¬
 plication, subtraction, and division exist and satisfy the usual laws of algebra
(exclusive of order properties). A vector space over F is a set V in which addition
D + w is defined and scalar multiplication cv is defined for c in F, v in V,
having various properties such as u+ w = w+ u. The standard example is the
 spaces of n-tuples Fn of elements of F, where (x1(x2,          + (yi,y2,...,yn) =
(xi + yux2 + y2, .... xn + yn) and c(xu x2,            xn) = (cxu cx2,       cxn).
Vector spaces are used to study systems of linear equations, geometry of
 ^-dimensional space, forces and velocities in physics, supply and demand for
many goods in economics, and have other uses.
      Every vector space has a set {vu v2,vk} of vectors such that all vectors
w can uniquely be written as linear combinations civx + c2v2 + ...+ ckvk.
A set {Vy, v2,..., vk] is called a basis. The number of vectors V\, v2,vk is
called the dimension of the vector spaces.
      A matrix is a rectangular array of numbers. Matrices can be added,
subtracted, and multiplied. The rule AB = BA does not always hold, and
inverses A'1 may not exist. For given bases, there is a 1-1 correspondence
between matrices of a certain size and linear transformations / from one vector
space to another, i.e. functions / such that f(cv) = cf(v) and f(v + w) =
f(y) + /(w). A set of simultaneous linear equations may be written as a single
matrix equation xA — b.
      The determinant of a matrix is a somewhat complicated function having
many properties such as det (A B) = det (A) det (B) and det (A) =£ 0 if and only
if A has an inverse. The characteristic polynomial of an n X n matrix is the
polynomial of degree n det (tl — A) = 0. It is a similarity invariant of a matrix,
that is, it is the same for A as for XAX'1. This means it gives properties of a
linear transformation independent of the basis. Its roots are eigenvalues of the
matrix A, that is, numbers k such that for a nonzero vector v, vA — kv.
120                               Vector Spaces                             [Ch.3
    A vector can be regarded as simply an n-tuple of real numbers. Thus the set
of vectors is in 1-1 correspondence with the set of points in ^-dimensional
space, represented by coordinates. Unlike points, however,vectors can be added
and multiplied by numbers.
a + b = b + a, ab = ba
a(b + c) = ab + ac
EXAMPLE 3.1.4. The rational, real, and complex numbers are fields.
    The field will be the set of ‘numbers’ by which vectors can be multiplied as
3(1, —1) = (3, —3). Elements of it are called scalars.
(v + w) + Z = V + (w + z), V + tv = W + V
0+v = v
and, for the zero, identity elements 0,1 of the field we have
0 • v = 0, 1•v = v
EXAMPLE 3.1.7. The set of all ^-tuples (vlt v2,..., vn) over F is a field with
operations (xj, xa,.... x„) + (j>i, J'a. •••. T») = (x1 + yux2 + ya,.... xn + yn)
and c(vu v2,..., v„) = (cvx, cv2, ...,cvn), c G F.
EXAMPLE 3.1.9. The set of functions from any set X to F is a vector space
under the usual addition of functions and multiplication of functions by
constants.
122                              Vector Spaces                               [Ch. 3
EXAMPLE 3.1.11. Let I = {1, 2, 3}. Then our indexed family consists of three
sets Ax, A2, A3. The product is the set of all functions g such that g(l)GAi,
g(2) e A2, g(3) e A3. This can be written (Ui, g2, gi) : gi G Ax, g2 G A2,
g3 G A3}. So we see this really is the same as the previously defined Cartesian
product.
EXAMPLE 3.1.12. The set of vectors {(1,0, 0), (1,0, — 1), (—1,0, 2)} is
linearly dependent, since
EXAMPLE 3.1.16. For any n the set of n-tuples {(1, 0,..., 0), (0,1,..., 0),
..., (0, 0,..., 1)} with (n — 1) zeros and 1 one is linearly independent.
Sec. 3.1]                              Vector Spaces                          123
DEFINITION 3.1.6. The span <S) of a set S of vectors is the set of all linear
combinations ft zq + f2 v2 + ... + /„ vn where ft G F, zq G V, and n is any
positive integer.
EXAMPLE 3.1.17. The span of {(1,0, 0), (0,1, 0)} is the set of all vectors of
the form (ft, f2, 0) for ft G F.
     Vector spaces are frequently studied in terms of subsets called bases. Two
vector spaces with bases of the same size are isomorphic. A basis gives a system
of coordinates (which need not be at right angles to one another). Thus the usual
x, y, z coordinates correspond to the basis {(1, 0, 0), (0,1,0), (0, 0,1)}.
PROPOSITION 3.1.2. The set (zq, v2,..., vn} is a basis for V if and only if
every vector v G V has a unique expression v = ft zq + f2 v2 + ... + /„ vn where
/i'SF.
Proof. Let {zq, v2,.... vn} be a basis. Since it is a spanning set, for any v,
v = ft Vi + f2v2 + ... + fnvn for some ft G F. If the ft are not unique take the
difference of two expressions for v. This gives a relation gx zq + g2 v2 + ... +
gnvn = 0 where not all gj = 0, a contradiction to independence.
     Suppose conversely every vector v G V has a unique expression
v = ftvx + f2v2 + ... + fnvn. Then zq, v2,...,vn spanV. Let v = 0. Uniqueness
shows that all ft = 0. This proves independence.                               □
EXAMPLE 3.1.18. The set {(1,0), (0,1)} is a basis for any fixed a G F, for the
space of all ordered pairs (ft, f2).
124                               Vector Spaces                               [Ch.3
THEOREM 3.1.3. Any independent set maximal under inclusion is a basis, and
any spanning set minimal under inclusion is a basis. Every independent set is
contained in a basis and every spanning set contains a basis.
Proof. Suppose S spans V but is not a basis. Then some vector v £ S is a linear
combination of the other members of S. Thus if w is deleted, we still have
a spanning set. So S is not minimal.
      Suppose S is independent but not a basis. Then it does not span S. So some
vector v of V is not a linear combination of elements of S. Then S U {v} is
independent: if fxvx + f2v2 + ... + fnvn + fn+xv = 0 then fn+xv = 0 since
vfi(S) and ft = 0, i < n + 1 since S is independent. This proves S is not
maximal.
      Let S be an independent set. Consider the family F of independent sets
which contain S. The family F is partially ordered by inclusion. Any chain C in
F is bounded by the union of the members of C, which will be independent:
if fxvx + f2v2 + ... + fnvn = 0 take members Cj, C2,..., Cn of C containing
vx, v2, ..., vn respectively. Let Ck be the largest under inclusion. Then all
vxE Ck and /} = 0 by independence of Ck. Thus C is bounded. So by Zorn’s
Lemma, F has a maximal element. This will be a basis by what was proved
above.
      Let S be a spanning set. The Well-Ordering Principle which can be proved
from the Axiom of Choice, states that there exists a linear ordering < of S in
which every subset of S has a least element.
      Let T — {s E S: s is not a linear combination of elements t < s in the
ordering}. Suppose T is dependent. Let /i -E f2 t2 + ... + /„f„ = 0. Assume
all ft    0 else delete that term. Let the last of tx, t2,..., tn be tk. Then tk is a
linear combination of prior elements. This contradicts the definition of T.
      Suppose T does not span V. Then since (S) = V it cannot span S. Let t be
the first member of S not in <T>. Then t is not a linear combination of prior
elements since prior elements are in <T) and t would be. So by definition of
 t, t e T. This is a contradiction. So T is a basis.                               □
     This theorem assumes the Axiom of Choice, and cannot be proved without
it for infinite-dimensional spaces. For finite-dimensional spaces, its main use, the
Axiom of Choice is not needed.
EXAMPLE 3.1.20. The set 5 = {(0, 0, 0),(1, 0,1),(2, 0, 2), (0,1, 0), (1,1,1),
(0,0,1), (1,0,2)} spans the set of all ordered triples of R. To obtain a basis
delete all elements of S which are linear combinations of prior elements. This
leaves {(1,0,1), (0,1,0), (0, 0,1)} which is a basis.
Sec. 3.1]                         Vector Spaces                               125
     We will conclude this section with a brief history of vector analysis. The
parallelogram method of addition for vectors was discovered by the Greeks for
addition of velocities. It was used to represent addition of forces by physicists
in the sixteenth and seventeenth centuries. C.Wessel, a Norwegian surveyor, in
1799 discovered the geometric representation of complex numbers (which are a
vector space over R) and extended some results to 3 dimensions. This result was
independently discovered by C. F. Gauss, J. R. Argand, C. Mourey, and J. Warren.
W. R. Hamilton tried for years to find a system that extends the complex
numbers in the same way the complex numbers extend the real numbers. He
found no 3-dimensional system, but a 4-dimensional noncommutative one
called the quaternions, with basis 1, /, /, k where i2 = j2 = k2 = — 1 and ij = k,
jk = ki = /,// = —k, kj = —i, ik = —j. This system can be used to represent
rotations in 3-dimensional space. He also introduced the operators del and del2
of mathematical physics.
     Operations of dot and cross product were introduced by A. M. Moebius,
H. G. Grassman, A. Barre and others. Grassmann in particular considered very
general types of n-dimensional systems with vector space operations and various
types of products, some not even associative.
     P. G. Tait further developed the theory of quaternions. The modern form
of the theory of vectors is due to two mathematical physicists, J. W. Gibbs and
O. Heaviside. Much of the above material is from J. M. Crowe (1967).
     The nineteenth century was the time of the beginnings of a number of other
concepts of abstract algebra. A. Cauchy studied cycles of permutations and
transpositions. E. Galois studied groups as a method of proving polynomials
of the fifth degree were not solvable, and discovered the importance of normal
subgroups and commutativity. A. Cayley proved his previous cited theorem.
     Fields of algebraic numbers were implicit in the work of E. Galois on
solving polynomials. Finite fields Zp were discovered by C. F. Gauss, in his work
on congruences. Gauss also discovered what in effect were deep results about
algebraic number fields in his work on quadratic forms, quadratic reciprocity,
and other types of number theory. E. Kummer studied algebraic number
fields in order to solve many cases of Fermat’s still unsolved conjecture that
xn + yn = zn, n > 3 has no solutions in whole numbers. These authors did not,
however, use the abstract, axiomatic approach based on set theory which is
used today. This came about as an attempt to find rigorous foundations for all
of mathematics, especially calculus, in the late nineteenth century. G. Cantor is
generally considered the inventor of set theory.
EXERCISES
Level 1
 1. Add (1,2, 3), (4, —5, 6), (—5, —10,1).
 2. Multiply (1,0, -2) by -3.
126                                Vector Spaces                                [Ch.3
Level 2
 1. Prove that for any a, b, c: {(1, 0, 0), (a, 1, 0), (b, c, 1)} gives a basis for all
    triples of real numbers.
 2. Give an example of a subset of {(<z, b)\ a, b E R} which is closed under
    addition but is not a vector space over R.
 3. Tell why if a field Fj is contained in F2 that F2 is a vector space over F2.
    What is a basis for the complex numbers as a vector space over R?
 4. Find a subset of this set which is a basis, by the method of Example 3.1.20:
    {(0,1,0),(1,2,0),(2,4,0),(1,3,6),(1,1,1),(2,2,2)}.
 5. Extend this independent set to a basis: {(1,1,1), (1, 2, 0)}. To do this, add
    a spanning set {(1,0, 0), (0,1,0), (0, 0,1)} and apply the method of the
    last exercise.
Level 3
 1. Does any countable set have a well-ordering?
 2. Use the existence of a basis for the real numbers over the rationals to
    construct a function / from the real numbers to itself such that /(x + y) =
    /(x) + f(y) but / is not continuous.
 3. Add the quaternions 1 4- 2/ + 3/ +4k and 2 + i + j — k.
 4. Multiply them. The distributive law holds for quaternions.
 5. Prove that the associative law holds for the quaternions. It suffices to check
    the basis elements ±1, ±i, ±j, ±k. If one of x, y, z is the identity, the relation
    (xy)z = x(yz) always holds. Factor out all minus signs. By symmetry in
    /, /, k assume x = i. Then check 9 cases for y, z = /, /, k.
EXAMPLE 3.2.1. For finite sets this means the number of elements in 5 is
less than or equal to that in T.
Proof. Each equation can contain only a finite number of variables. Thus if E
is infinite the number of variables which actually appear in the equations will
be no more than |ZX£’|=|£’|<|I|. So some variables will not appear in any
of the equations. Let the variables which appear in the equations be zero,
and assign arbitrary nonzero values to finitely many others.
     Thus we may assume E is finite. We may now by a standard procedure
reduce E to a simpler system E1. Take the first equation and choose a variable
which occurs in it with nonzero coefficient. Eliminate this variable from the
other equations by adding or subtracting a multiple of the first equation. At
the z'th stage, if the z'th equation is zero, delete it. Otherwise choose a variable
which occurs in it with nonzero coefficient, and eliminate that variable from all
the other equations by adding or subtracting a multiple of the z'th equation. At
the final stage each chosen variable will occur in only one equation. Since there
are more variables than equations, some variables must not have been chosen.
Assign variables not chosen, arbitrary nonzero values. Then there will exist
unique values of the chosen variables satisfying all equations (just solve the
equations for the chosen variables).                                              □
             (
                 x + 2y + z = 0
                 3x — 2y + 4z = 0
128                                 Vector Spaces                              [Ch. 3
has the nonzero solution x — —10, y — 1, z =8. Any multiple of this gives
another solution.
THEOREM 3.2.2. Any two bases of a vector space have the same cardinality.
Proof. Let and {w/}/<= j be two bases for V. Suppose |I| < 1JI. Since
                 Wi =    2     an
                        fe i
for each j G J. By Theorem 3.2.1 there exist {x,-}j^j not all zero but only
finitely many nonzero solving the equations
              2 OijXj = 0
             /e J
for all i G I. Therefore
DEFINITION 3.2.2. The (external) direct sum of vector spaces V1; V2, ...,Vn
over F is the set of all ^-tuples (v2, v2,.... vn) such that v{ G Vj for each i. Addi¬
tion and scalar multiplication are defined by (v2, v2,..., Vn) + (w1; w2,..., wn) =
(Vi + wlt V2 + W2,...,vn + wn), c(vu v2,..., vn) = (cv2, cv2, ...,cvn) where
c G F.
EXAMPLE 3.2.4. The direct sum F ® F © ... © F is the usual space of n-tuples.
It is denoted Fn. This vector space is the same as the Cartesian product Fn
mentioned in previous sections.
    This definition extends to infinite direct sums and products. The direct
product is as in Definition 3.1.4. A direct sum, or restricted direct product in
somewhat confusing language is the subset of the direct product consisting of
functions which have only a finite number of nonzero values.
     A basis for a direct sum space can be obtained as the union of bases for each
vector space Vj. Therefore the dimension of a direct sum of vector spaces Vj is
the sum of dim Vj.
EXAMPLE 3.2.7. The vector space F2 is the direct sum of the subspaces         =
{(x, x) : x G F} and W2 = {(x, 0) : x G F}. In fact (x, y) = (y, y) + (x — y, 0)
for all xjGF.
Proof. Let V be the internal direct sum of Wlt W2, ..., Wn. Let f :V-*■
Wi © W2 ©... © Wn be defined by /(w! + w2 + ... + w„) = (wj, w2,..., wn). Let
g: Wi © W2 © ... © Wn -»-V be defined by g(wi, w2,..., wn) = Wi + w2 + ...+ wn.
Then / and g are homomorphisms, and gf(x) = x and fg(y) = y. Thus g is the
inverse of f                                                                    □
EXERCISES
Level 1
 1. Find a nonzero solution of these equations:
Level 2
 1. Prove |Z X Z| < |Z| because |Z| = |Z+| and the map (x, _y) -*■ 2X3 y on Z+
    is 1-1. Here Z+ denotes the set of positive integers.
 2. Prove |RXR|< |R I as follows: write a real number x as an infinite decimal
    (if a999 ... occurs replace it by a + 10 000). For two real numbers x, y.
    form the real numbers obtained by alternating digits of x, y. Thus if
    x = 0.101 and y = 0.345 send (x, y) to 0.130415. Show |R X Z| < |R|.
 3. What is the dimension of {(x, y, z) : x + 2y + 3z = 0}? Find a basis.
 4. What is the dimension of {(x, y, z) : x 4- y = 0, y + z = 0}? Find a basis.
 5. Find a complement to the space spanned by (1,1, —2) in {(x, y, z) :
    x + y + z =0}.
Level 3
 1. Prove the Schroder-Bernstein Theorem in the case where one set is finite.
 2. Using Exercise 1 prove when both sets have cardinality at most |Z|, hence
    have cardinality exactly |Z| or are finite.
 3. Find (possibly in a book) a general proof of the Schroder-Bernstein
    Theorem. One method is as follows: Suppose we have 1-1 maps /: X -* Y
    and g: Y -» X. To an element x G X associate the set Cx of all elements
    of X which can be obtained from x by iterating f g, f~l, g_1 where
    defined. For yEf define a similar set Dy. Show that f(Cx) C •£>/(*) and
    g(Dy)C Q(X). This gives a 1-1 correspondence between the family {Cx}
    and the family {Dx}. To construct a 1-1 correspondence from X to Y it
    suffices to construct a 1-1 correspondence on each Cx to -£>/(*) by the
    Axiom of Choice. This reduces the problem from X, Y to the case
    Cx, Df(xy Show these sets are at most countable. Next use Exercise 2.
 4. For vector spaces U, V, W, let ilf i2 be the inclusion U-*U®V,V-*U©V
    and 7?!, 772 the maps 77!(x,.y) = x, 7r2(x, y) = y. For any vector space homo-
    morphisms fh f2 (i.e. /(ax) = af(x) and /(x +y) = /(x) + f(y)) from
    W -*■ U, W -* V, show there exists a unique homomorphism /(W) -+ U © V
    such that / °     =/i, / o 7r2 = fi- Show for any homomorphisms g^: UW
    and g2 : V -> W there exist a unique homomorphism g: U © V -> W such
    that z'i <©£ = gu i2 O g2 = g2.
 5. Prove either property in Exercise 4 uniquely characterizes U © V, that for
    any space W having the property W must be isomorphic to U © V.
3.3 MATRICES
It is assumed that the reader is familiar with basic operations on matrices by
earlier study but we review the basic definitions here.
     An n X m matrix over a set S is an indexed collection ay of elements of S
for / = 1, 2,..., n and / = 1, 2,..., m. That is, it is a function from the set
{1, 2,..., n] X (1, 2,..., m} to S. Matrices are usually represented as rectangles
132                                             Vector Spaces                 [Ch. 3
of elements of S, with the value fly in row i and column /. However, they exist
as functions independent of any particular diagram. The set S will usually be
assumed to be a field, or at least to have operations of addition and multiplication
in it, as well as additive and multiplicative identities 0,1.
DEFINITION 3.3.1. The nXn identity matrix is the matrix I = (5 y) such that
5y = 1 if i = / and 8y = 0 if i =£ j.
EXAMPLE 3.3.1.
             "l       0       o"
              0       10
             —
              0       0       1   —
DEFINITION 3.3.2. The mXn zero matrix 0 is the matrix all of whose entries
are 0.
EXAMPLE 3.3.2.
              0       0       0            o"
              0       0       0            0
              0       0       0            0
     This means in the case of addition that entries in the same locations in A, B
are added to give the entry of A + B in that location.
EXAMPLE 3.3.3.
EXAMPLE 3.3.4.
                -1        3              2        3   -1     =   6   8 -3
                4         2              0        0    1         4   10    4
    Addition is defined only if both matrices have the same number of rows and
both have the same number of columns. Multiplication of an n X m matrix times
an r X s matrix is possible only if m = r. The answer is then n X s. Matrices
obey the following laws, assuming addition and multiplication in S have the
corresponding properties (e.g. if S is a field).
        A + B = B + A,              A + (B + C) = (A + B) + C,                  (AB)C = A(BC)
       A(B + C) = AB + AC,                    (B + C)A ~ BA + CA,               0 + A=A
IA = AI = A
EXAMPLE 3.3.5.
            A =       1        0
                      1        0_
Then A has no inverse since for any B, both rows of AB are equal since both
rows of A are equal.
DEFINITION 3.3.5. A matrix is a diagonal matrix if all entries not on the main
diagonal are zero.
134                                  Vector Spaces                           [Ch. 3
EXAMPLE 3.3.7.
'2 0 ~
_0 3_
     Any diagonal matrices will commute. However, the commutative law is not
true for all pairs of matrices.
     The (i, /)-entry of the mth power Am of a matrix is denoted aif'm\
     The ith row of A is written At* and the ith column A*,-. (By replacing the
asterisk with numbers we obtain the entries of the row or column.) A 1 X n
matrix is called a row vector. An n X 1 matrix is called a column vector.
    That is, the (i, /)-entry of A becomes the (/, z)-entry of AT. Rows
become columns and columns become rows. We have (A + B)T = AT + BT,
(AB)t = BtAt, (At)t = A.
EXAMPLE 3.3.8.
                           T
             '1    2           'l    6
0 1_ 2 i_
(vA)i = (2 vk aki)
A(av) = a(Av), Iv = v, Ov = 0
11 Al2 .. • Ain
21 ^22 •• ■ A2n
nl An2 • ■ ■ ■ Ann
EXAMPLE 3.3.9.
                 1        2               4                5
                 0        0               1                0
                 1        1               3                2
                 1        1               1                0
                              "l                  2                           4    5"
                                                       5       ^4l2 —
                              0                   0_                          1    0
                              "l                  1                           _3   2"
                                                                   II
                                                                    c*
_1 1_ .1 0_
 belongs to the (s, t)-block. Thus the (s, t)-block of AB is E AskBkt. Here dk
                                                             Jc
 denotes the kth block.                                                     □
'1 1 f 0 1 0"
             0        1             1                  1       0      0
                                           5
_0 0 1. _1 0 1_
Then A + B, AB are
"1 2 f 2 1 r
             1        1              1        5
                                                       2       0         1
             1        0             2                  1       0         i_
136                                           Vector Spaces             [Ch.3
Note that
      "l    f                 1
                                  +        [1      0] =            +
       0    1_                0
      ~1    f
                              +        [1] =
       0    1
      [0    0]                    + [1] [1       0] = [1      0]
                      1       0
                 1        1       3
                 0        1       2
_0 0 4_
EXERCISES
Level 1
 1. Find
                  1                       4
                 0                        0
Sec. 3.3]                                            Matrices             137
2. Find
3. Find
                                                                4    0
                                       + (-3)
                                                                0    0
4. Find
            "l       4   0"       "l       -1         f
             0       5   3        2         1         1
                                                 1_
             2       2-5
                                                  1
            [1           1]                -5     -9
                                            0        13
Level 2
 1. Give an example to verify the distributive law for matrices.
 2. Given an example to verify the associative law for matrices.
 3. Multiply these matrices quickly using block forms and properties of the
    identity matrix:
                                            1
            l
to
                              1        0                        10   9
                 0   1       0         1         8        7     4     5
                 1   0        1        0         3        6     9    12
                 0   1       0         1        11        9     7    5
                 a   0
                 b   a
Level 3
 1. Multiply two matrices having block form
A B~
.0 D_
                ~A   B    X        Y         7   o"
                .0   D    .o       z.        0   I
C D_
A B A O' 7 Y
C D_ X l 0 D — XY_
     In principle this and the preceding exercises give an inverse for any 2X2
     matrix in block form.
  5. Prove A 4- Ar, AAT, and ,474 are symmetric using the laws regarding
     transposes given in the text.
  6. Prove for symmetric matrices A, B that AB is symmetric if and only if
     A, B commute.
 '7. Prove that a matrix A commutes with any polynomial c0/ + c^A 4- ... +
     cn An where c,- e F.
represented by a matrix for a given basis. Conversely every matrix gives a linear
transformation.
DEFINITION 3.4.1. Let Vand W be the vector spaces over F. A function g from
V to W is a linear transformation if and only if g(ax + by) = ag(x) + bg(y)
for all a, b EF, x, y E\.
EXAMPLE 3.4.1. Let V be the vector space of all polynomials with coefficients
in a F containing the rationals. The following are linear transformations on V.
£(*W(*), *(*)-**(*)-*(0)
Proof Since
so
ki = 2 //«//
            '1    f
            .2    2_
on row vectors. Then the image space of g is the set of vectors having the form
(x, x). The kernel of g is the set of vectors having the form (— 2x, x). The rank
of g is 1.
DEFINITION 3.4.3. The row (column) space of a matrix is the vector space
spanned by its rows (columns). The row {column) rank is the dimension of
the row (column) space. The row (column) rank of A will be denoted by
PrOO (PcU))-
”l l"
2 2_
are {(x, x) : x E R} and {(x, 2x) :x£R}, The row rank and the column rank
are both 1.
   Note that the row (column) rank can more simply be expressed as the
maximum number of independent rows (columns).
e{A = Ai*. So the row space is contained in the image space. Yet if w belongs
to the image space then w = vA = 2 ViA{* which is contained in the row space.
Therefore the image space is contained in the row space.
     The proofs for column vectors are similar.                            □
THEOREM 3.4.4. The row and column rank of a matrix are equal.
                        r
            @ij     2 @ik Pkj
                   k=1
by taking the i component of the equation above. This implies that for any
linear combination v of the Aj*,
                    r
            Vj =    2 vkpkj
                   k= 1
                                1
                                5
Then A*h A*2 form a basis. There is a 1-1 map on the row space taking [10 1]
to [1 0], [0 1 1] to [0 1], [2 3 5] to [2 3]. Thus the row space is a subspace
of R2 and is two-dimensional.
142                              Vector Spaces                             [Ch.3
EXERCISES
Level 1
 1. Find matrices to represent these linear transformations, according to
    Proposition 3.4.1: (a) /(x, y) — (x + y, y), (b), f(x, y, z) = (y, z, x),
    (c) /(x, y, z) = x + y + z.
 2. If the rows of a matrix are independent, what is its rank? What is the rank of
             1    1    1
             0    1    1   ?
0 0 1
 4. Show the zero matrix is the matrix of the linear transformation f(x) = 0.
 5. Show if A has rank k, AB and BA have rank < k for any B.
Level 2
 1. Find matrices to represent these linear transformations on the space of
    polynomials of degree <5 with basis 1, x, x2, x3, x4: (a) /(x) — /(0),
    (b) /'(x), (c) * f£f(x) dx, (d) O/O))'.
 2. What are the ranks of the matrices in Exercise 1?
 3. Prove linear transformations from V to W form a vector space. If V has
    dimension n and W has dimension m, what is the dimension of the space of
    linear transformations from V to W?
 4. Show the identity matrix is the matrix of the identity linear transformation.
Level 3
 1. For any vector v G Rn show the transformations x              (x • v)v and
    x -> x — (x • v)v are linear where x • v is the inner product 2 x,- V(. What
    are the kernels?
 2. Identify the ranks and image spaces in the above exercise, and describe
    these mappings geometrically. Prove that f O / = / for these linear
    transformations.
 3. Prove composition of linear transformations obeys the distributive law on
    each side f(g + h)- fg + fh, (g + H)f = gf + hf.
 4. Find a general form for rank 1 matrices.
 5. Prove that if a multiple of one row is added to another row, the rank of a
    matrix is unchanged. Represent such a row operation as multiplication by
    a matrix / + cE(i, j) where c times row i is added to row j and E(i, /) has
    a 1 entry in location i, j and all other entries are 0.
 6. Describe the infinite matrices of /-*■ xf and /-> /' on the space of all
    polynomials of any degree with basis 1, x, x2,          xn, _ Show these
    matrices obey the identity AB — BA = I, used in matrix mechanics.
 7. Prove any two vector spaces of the same dimension are isomorphic.
Sec. 3.5]         Determinants and Characteristic Polynomials                   143
inverts the pairs (1, 2) and (2, 3). So it is even. The permutation
Proof. A pair (z, /') is inverted by ox o2 if and only if it lies in one of the sets
S = {(/, /) : o2 inverts (/, /)} or T = {(z, /) : ax inverts (a2(z), o2(/))}, but not
both. The cardinality of this set equals |S U T\ — \S n T\ = \S\ + 171 — 215 n 71
which is an even number plus |5| + |71. Thus sign (0\02) = (—l)151 + |:r|, sign
(a2) = (—l)151, sign (aj) = (— l)|r|. This proves the first assertion.
     For the second assertion, let a interchange i, j. Then if i < k < / both (z, k)
and (k, /) are inverted. One other pair is inverted: (z, /) itself. So o is odd.   □
144                                            Vector Spaces                         [Ch. 3
EXAMPLE 3.5.2.
                   a        b          c
            det    d         e         f        aei + bfg 4- cdh — ceg — fha — dbi
g h i
 Dl. A determinant changes sign if two rows or two columns of a matrix are
     interchanged.
 D2. A determinant is linear as a function of the ith column or the jth row.
 D3. A determinant of a diagonal matrix is the product of the main diagonal
     entries.
 D4. If any row or any column of a matrix is zero, then the determinant is zero.
 D5. If the matrix B is obtained from A by replacing Aj* by Aj* — kAt* where
     i =£ j, then det (B) = det (A). Likewise for columns.
 D6. det (A) = det (Ar).
 D7. If B is obtained from A by rearranging the rows by a permutation o then
     det (B) = sign (a) det (A).
 D8. det (AB) = det (A) det (B).
 D9. det (A)     0 if and only if A has an inverse A'1 such that AA~X — A~lA = I.
DIO. Let A[i |/] be the (n — 1) X (n — 1) matrix obtained from A by removing
     the ith row and the jth column. Let C[i\j] be the {i,jjth-cofactor of
     A[i\j] which is (—l)l+’det(A[i\j\). Then
                                 n                     n
           det {A) =             2 arjC[r\j] =         2 fl/sC[z|s]
                             /=i                      «=i
     for any, r, s.
Dll. Suppose A has the form
An 0 ... 0
     where the zeros and At/- represent submatrices (blocks) and not single
     entries, and the Ati are square matrices. Then
D12. For any matrix A, let cof (A) be the matrix C[j\i]. Then A (cof (A)) =
     (cof (A)) A = I (det (A)). Thus if A has an inverse,
            A~i = c°f(A)
                          det (A)
     The matrix cof (A) is called the adjoint of A.
            "l        1        f
             1        2        3
             1        4        9
            "6-5                   l"
             -6           8 -2
                 2 -3              1
            "2            0        (f
                 0        2        0
                 0        0        2
            ~t -1             -1        -1 '
                 -1       t-1           -3
                 -1           -4        t-9
146                               Vector Spaces                               [Ch. 3
Proof Let B(t) = {tl — A) and let B(t) = B0 + Bit + B2t2 + ... + Bn_ltn~1
be the adjoint of B (to expand B(t), let Bt be the matrix of coefficients of tn~l
of tn~l in B{tf). Then B{t)B{t) = det (B{tJ)I = p(t)I. So
= Pit) I
We expand
= P(A)
But AI - A = A - A = 0. So p(A) = 0.                                              □
Sec. 3.5]            Determinants and Characteristic Polynomials                  147
EXERCISES
Level 1
 1. Compute the determinant of
                                     "l        1       f        ~1       1   o'
            ~1       2
                             >        1        2       3        0        1   1
             2       3.
                                      14               9         1       0   1
                                          'o       1       o'
                                 5        0        0       1
                             -            _0       0       0_
Level 2
 1. Compute the determinant of
            a        b           c                 0       a         b
            c        a           b )           —a          0         c
            b        c           a             -b      —c            0
 2. Prove Property D2 of determinants. Show also that if all entries are multi¬
    plied by a constant c the determinant is multiplied by cn where n is the
    order of the matrix.
 3. Use Exercise 2 and Property D6 to show that the determinant of an n X n
    matrix A is zero if AT = —A and n is odd.
 4. Prove that if two rows of a determinant are equal its value is zero.
 5. Prove Property D5 of determinants.
 6. Use Property Dll to compute the determinant of
                 1       2            0        0
                 2       10                    0
             10      11               3        5
             14      15               5        3
148                                        Vector Spaces                      [Ch.3
             "l     1     l"
              1     2     4
              1     4    16
Level 3
 1. Prove Property D7 of determinants.
 2. Prove Property D8 of determinants. Show det(^45) is a function which
    is (i) linear in each row, (ii) if two rows of A are equal then it is zero. Thus
    it is unchanged under row operations as in Level 2, Exercise 5. Prove under
    permutation of the rows of A we have a property like D7. Now by such
    operations we can reduce A to a matrix having at most one nonzero entry
    per column. Prove directly det (AB) = det {A) det (B) in this case.
 3. Find a general formula for the inverse of a 3 X 3 matrix.
 4. Find recursion formulas for the characteristic polynomial of an n X n
    (0,1)-matrix A such that <z,y = 1 if / > / — 1, for example
1 10 0 “
              1110
              1111
              1111
              X     1     0    6            1    1   0     0
              1     X     1    0            1   X    1     0
                                       5
               1    1     X    i            1    1   X     1
              1     1     1    X            1    1   1     X
    by showing this coefficient satisfies the same recursion formula and has the
    same value for n = 0,1.
 7. Prove Property D9 for determinants by using row operations as in Exercise 2
    to simplify A.
 8. Show every polynomial in an n X n matrix A can be reduced to a sum of
    powers of I, A, A2,An~1. First express An this way using the Cayley-
    Hamilton Theorem. Then express An+1 in terms of An, An~\ ..., A using
    that expression and substitute the previous expression for An.
                       >
                            _
                            o
                                7
              1
1 l"
-1 1_
f(Vj) = 2 vt ay = 2 2 wkxkiaij
Therefore
              2     2 xkiaif = 2 wk 2 bkixij.
              k      i           k      i
      Since the set {wj, w2,..., wn] is independent,
             ? xkiaij =       kixij •
So XA = BX. By the same sort of argument, XY = /.                             □
Proof, det (tl - XAX~l) = det (X{tl - A)X~l) = det (X) det (tl-A)
(det (.X))-1 = det (tl — A).                                    □
EXAMPLE 3.6.2. The vectors (1,1) and (1,-1) are both row and column
eigenvectors of the matrix
0 l"
_1 0
             "l   0~
             0     1_
PROPOSITION 3.6.7. The trace is the sum of the eigenvalues, each counted
with its multiplicity. The determinant is the product of the eigenvalues, each
counted with its multiplicity.
     From here on, in this section, we assume that the field F is such that the
characteristic polynomial p(t) factors into linear factors t — kt over F. For
instance this will be true for any matrix of real or complex numbers if we use
F = C. We will also assume vectors are row vectors unless the contrary is stated.
     Let the eigenvalues of A be kx, k2, .... kr and their multiplicities be
ni, n2,..., nr. Then the characteristic polynomial is p(t) = (t — kt)ni(t — k2)”2
...(t-kr)\
             "l       0        0_
              1       1        0
             0        0 -1
has two eigenvalues: 1, with multiplicity 2, and —1, with multiplicity 1. The
characteristic subspace belonging to 1 is {{x,y, 0): x,y £ R}. The characteristic
subspace belonging to —1 is {(0, 0 ,z):zE R}.
0 0 ... B{r)
where the zeros are zero submatrices and the B{i) are square submatrices
{blocks). The characteristic polynomial of B(i) is (t —
Proof. Let f{t) = p{t) {t —           Then fXt) is a polynomial, and the different
polynomials f have greatest common divisor 1. Thus 1 = fli(0/i(0 + ci2{t)f2 (f) +
... + ar{t)fr{t) for some polynomials a,-. Such an identity will mean that the co¬
efficients of each power of t are equal on both sides. This implies that the identity
will remain true if t is replaced by A. Thus I = a2{A)fi{A) + a2{A)f2(A) + ...
+ ar{A)fr{A). Multiply both sides by the row vector v. So v = va\{A)fi{A)
+ va2{A)f2{A) + ... + var{A)fr{A). Let v(i> = vat{A)f({A). Then
v{i){A-kiI)ni = vai{A)ft{A) {A - kil)ni = vat{A)p{A) = 0 by the Cayley-
Hamilton theorem.
    So v(i)E V{. This proves that every vector is a sum of vectors lying in the
subspaces Vt. So V = V2+ V2 + ... + Vr.
    We must also show that for any choice of u(i)G Vt, that if u(\) + u{ 2) + ...
+ u<r) = 0 then u(i) = 0. We have u{i) = u(i)a1(A)f1(A) + u(i)a2(A)f2{A)
+ ... + u{i) ar{A) fr{A) = u(i)f1{A)al{A) + u{i)f2{A)a2{A) + ... +
u{i)fr{A)ar{A) since any two powers of A commute. But for j          i, fj{A) has
Sec. 3.6]                  Eigenvalues, Eigenvectors, Similarity                 153
So each u(i> is 0. This proves that V is the direct sum of Vu V2,..., Vr. If
v(A - ktI)ni = 0 then vA(A - ktI)ni = v(A - k,I)niA = 0A = 0. This proves
(Vi)A C Vh
    Let di = dim (F,). Choose vectors wx, w2,..., w„ such that Wj, w2,.... is
a basis for Vlt wdi+1, wdi+2, ... , wdl+d2 is a basis f°r       an(i so on. Then
wi, w2,..., w„ is a basis for A. Let 5 be the matrix of the linear transformation
given by A, with the wh w2, ...,wn as basis. Then B is similar to A, by
Proposition 3.6.5. And since (V^A C Vt, wtA is a linear combination of those
Wj which lie in the same subspace V{. This means that B has the form
0 0 ... B(r)
where B(i) are certain submatrices corresponding to the subspaces Vt. For
instance B( 1> is the submatrix of         such that i, j = 1,2, ...,d2. Then the
characteristic polynomial of B by Property Dll of determinants is the product
of the characteristic polynomials of the B(i). Thus p(t) = (t — ki)n\t — k2)n2 ...
(t—kr)nr = gi(t)g2(t) ... gr(t) where gt is the characteristic polynomial of
B(i). But on Vj. (A—kiI)rii=: 0, by definition of Vf. Also gt{A)= 0 on V(.
Suppose gf(t) has a root / other than kt. Then / is an eigenvalue of B(i), by
Proposition 3.6.6. So for some v G V{, vA = fv. Then y(A — A;,/)”'=
v(f — ki)Ki ^ 0. This is a contradiction. So gt(t) = (t — ki)di. So (t — ki)ni
(t — A:2)”2 ... (t — kr)nr = (t — kt)dl(t — k2)d2 ... (t — ky)dr where klt k2,... ,kr
are distinct. So nt = dt. This proves the theorem.                                 □
              2       0        0          2       0   O’       4   0   O’
              1       2        0    J
                                          0       2   0    J
                                                               0   1   0
             _0       1        2_         0       1   2_       0   1   1
154                                    Vector Spaces                         [Ch.3
However, the eigenvalues which are the numbers appearing on the main diagonal,
are sufficient for many purposes.
EXERCISES
Level 1
 1. Find the eigenvalues of these matrices.
              y     4          0   1      f       3    4   O"
              _i_   3 ’       -1   0      1   5   4    2   0
                              -1 -1       0       0    0   1_
                                                                1111
              a     b     c
              c     a     b
              b     c     a
Sec. 3.6]               Eigenvalues, Eigenvectors, Similarity                   155
                   0         1   0
            P =    0      0          1
                    1     0      0
             a    b      b       b
             b    a      b       b
             b    b      a       b
             b    b      b       a
Level 2
 1. Show by Theorem 3.6.8 that any matrix with distinct eigenvalues is similar
    to a diagonal matrix.
 2. If a matrix has distinct eigenvalues t\, t2,..., tk what diagonal matrix will it
    be similar to?
 3. Prove by induction that any matrix over C is similar to a lower triangular
    matrix. Let V\ be an eigenvector and W a complementary subspace with
    basis v2, v3,...,vn. Express the linear transformation in terms of V\, v2,,
    vn. Show there is a block triangular form. If the matrix has already been
    made similar to a lower triangular matrix on W (by choosing a suitable basis)
    this completes the proof. This suffices to establish the last proposition
    above.
4. A matrix A is called nilpotent if Ak = 0 for some k. Show all eigenvalues of
    a nilpotent matrix are zero.
 5. Conclude from Exercises 3, 4 that a nilpotent matrix is similar to a matrix
    with zeros on or above the main diagonal. Is any such matrix nilpotent?
6. If A2 = A what are the only numbers which can be eigenvalues of A?
7. Show that a matrix A has an inverse if and only if 0 is not an eigenvalue.
8. Find the eigenvalues of the nX n matrix J all of whose entries are 1. A
    complete set of eigenvectors is given by (1,1,..., 1), (1, — 1, —1,..., 0),
    (1, 0, —1,..., 0),..., (1, 0, 0,..., —1). Generalize Exercise 7, Level 1 to
    nX n matrices.
9. Generalize Exercises 5,6, Level 1 to n X n matrices.
156                                    Vector Spaces                           [Ch.3
Level 3
 1. Conclude from the Jordan Decomposition Theorem that every matrix can
    be expressed as a sum A = D 4- N where DN = ND and N is nilpotent and
    D is similar to a diagonal matrix.
 2. Show that the characteristic polynomial of a matrix can be calculated from
    the n numbers Tr (Ak), k = 1 to n. Let the eigenvalues be xk. Then
    Tr (Ak) = 2 xkk. Let this be denoted sk. Let ck be the coefficients in the
    characteristic polynomial. They are except for sign
— Ci = xl+x2 + ... + xn
               c2 =       2 XfXi
                         i<i
               C3 —        2      XjiXjXm
                         i</< m
              1      1     0      0~
               1110
               1111
               1     1     1      l_
      Use the results of those exercises in that the characteristic polynomial is the
      coefficient of un in
                   1 —u
              1 — tu + tu2
               0    1      o'
              0     0      1
               a    b      c
Sec. 3.7]                   Symmetric and Unitary Matrices                    157
"cos 0 —sin 0”
Jin0 cos0.
sin 0 cos 0 _
~2 2 + 3i
2-3 i 5_
Entries above the main diagonal must be complex conjugates of those below it.
PROPOSITION 3.7.1. Let x, y, z be any row vectors and a£F. The inner
product has these properties:
    (1) x ' x is real and nonnegative.
    (2) x • x = 0 only if x = 0.
    (3) x • y = (> • x)*.
    (4) x • (y 4- z) — x • y + x • z.
    (5) (7 4- z) • x = y • x 4- z • x.
    (<5) ax • 7 = a(x • 7).
    (7) x • ay — a*(x • .y).
y'X = = (x*^)*
EXAMPLE 3.7.5. The vectors (1, 0,..., 0), (0,1,..., 0),..., (0, 0,..., 1) are
orthonormal.
     Orthonormality means that the vectors can in effect be chosen as the basis
of a coordinate system geometrically equivalent to standard coordinates. Ortho¬
normal vectors must be linearly independent: if a^xj + a2x2 + ... + an xn = 0,
Sec. 3.7]                   Symmetric and Unitary Matrices                  159
This is
                       Vi
            Wx =
                    yjvi * vt
We have Wj-Wi^l. Given wit w2, ... ,wt construct wi+l as follows. Let
ui+i = vi+1 — ^ (Vi+1 ’ wi)wi- Then ui+1 • Wj — 0 for / = 1 to i and ui+x ^ 0.
Let
                            “/+1
            wi+1 ~    f-
                     V«i+1 ’ ui+1
Then w( • w,- = 1 and w/+1 • Wj = 0 for / = 1 to z. Moreover w,-+1 is linearly
independent from w1( w2,wt. Therefore Wj, w2, ...,wn form an orthonormal
basis.
     We can extend this to a basis for all of Cn by extending the basis   to a
basis for all of Cn and using the same process.                             □
Proof. We have UMU 1 = X where U is the matrix whose z'th row is wt.
And by orthonormality U(UT)* = I. Therefore U is unitary. So      =
(y-lxu)(u-lxu)T* = (u~lx u) (uT*xT*(u~1)T*) = (y-lxu) (u-lxT*u)
= U~1XXT*U = U~1Xr*XU = (U-lXT*U) (U-'XU) = mt*m.                               □
COROLLARY 3.7.8. The eigenvalues of a Hermitian matrix are real and those
of a unitary matrix have absolute value 1.
Proof. The matrix D = UXU~l must be, respectively, Hermitian or unitary. Thus
in the respective cases D = (Z)T)* = D* and D~l — (Z)T)* = D*.             □
EXERCISES
Level 1
 1. Write these normal matrices as U~XDU. To do this, first find the charac¬
    teristic polynomial. Then find its roots, the eigenvalues. For each eigenvalue
    k solve the linear equation vA — vk to find an eigenvector v =£ 0, (for
    instance take vy = 1). Then write U, D as in Corollary 3.7.7. The matrix U
    need not be unitary.
Sec. 3.7]                           Symmetric and Unitary Matrices            161
                  1        1        1
                  1        1        1
1 1 1
0 1 l"
             -1            0         1
             -1           -1        0
Level 2
 1. Prove directly that if M is symmetric, then two eigenvectors vx, v2 belonging
    to different eigenvalues k\, k2 are orthogonal. Show xMy = kjtq • v2 =
    k2Vi • v2. Conclude that V\ • v2 = 0 since k^k2.
 2. A quadratic form is an expression of the form
             n        n
             2        2 UijXfXj
            /=1 i = l
    such as x? + 2xxx2 — x2. Prove that the quadratic form can be represented
    as xAxt where A = (fly), x = (jc1; x2,..., xn). Here we assume the ay are
    real numbers.
 3. Show that in Exercise 2 we can always take the matrix atj to be symmetric.
    If aij =£ dji replace both by
            (djj + dji)
                      2
                 x =       vf*   y =
 8. Write the quadratic form xy + yz + xz as 2 c,-wf where cf E R.
Level 3
 1. Let M be a normal matrix. MMT* = MT*M is real symmetric, and its
    eigenvalues are the squares of the absolute values of the eigenvalues of M.
 2. Show a real symmetric matrix M has a real symmetric square root X such
    that M = XX provided that all eigenvalues of X are nonnegative. Use
    M = UDU~X and find \[D.
 3. Show any normal matrix A can be written as BC where BC = CB, B is
    Hermitian and C is unitary. Let A — UDU~X and factor D = XY where
      xii ~~   I dii I >
Rings
A ring is a general system in which there are two operations, addition and
multiplication. A ring is a commutative group under addition, a semigroup
under multiplication, and satisfies distributive laws. We describe the integers as
a special ring in this chapter. The set of n X n matrices over a field and the set
of polynomials in a variables over a field are also rings.
     There are many kinds of rings. An integral domain is a ring having a unit 1,
satisfying the commutative law ab = ba and a cancellation property that if
ac = be, c     0 then a = b. A Euclidean domain is an integral domain in which
we can divide a nonzero element y into an element x to obtain a quotient and
a remainder such that the remainder is of smaller degree than y. The integers are
an example of both. In any Euclidean domain prime numbers and divisibility
have most of the usual properties. Every element can be uniquely factored into
primes.
     An ideal in a ring R is an additive subgroup H such that if x GR, y G H
then xy, yx G H. For any ideal there exists a congruence defined by x ~ y if
and only if x — y G H. The equivalence classes form the quotient ring R/H.
In the case of the integers these concepts take the form that x=y(mod m)
if x — y is a multiple of m. For instance 5 = l(mod 2) since 2 divides 5—1 = 4.
Congruences can be added, subtracted, and multiplied. The quotient ring is a
finite ring Zm of m elements. For m prime, it is a field.
     Two numbers x, y are called relatively prime if they have no common
divisor (c.d.) except 1.
     An element c in Zm has an inverse (c)-1 if and only if c is relatively prime
to m. The elements with inverses form a group. Its order is 0(ra), the number of
positive integers from 1 to n — 1 relatively prime to m. From this follows the
Euler-Fermat Theorem x^m^ = l(mod m) if x is relatively prime to m. For m
prime the group of nonzero elements of Zm is cyclic. This gives a criterion for
equations xk = c(mod m) to be solvable.
     In Section 5 we present an advanced topic, simple and semisimple rings,
needed for the study of group representations. A ring is simple if it has no
164                                     Rings                                [Ch.4
(5) a + b = b + a, (6) a + 0 = a
DEFINITION 4.1.2. A ring R is a ring with unit if there exists an element 1^0
such that lx = xl for all x G R. It is commutative if ab — ba for all a, b G R.
     A ring is linearly ordered if the order < is also a linear order, that is, for all
x, y, z G R either x = y, x < y, or x >y. The symbol > is defined by x > y if
and only if y < x.
    The axioms for Z can now be stated compactly.
AXIOM 1. The integers are a linearly ordered, commutative ring with unit.
AXIOM 2. Let S C Z be such that (i) 1 G 5 and (ii) if x £ S then x + 1 E S.
         Then S contains all positive integers Z+(all x such that 0 < x).
    Axiom 2 is called the inductive axiom. All the usual forms of mathematical
induction follow from it.
 Zl.   1>0.
 Z2.   (-a)(h) = a(-h) = -(ab).
 Z3.   (-1)(-1)=1.
 Z4.   a(h — c) — ab — ac.
 Z5.   If a, b are positive so is ah.
 Z6.   If one a, b is positive and the other is negative ab < 0.
 Z7.   If a, b are negative, ab is positive.
 Z8.   aO = 0.
 Z9.   If a > 0 then —a < 0.
Z10.   If a < Othen -a> 0.
Zll.   If a + b = a + c then b = c.
Z12.   If ab = 0 then a = 0 or b = 0.
Z13.   \a\>0.
Z14.   If a =£ 0 then |a| > 0.
Z15.   \ab\ = \a\\b\.
Z16.   |a|+ |h| < |a| + |b|.
Z17.   The smallest positive integer is 1.
Z18.   If a =£ 0 then aa > 0.
Z19.   If ah = 1 then a = 1 or a = —1, and a = h.
Z20. |a| = | —a|.
EXAMPLE 4.1.6. The integers, any field, and any subring of a field (subset
forming a ring under the same operations) are integral domains.
      For the rest of this section, F[x] (Q[x]) will denote the ring of polynomials
 over F (Q).
PROPOSITION 4.1.2. The relation a\b is a quasiorder. We have a\b and b\a
if and only if a = ub where u is a unit. If b\aj for i — 1 to k then for any
(-h c2> ••• 1 ck ^ b \ c\ a1 c2 u2 4" ... 4" ck ak.
    Let a\b and b \a. If a or b is zero both are zero, and 0 = 1(0). Suppose a, b
are nonzero. Let a = ub, b = va. Then a = u(va). So by Proposition 4.1.1,
uv = 1. So u is a unit.
      Let ai = u(b.Then c^ay + c2a2+...+ ck ak = (cj Ui 4- c2 u2 4-...4- ckuk)b.
                                                                                     □
      The g.c.d. also has a kind of associative property.
Sec. 4.1]                   The Integers and Divisibility                     167
EXERCISES
Level 1
 1. Prove Property Zll. Add —a to both sides.
 2. Prove Property Z8. Note that a 4- Oa = la + Oa = (1 + 0)a = la = a. Now
    add —a to both sides.
 3. Prove Property Z2. Note that ab + (—a)b = (a + (—a))b = Ob — 0 by
    Exercise 2. Now add —(ab) to both sides. The relation a(—b) = —ab
    follows by the commutative law.
 4. Prove Property Z6 from Exercise 2 and Property Z2.
 5. Prove Property Z9 from Definition 4.1.3, adding (—a) to both sides.
 6. Prove Property Z10 from Definition 4.1.3, adding (—a) to both sides.
Level 2
 1. Prove Properties Z13, Z14 by considering each of three cases, a is positive,
    negative, or zero.
 2. Prove Property Z20 in that way.
 3. Prove Property Z3 using 0 = 00 = (1 + (—1)) (1 + (— 1)) = 1(1 + (—1)) +
      (-1(1 + (-1))) = 1 + (-1) + (-1) (1) + (-1)(—1) = 0 + (-1) + (—1)(—1)
      = —1 + (—1) (—1). Add 1 to both sides.
 4.   Prove Property Z7 using Properties Z2, Z3, Z10.
 5.   Prove Property Z18 using Properties Z5, Z7 and two cases: a positive or
      negative.
 6.   Prove Property Zl. Suppose 1 is negative.Then 1(1) = 1 < O.This contradicts
      Property Z18.
 7.   Prove Property Z4.
Level 3
  1. Prove Property Z6 using Properties Z9, Z10, Z2, Z3.
 2. Prove Property Z15 by taking five cases: a = 0 or b = 0, a> 0 and b > 0,
     a > 0 and b < 0, a < 0 and b > 0, a < 0 and b < 0.
168                                    Rings                                     [Ch. 4
3. Prove Property Z12 using any from Properties Zl-Zll and possibly
   Properties Z13-Z15.
4. Prove Property Z16 by taking five cases as in Exercise 2.
5. Prove Property Z17 from the induction axiom.
6. Prove Property Z19.
7. Show any ring R is a subring of a ring Ri with unit. Let Ri = Z © R
   and define (a, b) + (b, d) = (a + c, b + d). Define (a, b) (c, d) =
   (ac, ad+ be + bd). Show R is a subring of R1; and Rx is a ring. What is
   the unit?
8. Which of the listed properties of Z hold for all integral domains?
      We remark that from (i) it follows that v(a) > v(l) for all a.
Sec. 4.2]              Euclidean Domains and Factorization                      169
EXAMPLE 4.2.4. Let V be F[x] and let v(a) be the degree of the polynomial a.
EXAMPLE 4.2.5. Let V be {a + by/—I: a,b & Z) and let v(x) = \x\2 = a2 + b2.
Proof. First find a g.c.d. gy of ay, a2. Then let g2 be a g.c.d. of gy, a3. Find
S3, g*> ••• » Sk-\ bi similar fashion, always using Theorem 4.2.1. Then let
g =gk_y. We will have g\a( for i = 1 to k and g = ayXy + a2x2 + ... + akxk.
This implies g is a g.c.d. of Xy, x2,..., xk.                            □
     Since we can multiply both sides of g —      ayXy-V    a2x2 + ... + akxk by any
unit, any g.c.d. can be expressed in this form.
Proof. Let a be a unit. Then v(ab) > v{b). And v{b) = v^ab) > v(ab). So
v(ab)=v(b). Suppose v(ab) = v(b). Then b=qab + r for some q,rEE
where r = 0 or v{r) < v(ab) = v(b) where v(x) denotes the degree of x.
Suppose r=h 0. Then r = b( 1 — qa). So v(r) > v(h). This is false. So r = 0. So
b = qab. So qa = 1. So a is invertible.                                           □
Proof Let a be an element of minimum degree for which this assertion fails.
Suppose v(a) = v(l). Then since v(al) = v(l), a is a unit by Proposition 4.2.3.
This is contrary to hypothesis. So v(a)>v(l). Since a is not prime, a — be
where neither b nor c is a unit. If v{a) = v(b) then c would be a unit, by
Proposition 4.2.3. So v(b) < v(a). Likewise v(c) < v(a). But the proposition is
true for all elements of degree less than a. So b and c are products of primes.
So a = be is a product of primes. This completes the proof.                  □
     In most cases it is fairly clear that the last result holds. It is less obvious,
however, that a factorization into primes is unique except for rearrangement of
the primes and multiplication of each prime by a unit.
     We first note that it follows by induction from Proposition 4.2.4, that if p
is prime and p|aja2 ... ak then p\at for some i. That is, p\ax or p\a2a3 ... ak.
If p|a2a3 ... ak, then p|a2 or p|a3a4 ... ak. And so on.
     This theorem also holds for certain non-Euclidean rings. It is known that
polynomials in several variables do not form a Euclidean ring, yet unique
factorization still is true.
     In any Euclidean domain, there is an effective method: (i) to find the g.c.d.
g of two nonzero elements a, b and (ii) to express g as ax + by. Label a, b so
that v{a)>v(b). Let Xj = a, x2 = b. Obtain x,-+1by setting xi_l = qixi + xi+x.
Then v(x/+1) <v(xf) unless xl+1 = 0. So eventually some xt is zero. The last
nonzero element is taken as the g.c.d. g. This procedure is called the Euclidean
Algorithm.
Sec. 4.2]             Euclidean Domains and Factorization                      171
Proof. Let g = xt. Then xt_x = qiXt. We prove by a backwards induction that
for each /, g\Xj, g\Xj_x, and g is a linear combination of Xj, Xj_v For /' = i this
is immediate. Assume g\x/, g\x/_h and g = rxj + sxj_1. We have
X]_2 = Ql-lXf-i + Xj
EXAMPLE 4.2.7. Find (31, 47). Find x and y such that (31, 47) = 3lx + 47^.
Divide and take remainders.
            47 = 1 • 31 + 16
            31 = 1-16 + 15
16 = 1-15 + 1
15 = 15-1 + 0
The last nonzero remainder, 1 is the g.c.d. To find the linear combination, solve
the equations for the remainders
47-1-31 = 16
31-1-16 = 15
16—1*15 = 1
Divide polynomials: -x + -
              2x2 — 3x + L) x3 +       0 + 0 — 1
                             x3 — |x2 + \x
                                   fx2 + \ x — 1
                                   3    2_9         +3
                                   2X      4   ■*   '   4
172                                    Rings                               [Ch.4
We may write \{x — 1) and use (x — 1) as a divisor in the next stage since \ is a
unit when we are dealing with polynomials
                           2x -1
             * - 1 j’2x2 - 3x 4- 1
                    2x2 — 2x
                         —   x   + i
                         —   X +   1
                                   0
The g.c.d. is (x — 1).
EXERCISES
Level 1
 1.   Factor 192 as a product of primes.
 2.   Find (36, 54).
 3.   Find the g.c.d. of 501, 111 by the Euclidean Algorithm.
 4.   Find integers x, y such that 4x + ly — 1.
 5.   Find the g.c.d. of 700,133.
 6. Find the g.c.d. of x3 — 4x + 1 and its derivative.
Level 2
 1. Find numbers x, y such that I7x + lly = 1.
 2. Find numbers x, y, z such that 6x + 15>» + lOz = 1. (First find numbers
    such that 6r + 15s=3. Then find numbers such that 3x + lOz = 1.)
 3. Find polynomials f(x),g(x) such that /(x)(x2 + l)+g-(x)(x2 + x + 1) = 1.
 4. If ar + bs = 1 (so a, b are relatively prime) show that a(r + mb) +
    b(s — ma) = 1.
 5. Show that Exercise 4 yields all solutions of ax + by = 1.
Level 3
 1. Prove from the properties given in Section 4.1 that Z is a Euclidean domain,
    i.e. prove that for any x ^ 0, y =£ 0 there exist q, r with x = qy + r and
    | r | < |x |. Take r to be a number x — qy of minimum absolute value.
 2. Prove that the set of integers {a + bi: a, b E Z} is a Euclidean domain.
 3. Factor 1 + 3i into primes in this ring. (Try factoring a2 + b2 = |z|2.)
 4. Show unique factorization into primes fails in the subring of Q[x] generated
    by l,(x - 1)2,(* - l)3.
 5. Although unique factorization into primes holds in the ring of polynomials
    in 2 variables over C, show that this is not a Euclidean domain. To do this
    show that a g.c.d. of x, y is 1, yet there do not exist /(x), g(x) such that
    /(x)x + g(x)y = 1.
Sec. 4.3]                    Ideals and Congruences                           173
EXAMPLE 4.3.2. For any ring R and finite set of elements ax, a2,..., an E R
the set Ra! + Ra2 + ... + Ran = {r!ai + r2a2 + ... + rnan: r/E Rj is a left
ideal called the left ideal generated by a1( a2,..., an.
PROPOSITION 4.3.1. For any two ideals l, J both either right, left, or
two-sided, the following are ideals of the same type:
     (1) Z + J = [x + y: x E l, y E J}
     (2) IJ = {xxyx + x2y2 + ... + xnyn : n E Z,XiEl,y{E J}
     (3) in J
For any set S the intersection of all ideals containing S is an ideal {the ideal
generated by S).
Proof. We verify (1), (2), (3) for left ideals. First the additive property (1)
ax + bx + a2 + b2 = Oi + a2) + {bx + b2), (2) {xxyx + x2y2 + ... + xnyn) +
{rxsx + r2 s2 + ... 4- rksk) is again a sum of this type, (3) a + bEl and
a + b E J so a + b E l n J. For the multiplicative property (1) c{x +        =
ex + cy E l + J, {2)c{x1y1 + x2y2 + ... + xnyn) = {cxx)yx + {cx2)y2 + ... +
{cxn)yn, (3) ca E l and ca E J so ca E l n J.
     The remainder of the proof including the verification that —a is in the
ideal, is similar.                                                              □
     In every ring R there are two ideals, {0} and R. Since a + {—a) = 0, 0 is in
every ideal.
      All congruences of rings arise in the way given in the next result.
      If x ~ y and z ~ w then xJrz~x + w~y + w and xz ~ xw ~ yw.
PROPOSITION 4.3.3. The classes 0,1, 2,..., m — 1 are distinct and include all
congruence classes modulo m.
               5
             51T
               5_
               0
Sec. 4.3]                       Ideals and Congruences                       175
and 2 3 = 6 = 1 since
                 1
              5W
                 5_
                 1
      The proof of the following result follows the same pattern as for groups
(it is not given in full).
EXERCISES
Level 1
 1.   Work out the mod 5 addition table.
 2.   Work out the mod 5 multiplication table.
 3.   Work out the addition and multiplication mod 7.
 4.   Work out the tables for Z13.
 5.   Find x such that 4x = 2(mod 7).
Level 2
 1.   For any congruence x ~ y on a ring show the set {x : x ~ 0} is an ideal.
 2.   Show the kernel {x : /(x) = 0} of any ring homomorphism is an ideal.
 3.   Show that a field F has no ideals except {0} and F.
 4.   Prove the addition table of Zm has exactly one copy of each element in
      each row and column. Excluding the row and column of zero, when will
      this hold for multiplication?
 5. Define a ring structure on a Cartesian product Ri X R2 of two rings. Show
    that if both have units there must exist ideals of R, X R2 other than
    {0}, Ri X R2.
 6. Prove that the last statement of Proposition 4.3.1 agrees with the previous
      idea of left ideal generated by a set.
176                                     Rings                                 [Ch.4
Level 3
 1. Show any congruence on R is determined by a unique ideal.
 2. Prove any ideal in a Euclidean domain E is of the form Rx for some element
      x E R. Such ideals are called principal.
 3. Prove that the family of ideals of R is a lattice under inclusion.
 4. Prove that any integral domain V is a subring of a F. Define F by taking
    ordered pairs (a, b) from R interpreted as fractions a/b. On these ordered
    pairs take a congruence (a, b) ~ (c, d) if ad = be and use the usual
    definition for sums and products of fractions.
 5. Let I =£ {0}, I =£ R, and I is maximal under inclusions among proper ideals of
    R. Prove R/I is a field.
 6. Prove that if R/I is a field, then I cannot be contained in another proper
      ideal J.
    In any ring the set of elements having inverses is a group since we can take
(x-1)-1 = x and (xjv)-1 =          Thus the set of invertible elements of Zm
forms a group.
Proof. The order of any element of a group divides the order of the group.         □
Sec. 4.4]                          Structure of Zn                          177
COROLLARY 4.4.6. For any prime p there exists an element a such that
a, a2,, ap~l ranges over all nonzero elements of Zp.
Proof. If x — b2 then
             p-t
            x 2 = bp~l = l(mod p)
             x = (J)2                                                          □
178                                  Rings                                [Ch. 4
EXERCISES
Level 1
 1. A test for primeness of a number/? is to check whether xp_1 = l(mod p).
    (It is not always sufficient but for p large gives strong evidence.) Try this
    for x = 2, p = 1 to 10.
 2. When does ax — Z?(mod m) have a solution x?
 3. Find a multiplicative inverse of 5, mod 13.
 4. If x, y are quadratic residues modulo m, prove xy is also a quadratic residue
    modulo m.
 5. How many quadratic residues exist modulo 3? 5? Try to generalize to any p.
 6. Do you think a product of two quadratic nonresidues must be a quadratic
    residue, modulo a prime? Compute a number of examples.
 7. Prove x2 = l(mod 8) for any odd x by checking all cases.
Level 2
 1. In any field, show by Theorem 4.4.5 that ±1 are the only solutions of
    x2 — \ .                              p-l
 2. Show from Exercise 1 that for any x, x 2 = ±1.
 3. Prove Wilson’s Theorem that (/? — 1)! = (—l)p(mod p) for any prime p.
    All numbers 1, 2,...,/?— 1 are solutions of xp~1 — 1. Hence (x — 1) (x — 2)
    ... (x — p + 1) divides xp_1—1. Hence xp_1 — 1 = k(x — 1) (x — 2) ...
    (x — p + 1). By considering the xp_1term, k = 1.
 4. Show that if p divides x2 + y2 and p does not divide                y then
    p = l(mod 4), using Corollary 4.4.8.
 5. When does the equation x2 + ax + b = 0(mod p) have a root jc, for odd
    primes pi
 6. Prove x2 + y2 + z2 cannot be congruent to 7(mod 8), by considering cases.
  7. Let the Legendre symbol (xly) be ±1 accordingly, as x is or is not a
     quadratic residue of y. Prove
                       y-1
(x | y) = x 2 (mod y)
      for y prime.
Sec. 4.5]                 Simple and Semisimple Rings                           179
Level 3
 1. Show that if f(x) and #(x) are polynomials of degree <p in a variable x
    over Zp and f(k) = g{k) for k = 0,1, 2,..., p — 1 then f(x) = #(jc). Since
    kp = k, this is false for degree p.
 2. Prove for m, r relatively prime Zmr — Zm© Zr. Map Zmr-> Zm and Zmr-+ Zr
    by the map sending k to k. This is a homomorphism because ZmrC Zm and
    Zmr C Zr. Show the kernel of this map is zero (this proves isomorphism).
 3. Extend Exercise 2 to k factors.
 4. Prove the 1 Chinese Remainder Theorem ’. If xt = c{ (mod mf) are a set
    of congruences, they have a simultaneous solution if and only if for all
    i, j, ct = Cj (mod <i) where d = g.c.d. (mit m{).
 5. Prove                                                   ,        .
            ‘M.pf'Pi"2 - P*nk) = p"‘pi"2 ■■■ Pk"k0 -^)(l -^ ...
                 ... (l —t-)
DEFINITION 4.5.2. A ring R with unit is a division ring, if and only if every
nonzero element has a multiplicative inverse, and is sometimes denoted Rp.
    Over general fields there exist many complicated division algebras. However,
we will show next that over C, the only finite dimensional Rp is C itself.
EXAMPLE 4.5.10. The ring of lower triangular matrices over F has a nilpotent
ideal (those with zeros on the main diagonal) and so it is not regular.
             (1-2 ctf)R*0.
                i=1
Let l\i+j be a minimal right ideal in this ring. Write         = wl^+j where w is
an idempotent in I^+|. Thus enw = 0 for i = 1 to k. Let
            x = w(l - 2 eu)
                     i=1
      The rings eff Rew will be the required division rings. We show that etiReit is a
division ring. It is a subring with identity eit. Suppose it is not a division ring.
If y =£ 0 is not invertible in it then y eit R ez7 ezzRezz-. Therefore y ei{ R ezz R.
This contradicts the fact that ez7 R was a minimal right ideal. Therefore e/z-Rez7 is
a division ring Rp..
                   A,
     Next we observe that ey/Re« =£ 0. Since R is simple, R = ReieR. Thus
ejj — 2 akenbk. So 2         akenbk      0. This implies e7/afce,7- ^ 0 for some A:.
     Choose for i = 2 to n a nonzero element en6ze/z- and write it as              We
have        = elzez7 = elz-. Also elz-R C en R so elzR = enR by minimality. There
exists therefore y( such that elzyz- = en. Set eix = e^^e^.Then euen — eixen =
en> euen=eu(.eiiyien)=euyien=en. Therefore (euen)2 = eu, so eneu # 0.
Moreover (enelz)2 = ezlelz- is a nonzerh idempotent in Rp.. So ezlelz- = eu.
      Now set e,y = ezle1;-, which is consistent with the previous definitions.
We have eijSjk ^n^ij^ji^ik                k   ^n^ik ~~ ^ik• And for j ^ r, eXj£rs —
eijejjerrers = 0. Therefore ef/- have precisely the properties required to be the
0,1)-matrices whose only 1 entry is in location i, j.
     All the division rings Rp. are isomorphic to Rp. by the mapping y -*■ euyen.
                              A,                      I
And in fact eti Re/;- is isomorphic as a vector space to Rp. under the mapping
x -* euxejX which has an inverse x -* e(ixe1 j.
     It readily follows that we have a homomorphism from the ring of matrices
D = (dij) over Rp^ into R sending (dy) to 2 endijelj.
    This has kernel zero since if we multiply by e(i and e;/- on left and right only
the term in dtj will remain. It is onto since x = l(x)l = (2 ez7) (x) (2 ez7) and
eiiRejj^Rpr                                                                       □
      This result is also valid for rings which are not F- algebras but are such that
there does not exist an infinite descending family lj D        D     D ... of distinct
left ideals (Artinian rings).
      The converse is left as an exercise.
EXERCISES
Level 1
  1. Show that the quaternions are a division ring.
  2. Consider the ring of rational functions
              Qi(x)
              Q2 O)
     over C where x is a variable. Show this is a field.
  3. Show it is an infinite dimensional division ring over C.
  4. If z is in the center of R, prove z R is a two-sided ideal.
Sec. 4.5]                 Simple and Semisimple Rings                          183
Level 2
 1. In the ring of Mn(F):
     (a) Show all left ideals are principal (have the form Ra).
    (b) Classify left ideals in terms of the image space of a matrix on row
         vectors.
     (c) Classify right ideals.
     (d) Show no two-sided ideals exist.
Level 3
 1. Carry through Level 2 for matrices over R-p.
 2. Prove that a finite dimensional integral domain of F is a division ring.
 3. If u is an element of a finite dimensional F-algebra A, prove that there exists
    a polynomial in u such that p(u)uk = uk for some k. Assume uR = u2R.
    By induction show ukR = uR. Show p(u)u = u,p(u) is idempotent, and
    generates uR.
CHAPTER 5
Group representations
ring F(G) regarded as a module over itself. Therefore to obtain all irreducible
representations it suffices to find all irreducible submodules of the group ring.
     Then we introduce characters, the traces of the matrices of a representation.
The characters of distinct irreducible complex representations turn out to be
orthonormal vectors. This is a consequence of the fact that there exists no
nonzero homomorphism from one irreducible module to another unless the two
are isomorphic.
     It follows that every equivalence class of complex representations is
completely determined by its character. Characters can be added and multiplied,
and have a number of other properties.
     Group representations are important in the study of systems having
symmetry, for instance in physics. Frequently such systems can be decomposed
in terms of the distinct irreducible representations of the system.
     In the last section we discuss tensor products M ® W of the modules. These
are constructed by generators and relations expressing bilinearity. They explain
the properties of Kronecker products of matrices, and enable new representa¬
tions of a group to be found. Under some unproved assumptions, we find the
character ring of the n-dimensional unitary group.
DEFINITION 5.1.1. For a group G and ring R the group ring R(G) is the set of
all functions f:G~>R which are zero on all but a finite number of elements
of G. Such functions are added by the usual functional addition,
             (fOh)(x) =       2 f(y)h(z)
                             yz=x
Two such sums are added and multiplied like algebraic expressions in which the
gj are treated as variables and the rt are treated as coefficients. The coefficient
rt of gi is interpreted as f(gt) where / is the function described in the definition.
However, unless x, y commute in G, xy must be distinguished from yx in
multiplication.
    The description in terms of formal sums is equivalent to the description by
functions: to the sum 2 r{g{ corresponds the function / such that f(g{) = rt and
 186                               Group Representations                                   [Ch.5
f(x) = 0 for other elements of g and conversely. Let sums 2 r/gj and 2 Sjgj
correspond to functions f g. Then (2 r{-£,-)(2 Sjgj) is the sum 2 tkgk where
             h =      2        rtSf.
                   g{ij “ gk
             Kgk) =       2        f(gdg(gj)
                       SiSj=gk
This is the product of Definition 5.1.1.
EXAMPLE 5.1.1. Let G be the symmetric group of degree 3, with six elements
e, y, y2, x, xy, xy2 where y3 — e, x2 = e, xy = y2x. In R(G),
= 6e + 3y + 3xy — 8x — 4 xy2 — 4 y2
Proof. We prove one of the distributive laws and the associative law of
multiplication.
                                       =     2 f(y)r(z)+     2     f(y)s(z)
                                           yz = x           yz-x
Therefore
             fO(r + s) = (/ O r) + (/ O h)
It follows that
                               =       2     f(y)r(u)s(v)
                                   yuv-x
                           =           2     f(y)r(u)s(v)
                                   y uv-x
                      2uj
                cos
                      m
                                   2nj
                             cos
                                   m
EXAMPLE 5.1.4. Any regular solid in 3-dimensional space has a finite group
of symmetries G. Then G has a 3-dimensional representation as the matrices of
the rotations and reflections involved. This gives, for example, a 3-dimensional
representation of the alternating group of degree 5 by rotations of an
icosahedron.
               2 r(g)x • r(g)y
            g^G
188                                 Group Representations                    [Ch. 5
Then
Here, since G is a group, gh ranges over all elements of G if g does. This shows
/ is invariant.
     We show that f(x, y) is what is called a nonsingular bilinear Hermitian
form. We have
f(x,y) = f(y,x)
               = f(x> 2) + /O, z)
  f(ax, z) = 2 r(»ax • g(z) = a/(x, z)
These imply /(z, x + y) = f(z, x) + f(z, y) and f(x, az)= a* f(x, z).
    In addition
             fix, x) =          2   r{g)x • r(g)x > 0
                            g&G
for all x^O.
                    V/Ol, Ml)
so Vi • v1 = 1. For / = 1 to n, let
            w/ =       - 2 /(«,, zn) v-
                            j<i
Then (w,- • vj) = 0 for / < i. Let
                    V/(w/, W/)
Then y,- is the required basis.
    Now we claim that with respect to this new basis, the matrix X of r(h) will
be unitary. Let r(h)Vi = 2 xi}-vf. Then by invariance f(vt, vk) = 8ik = f(r(h)Vi,
r{h)vk) where 8ik = 1 if i = k and 8ik = 0 if i =£ k. This gives
EXERCISES
Level 1
 1. Compute in the group ring of the symmetric group of degree 3 over Z:
     (a) (2e + 6x + 5^ + ly2) + (2e 4- 10x + xy +- xy2)
    (b) (e + y + y2)(y)
     (c) (e + y + y2)(x)
    (d) (e + y + y2) (2x + 3^)
 2. Define a representation of Z2 X Z2 into 2X2 diagonal matrices over Z.
    Generalize this.
 3. Define a representation of the symmetric group into nXn permutation
    matrices over Z.
Level 2
 1. Prove that in a group ring F(G) there always exist nonzero elements which
    have no inverses, if \G \ > 1.
 2. Show Q(Z2) is isomorphic to Q ® Q.
 3. What are the nonzero ideals of Q(Z2)?
 4. Show that
                  1     0
           m
                  m     1
                     "o           f               " o    f
            X   -*                    ,   y -*■
                     .1           0                T    -\_
Level 3
 1. Consider the rational group ring Q(Zm). Define homomorphisms
    &:Q(Zm)-*Q by h(x) = 1, x G Zm and Q(Zm)-*F where F is the
    subfield of C generated by
                          2 tri
190                             Group Representations                      [Ch. 5
'h(x) 0 -
0 h* (x)_
EXAMPLE 5.2.5. Any vector space is a unitary module over the field in
question.
EXAMPLE 5.2.6. Any two vector spaces of the same dimension are isomorphic
F-modules.
   Right modules could have been used in Theorem 5.2.1 since to every left
module over F(G) there corresponds a right module with multiplication given by
m (2 aigi) = 2 aigi'm.
192                         Group Representations                       [Ch.5
DEFINITION 5.2.5. The direct sum of the left (right) R-modules Mi, M2, , Mn
is the Cartesian product Mi®M2®---®M^ with operations defined by
(*1, x2, ... , xn) + (yu y2, ... , yn) = (xi + yu x2 + y-i< •••. xn + yn) and
c(xhx2,... ,xn) = (cx1, cx2,..., cxn) (respectively (x1; x2,..., x„)c = (xqc,
x2c,..., xnc).
EXAMPLE 5.2.7. For vector spaces this is the same as the previous definition
of direct sum.
THEOREM 5.2.2. Let G be a finite group and let F be C or R. For every sub-
module N of a finite dimensional F(G) -module M there exists a complementary
submodule J such that M — W ® T. Moreover N/M — T.
    Theorem 5.2.2 is actually true for any field F such that (char (F), |G|) = 1.
A proof is given in the exercises (see Level 3, Exercises 2-5).
EXERCISES
Level 1
 1. Explain why every commutative group is a Z-module.
 2. If / is a homomorphism from a ring R to a ring S explain how S can be
    regarded as an R-module.
 3. Prove that Z is not a unitary Q-module.
 4. Prove that the set of ^-dimensional vectors over F is a bimodule over the
    ring Mn(F).
 5. For a G R, prove that aM is a submodule of M provided a commutes with
    all elements of R.
Level 2
 1. Suppose a group G acts by permutations on a set X. Find a Z-module
    associated with this action. (It can be taken as the set of functions X -> Z.)
 2. Prove that if M is a module over R, every invertible element of the centre
    of R, {x : xy = yx for all y G R} gives a module isomorphism M "*■ M.
 3. Let Mn be the direct sum of n copies of an R-module M. Prove              is a
    module over the ring of n X n matrices over R.
 4. Show that the subgroup of Z X Z generated by {(1,1), (2, 3)} is itself a free
    Z-module.
194                          Group Representations                         [Ch.5
 5. Do the same for the subgroup generated by {(1,4), (2, 2), (4,1)}.
 6. Prove that every abelian group of order m is a Zm-rnodule.
Level 3
 1. An integral domain V is called a principal ideal domain if and only if every
    ideal has the form V(a) for a G V. Prove every finitely generated module
    over a principal ideal domain is isomorphic to a direct sum of modules of
    the form V/V(a).
 2. If Zr <t F for rllGI every F(G)-submodule hi of an F(G)-module M is a
    direct summand. Let V C M be a vector space complement of hi in M, and
    let h : M -► V be a projection mapping onto V with kernel hi. Let
           hi(x) = ~ Zgh(g-\x))
                   IGI G
    Prove hi is a module homomorphism from M to M. The property Zr <£ F
    guarantees |G| has an inverse in F.
 3. Let hi and hi be the same as in the above exercise. Prove hi C ker (hi).
 4. Prove that the mapping V -*■ M1*1 -*■ M  M /hi — V is the identity.
 5. Prove image of hi is a complement of hi.
THEOREM 5.3.1. Every irreducible module        M over a ring R has the form R/K
where K is a maximal proper left ideal.
’* o’
             *    *
Sec.5.3]                          Irreducible Representations                  195
            "l     o'
                   1_
1_
                        9
             'o
                                    o
                            1
Proof. Without going into detail, each matrix algebra Mn(C) of n X n matrices
over C yields precisely n copies of a single irreducible representation, corres¬
ponding to the n columns of each matrix. Distinct matrix algebras give distinct
representations. The representation of Mn(C) on the set of column vectors can
be verified to be irreducible.                                                □
Proof. We show the module V of row vectors over Mn{C) has this property.
Here Mn(C) denotes the n X n matrices over C. Let /: V -* V be an
isomorphism such that f(Av)= Af(y) for every v. Let A be a (0, l)-matrix
with exactly one 1 in the (/, z')-entry. Let et be the (0,1)-vector having exactly
one 1, in place i. Then Af(v) = f(A(y)) = f(vt et) = vif(ei). Therefore the i
component of f(v) which is that of A f(v) is v{           So / is a diagonal matrix
D with entries         Let A have a,y = ay = 1 and all other entries zero. Then
AD = DA implies dti = djj by looking at the (/, /)-entry of each.                □
EXERCISES
Level 1
 1. If the group is commutative show the group ring is also.
 2. For a commutative group if C(G) is isomorphic to a direct sum of Mn(C)
    explain why no n can exceed 1. Therefore all irreducible representations are
    1-dimensional.
 3. Show that n distinct irreducible representations of Zn are obtained by
                             2 it ik
    sending a generator 1 to —-—. Therefore these are precisely the irreducible
    representations of Zn.
 4. For any irreducible representation of a group H into Mn(C) and for
    any homomorphism f:G-+H which is onto prove the representation
    /: G -*■ Mn(C) is irreducible.
 5. Use Exercise 4 to obtain p2 irreducible representations of Zp X Zp.
Level 2
 1. How many times does the regular representation contain the trivial
    representation?
 2. Identify the trivial representation as a submodule of Zn.
 3. For the symmetric group give         a linear representation of the form
    Sn^Z2->Mn(C).
Sec. 5.4]                       Group Characters                             197
Level 3
 1. Generalize Level 2 to obtain all irreducible representations of the dihedral
    group of order 2n, n odd. (They are all 1 or 2-dimensional.) Note that if
    the group is written in terms of generators and relations x, y: x2 = yn = e,
    xy = y-1x that there is a quotient map on to Z2 sending y to e where e
    is an identity and there are automorphisms y -> yk for any relatively prime
    to n. These with symmetries of a regular «-gon give the irreducible
    representations.
 2. Give the irreducible representations of the dihedral group for n even. (There
    are additional 1-dimensional representations sending y2 -*■ e but not y.)
                  "l    0*           0    f
            e =              , x =
                  0     1_           .1   0_
Proof. For a direct sum of representations rlt r2 the matrices look like this:
            >iU)      o
            - 0     r2(g)_
      The trace of such a matrix, the sum of the main diagonal entries, is
Tr (rite))+ Tr (/•,(*)).                                                         □
    In the following proof we use the fact that if r, s are representations, and
Y is a matrix such that         = Ks(g) then v -* Yv gives a module homo¬
morphism / between the corresponding modules. The reason is that f(r(g)v) —
Yr(g)v = s(g)Yv = s(g)f(v).
            Y = 2 r(g)Bs(g~1)
satisfies
            r(h)Y - Xr^Bsig-1)
= 2 r(hg)Bs((hg)~1)s(h)
= Ys(h)
For r, s distinct it must be zero by Lemma 5.3.2. Let r = s. Then all such
homomorphisms Y must be a multiple of the identity al, by Proposition 5.3.6.
     Let B be a (0, 1)-matrix with a 1 precisely in its (/, k)-entry. Then the
sum in question is the (z, ra)-entry of Y. This proves the first statement. Also
if z =£ m the sum is 0 since Y = al, and for z = m is independent of m. But
2 rij(.g)rkm(g~l) - 2 rii(g~1)rkm(g) if we let the sum run over g~l instead
of g. Therefore the sum for ij, km is the same as for km, ij. Therefore if / =£ k
it is zero, and all the nonzero sums are equal to some number a. They can be
evaluated by taking B — I, in which case Y = \ G\I. So nal = \G\I since taking
B — I means we add n equal sums for / = 1,2,..., n.                                   □
— 2 XiC^XaU"1) = — 2 Xi(g)X2(g*)
COROLLARY 5.4.4. If Xi. X2 are irreducible then (Xi, X2) = 0 if Xi- X2 are
not equivalent, and (xi, X2) — lif Xi. X2 are equivalent.
COROLLARY 5.4.5. For any representation           x,   the value (x, x)   is lif and only
if x is irreducible.
by Theorem 5.4.3. This is 1 if and only if there is only one nonzero nt and
it is 1.                                                                               E
      Most of these results go through for compact continuous groups, if the sums
are replaced by integrals.
     There are many other relationships involving characters, some sketched in
the exercises.
EXERCISES
Level 1
 1. Prove that the number of times the trivial representation occurs in a
    representation with character x is
Level 2
 1. Write the characters of the dihedral group of order 2n, n odd.
 2. Verify the orthogonality relations for this group.
 3. For an irreducible representation of degree 2 of the symmetric group of
    degree 3, what is x ® X? What irreducible representations make up the
    Kronecker product of this representation with itself?
 4. Let Ck be 2 g over the fcth conjugate class nk. Prove that Q Cy is a sum of
    elements Ck with integer coefficients, Q Cy = 2 nijk Ck for some integers
     nijk •
  5. In an irreducible representation Ck being in the center, must go to a certain
     multiple of the identity al. Let xk E nk and let the dimension be n and let
     l^fcl — hk- Then Tr (Ck) = hk\(xk) = na. What is then the image of Cfc?
  6. Let
                    fytxOfc)
             yk =
                        n
     We have from previous results y{yj = 2 n(jkyk. So each y{ satisfies a monic
     polynomial with integer coefficients, the characteristic polynomial of (a,y)
     where ajk = n.ijk. Such numbers are called algebraic integers.
  7. Show a basis for the center of C(G) is given by the sums Ck since elements
     in the same class must have the same coefficient. The center, as a ring, is
     a direct sum of copies of the complex numbers, one for each irreducible
     representation. Therefore the number of distinct irreducible representations
     is what?
Sec. 5.5]                       Tensor Products                             201
Level 3
 1. Try to prove the class orthogonality relations
             1                       1 for g conjugate to h
            — ?X/(*)X/W =
            |Cr I *                  0 otherwise
    where the sum is taken over all irreducible representations.
 2. Assuming sums and products of algebraic integers are algebraic integers and
    the results of Exercise 7 of Level 2 and the orthogonality relations of the
    above exercise, prove the degree of an irreducible representation divides
    the order of the group.
hx = identity
such that fhi = b. This contradicts'uniqueness. Thus the bt are onto. Thus
gxg2 and g2 gi are the identity. So each is an isomorphism.             □
(1) xr ® z = x® rz
(2) (x + y) ® z = x ® y + y ® z
(3) x ® (z + w) = x ® z + x ® w
The group with these generators and relations can be verified to be the tensor
product by the same sort of proof as was presented for semigroups.
    Tensor products have many properties.
Tl. R ®      M - M.
T2.   (M © N) ® G = (M ® G) e (N ® G).
T3. If M is a bimodule, M ® SI is a left module.
                             R
T4. (M ® N) ® G — M ® (M ® G), if these are defined.
         R      R        R       R
Therfe are dual properties where left, right factors are interchanged.
    In group representation theory, the tensor product is taken usually not over
F(G) but over F only, that is, it is a tensor product of vector spaces.
THEOREM 5.5.2. Let vx, v2, ..., vn be a basis for a vector space V and
wx, w2,... ,wn be a basis for vector space W. Then vt ® w;- is a basis for V ® W
where i, j = 1, 2,..., n.
Sec. 5.5]                            Tensor Products                                203
= g(z ® x + z ® 7)
               F(G)    ® M
                      F(H)
ring.
        Another method is especially important for representations of compact
continuous groups. Let V be a complex representation of any group G. Then
Vn = V ® V ® ... ® V is a G-module. However, it is also a module over the
symmetric group acting by permutation of the factors: 7r(Xi ® x2 ® ... ® x„) =
x^t,. ® X(2)jr ®...® X(„)w. Moreover these two actions commute: gn(x1 ® x2 ®
204                           Group Representations                            [Ch. 5
... ® x„) = gx(1)n ® £x(2)7r ® ... ® gx(„)7r = n(gxx ® £x2 ® ... ® gxn) =
ng(xi ® x2 ® ... ® x„). The G-module Vn decomposes as a direct sum according
to the different irreducible representations of the symmetric group 5^.
     One way to see this is to recall that corresponding to each irreducible
representation there will be a central idempotent e( in C(Sn), and any C(5^)-
module M is the direct sum of efM. Since et is a sum of permutations 7r it will
commute with any element G. Therefore ^(e/M) = e,-#M C e,-M so e/M is a
submodule over G.
   In general we can get many representations of any group from the tensor
powers M” of any 1-1 representation. The exterior powers are especially
important.
where o(n) is the sign of n. The kth symmetric power sfc(M) is given by fkMk
where fk is the idempotent
             1
            —    2rr
            n!
EXAMPLE 5.5.5. For k — \, sx(M) is M. For k = 2, X2(M), s2(M) are in the
preceding example.
PROPOSITION 5.5.3. Let vx, v2,..., vn be a basis for M. Then a basis for
Xfe(M) is given by Ai>/2A...A Vfk such that ix< i2< ...< ik.
Proof We have from the definition 7t(xj A x2 A ... A xfc) = o(ir) (xx A x2 A ...
A xk). The vXl A V/2 A ... A V\k for arbitrary iu i2,..., ik form a spanning set
Sec. 5.5]                         Tensor Products                                205
for Afc(M) since Afc(M) = e^ and vXl ® Vj2 ® ...®Vik form a basis for the
tensor product. By applying a permutation n we may assume zx< i2< ... < ik,
and 7r will at most alter the sign of the result. If Vj = Vjg then let ir E Sn inter¬
change r, s. Then -n(vix Ad/2 A ... A vik) =      A v^A ..! A vik since ir = is but
n(vh AvhA...A vik) = o( it) (vh A          A ... A vik) = ~(vh A vh A ... A vifc).
So Vix A Vj2 A ... A V[k = — (Vix AVj2 A ... A        So it is zero. Therefore for
*1 < i2 < ... < ik we have a spanning set.
     The given terms are independent in Mfc since different ones involve distinct
basis elements vXl ® Vj2® ... ® i>,• .                                             □
EXAMPLE 5.5.6. A basis for A2(M) is given by vi AVj where i < j. We have
Vj A vt = —vt A Vj.
PROPOSITION 5.5.4. Let a matrix have eigenvalues ex, e2,..., en. Then the
linear transformation it induces on the kth exterior power has eigenvalues all
products eix e;2 ... eik, ix < i2 < ... < ik.
Proof. Choose a basis vx, v2,..., vk in which M is lower triangular with main
diagonal elements eh e2,... , en. Then               plus a linear combination of
Vj,f<i. On the exterior power it will send vXx A Vj2 A ... A Vjk to         e/2 ...
eik(vix A Vj2 A ... A Vik) to plus terms involving lower Vj. So it will be lower
triangular with eigenvalues e^e;2 ... ez-fc.                                    □
     We next apply these results to determine the character ring of Un, the n X n
unitary matrices, under some assumptions. Let Dln the diagonal matrices such
that \dti\ = 1 for i = 1 to n. Then D\ is commutative. Every element of Un is
similar to a matrix of D„, hence the characters take the same value. Therefore
any character is determined by its values on D„. The group Dln is £" where £x is
the group of complex numbers of absolute value 1.
     We have shown in an earlier exercise that every irreducible representa¬
tion of a finite commutative group is 1-dimensional. This result extends to
compact commutative groups (in effect we can simultaneously diagonalize the
matrices). Every 1-dimensional representation is equivalent to a unitary represen¬
tation, which is a homomorphism                Such representation are sums of
homomorphisms |x -> £x, which are of the form x -*■ xn. Let xt denote the homo¬
morphism            which takes (ax, a2,, an) to a(. Then all 1-dimensional
representations of Dxn are of the form xfZix^2... x™n for mt E Z.
                   2      x™1x™2...Xnnp(ml,m2,...,mn)
            mx,...,mn<a Z
EXAMPLE 5.5.8. The determinant d gives a representation Un -*■ U]. Its value
on Dxn is the product of the main diagonal entries. So it has character XiX2 ... xn.
Its complex conjugate has character (xx x2 ... xn )_1.
EXAMPLE 5.5.9. The fcth exterior power Xfc(M) has character.            2   . xXlx/2
... Xjk by the Proposition 5.5.4.                          ll               lk
THEOREM 5.5.5. Let R be a commutative ring with unit. Then any symmetric
polynomial in xx> x2,... ,xn with coefficients in R is a polynomial in ax, o2,...,
on with coefficients in R.
Proof. Let p(xx, x2, ..., x„) be any symmetric polynomial. For any product
T of powers of the x,- let 2 [T] denote the sum of all terms symmetric to T.
It suffices to show all the 2 [T] can be expressed as integer polynomials in
Ox, o2,...,on since every polynomial p(x) is a sum of expressions 2 [T] with
coefficients in R. If n = 1 or the degree of p(x) = 1 the theorem is true.
      Assume that this result is true for m<n and for m — n and expression
2 [T] of degree less than the degree of p(x). If T involves every variable, 2 [T]
is divisible by on — xxx2 ... xn. By induction we can express
2JT]
EXAMPLE 5.5.12. For G = Z2, the character ring is the ring of all sums
n(l, 1) + m( 1, —1) since (1, 1) and (1,-1) are the irreducible representations.
EXERCISES
In the following exercises  is the multiplicative group of complex numbers elx
of absolute value 1 and D„ is the group of n X n complex diagonal matrices
whose main diagonal entries have absolute value 1. Other notation is the same as
in the preceding text.
Level 1
 1. Express XiX2 + XiX3+x|xi + x|x3 + x3xj + x|x2 as a polynomial in
    oi, o2, o3. First study x\x2 + x2Xi.
208                          Group Representations                        [Ch. 5
 2. Tell why every element of the character ring of a compact group is a sum
      2 riiXi where n; G Z and \i are characters of irreducible representations.
      Show every member is a difference of the characters of two actual
    representations.
 3. The irreducible representations of   have the form e27ridn, n G Z where Q
    ranges from 0 to 2it. The orthogonality relations for the characters have the
      form
             fl"e27tiene-2iridmd9 =     q
Level 2
 1. What is the dimension of X*(77)?
 2. What is the character of s{(>/)?
 3. Corresponding to the three irreducible representations of S3 we have
    M ® M ® M — X2(M) + s2(M) + M3 for some M3. By subtraction find the
    dimension of M3 if M has dimension n. For the unitary group, find its
    character.
 4. The tensor product can be defined more precisely as follows. Let G be the
    set of all functions /: M X M -* Z, which are zero on all but a finite set of
    ordered pairs. Let H(g) be the subgroup generated by all functions of the
    form g(xr, z) - g(x, rz), g(x + y, z) - g(x, z) - g(y, z), g(x, z + w) -
    g(x, z) — g(w, z). Then the tensor product is the quotient G/H(g). Let h
    be the mapping M X W -> H(g) such that h(m, n) is 1 on (m, ri) and 0 on all
    other pairs. Prove h is bilinear.
 5. Let G' be an arbitrary abelian group and b any bilinear mapping
    M X M -* G'. Define r: G ->• G' by r(f) = 2 b(m, n)f(m, ri). Prove r is 0
    on H(g) and rh= b where M, N, G, H(g), h are the same as in Exercise 4.
 6. Prove r is unique in the above exercise.
 7. Show that the irreducible 2-dimensional representation of S3 is induced
    from a representation of Z3.
 8. Find a conjugation by a permutation matrix interchanging the first two
    factors of D\.
Sec. 5.5]                       Tensor Products                              209
Level 3
 1. Find a relation between Xn and the determinant of an n X n matrix.
 2. Prove a complex representation cannot be decomposed as a direct sum if
    there does not exist any matrix other than the identity which commutes
    with every matrix of the representation.
 3. Prove the representation \lrj of the unitary group is irreducible (How could
    its character be a sum of positive symmetric polynomials in the xt ?)
 4. Try to find a relation between characters of     and Fourier series (consider
    Exercise 3, Level 1).
 5. Prove from the definition that (M ® SI) ® T — (M ® T) ® (SI ® T) where
    M, SI, and T are modules.
 6. Describe an induced representation as a matrix.
 7. Prove that tensor products of modules correspond to Kronecker products of
    representations.
 8. Find the character ring of unitary matrices of determinant 1.
 9. Prove the ring Mn(C) is a semigroup ring (of matrices having at most one
    1 entry) but not a group ring for n prime. Use the fact that a group of order
     n2 is commutative if n is prime.
CHAPTER 6
Field theory
EXAMPLE 6.1.2. [C : R] = 2.
THEOREM 6.1.2. Let gix) be an irreducible monic polynomial over F, and let
F[x] denote the ring of polynomials in x with coefficients in F. Then
              F[*]
           £0)F[jc]
is a field E with basis 1, x, x2,..., jc”-1 over F and the minimum polynomial
of x in E is gix). If y is any element of any extension field satisfying giy) = 0
then there exists an isomorphism E -* F(y) sending x to y.
Sec. 6.1]                  Finite Dimensional Extensions                       213
                  gO)F[x]
Then E is a ring containing F. Any polynomial h(x) is equivalent in E to
a polynomial of degree < n = deg QK*)), since h(x) = g(x)g(x) + r(x)
so h(x) — r(x) E g-(x)F(x). Let h(x) be a nonzero polynomial of degree < n.
Since #(x) is irreducible (prime) there exist /*(x), s(x) such that r(x)h(x) +
g(x)s(x) = 1. So r(x)h(x) is equivalent to 1 in E. Therefore h(x) has a
multiplicative inverse. Therefore E is a field.
      Since any polynomial is equivalent to a polynomial of degree less than n,
the powers 1, x, x2,..., x"-1 are a spanning set. No polynomial of degree less
than n is divisible by^(x). Therefore they are independent.
      Since g(x) = 0 in E but no polynomial of lower degree is zero in E unless
it is zero in F[x], g(x) is the minimum polynomial of x.
      Let y be an element of Ex D F such that g(y) = 0. There exists a map
F[x] into F(>’) sending any polynomial p(x) to p(y). This map is a ring homo¬
morphism. By the previous theorem it is onto, since 1, y, y2,, yn~x form
a basis. It sends #(x) to g(y) — 0. So ^(x)F[x] is in its kernel. This gives a
mapping from
            E = gw
                  g(x)F[x]
onto F(>’). It is onto. Since both spaces have dimension n, it is an isomorphism.
                                                                                 □
    This result gives a method of constructing many finite dimensional
extensions of F. Take any irreducible polynomial p(x). Then
              FW
            P(x)F[x]
is a finite dimensional extension.
      Moreover every finite dimensional extension Ex can be obtained by repeat¬
ing this procedure. Let y E. E! but y & E. Then the subfield generated by y is
isomorphic to a field
               FW
            p(x)F[x]
Then an element of E1\F(>’) can be taken, and so on.
    To carry this out, some criteria for irreducibility of a polynomial are needed.
The following are some well-known facts:
1 X x2
                          1            X                     x2
                         X             x2            — 2x2 — 2x — 2
                         x2    — 2x2 — 2x — 2           2x2 + 2x 4- 4
     Inverses can be computed from the Euclidean algorithm, finding r(x), s(x)
such that r(x)p(x) + s(x)/(x) = 1.
     For instance, if we want to find the inverse of x2 4- x + 1, divide it into
x3 + 2x2 4- 2x 4- 2. The quotient is x 4-1 and the remainder is 1. Therefore
(x2 4- x 4-1) (x + 1) — (x3 4- 2x2 + 2x 4- 2) = 1. So x 4-1 is (x2 4- x 4-1)-1 in
this field.
EXERCISES
Level 1
 1. Find the minimum polynomial of \fl 4- >/T. (Compute its first four powers
    and show they are linearly dependent.)
 2. Prove the 3rd irreducibility criterion mentioned.
 3. Show the polynomial x2 4-1 is irreducible over R. Compute the multi¬
    plication table for 1, x.
 4. Show the extension in Exercise 2 is isomorphic to the complex numbers,
    using Theorem 6.1.2.
 5. Show that two different irreducible quadratic polynomials can give the same
    extension field.
Level 2
  1. Suppose x, y lie in extension fields of respective degree m, n over F. Show
     both lie in an extension field of degree at most mn over F. (Adjoin first x,
     then _y.)
  2. Show that x3 4- 3 is irreducible. (Any roots would have to be integers
     dividing 3.)
Sec. 6.2]          Applications of Extensions of the Rationals                215
            E =       Q[*l
                  (x3 + 3)Q[x]
 4. Multiply (1 + x 4- x2) (2 + 3x — x2) in this extension field.
 5. Find an inverse of (1 + x) in E.
 6. Verify that Exercise 5 gives an inverse of 1 +  3.
Level 3
 1. There is a finite procedure for determining if a polynomial p(x) of
    degree 2, 3 is irreducible over Z. (Try linear factors over Z whose first and
    last coefficients divide those of p(x).) Is there such a procedure for higher
    degrees, where some factors may not be linear? Can the coefficients of the
    factors be bounded (consider the roots of p(x))?
 2. Prove that C is the only finite extension field of R. Use the fact that every
    polynomial of odd degree has a real root.
 3. Prove that there exist infinitely many non-isomorphic extensions of Q of
    degree 2.
 4. Show that (x3 — 3) has a root in 0(^3) but does not factor into linear
    factors over this field.
 5. Find an irreducible polynomial of degree 3 over Q which does factor into
    linear factors of a single root is adjoined to Q. (Look up cubic equations,
    the discriminant must be a perfect square.)
generated as lengths. Then by laying out these lengths on the coordinate axes
we may obtain the required point.
      Conversely the only way we can obtain new points is by intersecting two
lines (ruler), a line and a circle (ruler and compass), or two circles (compass).
The line must be between two points already constructed, so its coefficients
lie in the field they generate. The circle must have a radius consisting of a length
already constructed and a center already constructed, so its coefficients lie in
the field corresponding to points and lengths already generated.
      The intersection of two lines is found by solving simultaneous linear
equations. Therefore it lies in the same field since such a solution can be obtained
by adding, subtracting, multiplying, and dividing.
      An intersection of a line and a circle
ax + by = c
(x — h)2,4- (y — k)2 = r2
can be found by solving the linear equation for one variable and substituting in
the equation for the circle. This involves only a quadratic equation, which lies
in an extension field obtained by adding a square root.
     The intersection of two circles
Ux-a)2 + {y-bf = c2
Ux-/z)2 + (y-*)2 = r2
may be found in the same way after first subtracting one equation from the
other to obtain a linear equation.                                       □
Proof All the extensions involved must be finite. Let x{ be a basis for F over K
and yf a basis for E over F. Let z E E then z = 2 afyj = 22 b^x^j for some
dj EF, bji&YL. Therefore the xtyj span E over K. Suppose they are dependent.
Let 2 bjiXiyj — 0. Let aj = 2 bjixi. If some by =£ 0 then some a;- =£ 0. Therefore
2 a/yj    0. This is false. So   form a basis for E over K.                     □
Sec. 6.2]          Applications of Extensions of the nationals               217
     This criterion suffices for most of the impossibility results for ruler and
compass construction. Trisection of an angle and duplication of a cube (con¬
struction of a cube with twice the volume of a given cube) require solving an
irreducible cubic. Constructing a regular p-gon for p a prime requires finding
a solution to an irreducible equation of degree p — 1 so p must have the form
2n + 1, as 2,3,5,17, 257,.... Since ir does not satisfy any polynomial over the
rationals it cannot be constructed, so that a circle cannot be squared.
     We give a brief survey of a topic which would require one or more chapters
to deal with adequately, Galois theory. There is a close relationship between
solving a polynomial and studying how quantities are affected by permutations
of the roots. For instance, the coefficients
            —Ci = Xi + x2 + ... + xn
It can be verified that A is irrational and, like complex conjugation, this process
preserves sums, and products.
EXERCISES
Level 1
 1. Tell why this diagram, constructible by ruler and compass, multiplies lengths
    x, y, where AC = x, DE = y, BC = 1, AE = xy.
Level 2
 1. Construction of a regular n-gon can be simplified by introduction of
    complex numbers. Let the centre be (0, 0) and the radius 1. Then if a point
    x, y can be constructed the number x + iy can be obtained by repeated
    extraction of square roots. The converse is also true. Let one vertex be
                            27t     2ir                2tt        2 7r
    (1,0). The next is (cos-—, sin—). Let z = cos — + isin —. Then it
    can be shown zn = 1. Factor zn — 1 to prove z satisfies the equation
    zn-i + zn~2+    " + z   + 1 = 0.
    Show all coefficients after un are divisible by n but the constant term is
    precisely n. Therefore a regular p-gon is not constructive by ruler and
    compass for p not of the form 2k + 1.
 6. Prove the Eisenstein Irreducibility Criterion. If /(x) = g(x)h(x), prove that
    all coefficients of g, h except the first are divisible by p by reducing f, g, h
    modulo p. Then show the last nonzero coefficient of / is divisible by p2,
    contradiction.
Level 3
 1. Derive the solution of the general cubic equation, as follows. We use
    solvability of S3 by the series {e} CZ3C S3. Let the roots be xlt x2, x3.
    Begin with A = (xx — x2) (x2 — x3) (xx — x3). Since A2 is a symmetric
    function we can express it in terms of the coefficients cu c2, c3 of
    x3 — CjX2 + c2 x — c3 by the methods of Theorem 5.5.5. Assume that
    Ci = 0. This yields A2.
 2. Let to be a nontrivial root of co2 = 1 where
               l-iy/3
            to =-.
                         2
"11 1 "
1 to to2
-1 co2 CO -
    powers of zp. Then /(x)|,g-(x) since g(z) = 0. Yet this is not possible since
    yp~l + yp~2 + ... + y + 1 is irreducible. So for p > 2, a regular polygon of
    degree p2 cannot be constructed with ruler and compass.
THEOREM 6.3.1. Every finite field F has pn elements for some prime p, and
Zp is a sub field of F.
Proof Let F be a finite field. Then the additive group is finite, so for some
integer n, a sum of n copies of 1 is zero. We write n 1 = 0. Choose n to be the
least such positive integer. Suppose n = ab where a, b G Z+, 1 < a, b < n. Then
(al) (hi) = n \ but al =£ 0 and b 1^0. This contradicts the properties of a field.
So n is a prime p, unless n = 1. But if n = 1 then 1 = 0, which is false. So assume
P > 1.
      The set S of all sums of copies of 1 will be closed under addition and multi¬
plication. The additive and multiplicative groups of F are finite. This means that
some repeated sum of an element will be its additive inverse. The same is true for
products. So any subset closed under addition and multiplication also contains
all additive inverses and multiplicative inverses of nonzero elements. So it is a
sub field.
      The mapping a -» a\ is a ring homomorphism from Z onto S. Its kernel is
precisely the set of multiples of p. So by Theorem 4.3.5, the quotient ring Zp
is isomorphic to S.
      Now F is a vector space over S. So F has a basis xlf x2,..., x^. Then F
is in 1-1 correspondence with the set of all sums axXi 4- a2 x2 + ... + dkxk
where alt a2,..., ak G (0,1, 2,..., p — 1}. The number of such sums is pk.
So |F | = pk.                                                                    □
              F(s)
            pWFW
where p(x) is an irreducible polynomial over Zp. The elements 1, x, x2,..., xn~x
form a basis if p(x) has degree n. This determines the addition, for example in
an extension of Z5 of degree 2:
1 + 4x + 3 (2) = 7 + 4x = 2 + 4x
+ 0 1 X 1+ x
                  0        0         1        X      1+ x
                  1        1         0      1 + x      X
                  X       X        1+x        0         1
              1   + X    1+ x        X        1         0
X 0 1 X 1 + x
                  0        0         0        0         0
                  1        0         1        X       1+ x
                  X        0         X      1+ x        1
              1   + X      0       1+ x        1       X
EXAMPLE 6.3.2. We find a logarithm table for the field of order 8 generated
by z such that z3 + z + 1 = 0. The powers of z are:
z2=z2
z3 = 1 + z
z4 = z(l + z) = z + z2
zs = z(z 4- z2) = z2 4- z3 = z2 4- 1 4- z
z6 = z(z2 + 1 + z) = z3 + z + z2 = 1 + z + z + z2 = 1 + z2
z7=l
     The major theorem about finite fields is that there exists one and only one
field of order pn for every prime p and positive integer, n. To show existence it
suffices to show there exists at least one irreducible polynomial of degree n, then
the quotient ring has degree n over Zp.
Proof                           p_i
            (x + y)p - xp + yp + 2 (p)xryp~r.
                                      r=1
But for r = 1 to p — 1, p\p\ but not r\(p — r)!, since p does not divide any of
the factors of the latter expression. Thus p \(p). So in R, (x 4- y)p = xp + yp.
Also, by commutativity (xy)p = xpyp. And by Corollary 4.4.4, (nl)p = nl.
Therefore x -+xp is a ring homomorphism which is the identity on {«1}. But
x ^ xpT is the r-fold composition of x->xp with itself. So it is also a ring
homomorphism which is the identity on {«1}.                                   □
the derivative is linear: D(af + bg) = aDf + bDg. The formula D(fg) =
D(fg) = fDg + gDf holds for any powers xn,xm of x. By linearity one can
then show it holds for any /, g.
Proof Suppose this equation has an irreducible factor /(x) of degree larger
than n. Then form the quotient ring Rq associated with /(x). This quotient ring
has as a basis 1, x, x2,, xfc_1 and is a field of order pk where k> n. Since
/(x) xp      — 1, in this field xp  = 1. So xp = x. But this implies for any
k, (xk)pn = xk. By Lemma 6.3.4,
              ZP[*]
            /(x)Zp[x]
THEOREM 6.3.6. For any prime p and positive integer n, there exists a unique
field of order pn. A field of order pm is isomorphic to a sub field of a field of
order pn if and only if m\n.
where not all a,- are 0. Call this polynomial #(x). Then the degree of g(x) is
less than n, so g(x) is not divisible by f(x). Since f(x) is irreducible, g.c.d. of
f(x),g(x) is 1. Therefore f(x)u(x) + p(x)g(x) = 1. Put x = r. Then 1 = 0.
This proves 1, r, r2, ..., rn~x are linearly independent. Their span has pn
elements. So it is all of Fj. So they are a basis. Likewise 1, s, s2,..., s"-1 are a
basis for F2.
     Now define a function h : Fi -> F2 by
      Finite fields are also called Galois fields. A finite field of order pn is denoted
GF(pn).
   Many methods we have used here can also be used in the study of infinite
fields.
EXERCISES
Level 1
 1. Write out the addition table of a field of order 9. The 9 elements have the
    form a + bx, a, b E 0,1, 2 and are added as polynomials in Z3.
 2. Work out the multiplication table of this field. Use x2 4- 1 as a generating
    polynomial, so that x2 = — 1 in this field. (We can write the elements as
    a + bi, i = y/—\ instead of a + bx.)
 3. Find a multiplication generator g of this field and compute its powers
    g,g2, ,g•••   8-
Level 2
 1. Find an irreducible monic polynomial of degree 3 over Z3. It must satisfy
    /(0) =£ 0, /(l) =£ 0, /(— 1) ¥= 0 modulo 3.
 2. Show that if an irreducible polynomial of degree n, p > n > 1 exists over
    Zp one exists having the coefficient of x"-1 equal to zero.
 3. In a field of order 27 construct the multiplication table of 1, x, x2.
 4. Show that for any odd prime p there exists an irreducible quadratic over
    Zp of the form x2 — a. Use results on quadratic residues from Proposition
    4.4.7 and Corollary 4.4.8.
 5. Show that for any odd prime p of the form (6n + 1) there exists an
    irreducible cubic of the form x3 — a over Zp.
 6. Find an irreducible polynomial of degree 2 over GF(4). Using it find a
    logarithm table for the field of order 16.
Level 3
  1. Show the automorphism x -> xp generates                 a   cyclic   group Zn of
     automorphisms of a field of order pn.
Sec. 6.4]                         Coding Theory                                227
                                                                      k
 2. Show every automorphism of a finite field has the form x -*■ xp ./
 3. If f(x) is a monic polynomial with coefficients in Z which factors over Z
    it factors over Zp for every prime p. Do you think the converse is true?
    (This is a deep question. For quadratics it holds by quadratic reciprocity.)
 4. For 2,3 it has been remarked that xk + x 4- 1 is irreducible over Z2. What
    about 4, 5? Try irreducible quadratic factors x2 + ax 4- 1.
 5. Show that every irreducible polynomial of degree n is a divisor of xp — x
    which does not divide xp — x for k < n. Hence factoring xp — x is not
    in general a good method of finding irreducible polynomials.
Coding theory is concerned with methods of symbolizing data such that most
errors can be detected. This is done because correctly coded messages have a
certain form. For instance if the first digit of a number could not exceed 7, and
a 9 is received there must have been an error. Error correcting codes cannot
correct all possible errors since for any correct message any other correct message
of the same length could have been sent instead. They correct errors occurring
in only a small proportion of the digits in each group of numbers. Such codes
are widely used in computer circuitry and in digital radio communications.
     The simplest error-detecting code of any interest is a parity check. Suppose
a coded message is in blocks of 7 digits 0,1. Then an extra digit is added to
each block. This digit is chosen to make the total number of ones in the block
even.
     This code detects any single error in a block. If a single error is made, the
number of 1 digits is changed by 1 and therefore becomes odd. If a receiver sees
a block having an odd number of 1 digits, he knows an error has occurred.
However, if exactly 2 errors occur, the code cannot detect any error.
     This is an error-detecting code. There also exist error-correcting codes
which can tell what the correct block should have been, provided that 1 or more
errors occurred. A trivial example is the code with blocks of length 3 each all
zeros or all ones, 0 0 0 or 1 1 1. If a single error is made, the receiver can tell
whether the original block was 111 or 0 0 0 by looking at whether there is a
majority of ‘0’s or a majority of Ts.
     To be precise we assume the message is encoded in blocks of m digits from
a set S containing q possible digits. Each block is encoded as a block of n
digits from S where n>m.
228                                Field Theory                               [Ch.6
     A code involves a coding function from length m sequences from the set S
of symbols to length n sequences, and then a decoding function to recover the
original. However, for error detecting and correction the essential thing is the set
of encoded words, not the coding function: any 1-1 function may be chosen.
The coding and decoding functions should, however, be rapidly computable.
     We assume q is a power of a prime and regard S as GF (q). Also we regard
a sequence of length m as a vector of length m over GF (q).
DEFINITION 6.4.1. Let V(n, q) denote the set of n-dimensional vectors over
GF (q). A code is a subset of V{n, q). A coding function is a 1-1 function
c: V(m, q) C V(n, q) whose image lies in the code. A decoding function is a
function d such that d{c(v)) = v for all v £ V(n, q).
DEFINITION 6.4.2. For two vectors u = (ulf u2,..., un), v = (vu v2,, vn)
the Hamming distance H(u, v) is the number of places where the vectors differ,
i.e. |{i: Ui^Vi}\.
    Note that H(u, v) = H(u — v, 0). The function H(u, 0) is sometimes called
the weight of u, for any vector u.
THEOREM 6.4.1. A code can detect up to k errors if and only if the Hamming
distance between two encoded words is at least k + 1. It can correct up to k
errors if and only if the Hamming distance between any two encoded words is at
least 2k + 1.
Proof We will prove the latter statement first. Suppose the distance between
any two encoded words is at least 2 k + 1. Suppose that an encoded word v
is sent and that after at most k errors in transmission it becomes w. Then we
claim that v is the unique encoded word such that H(v, w) < k. Suppose for
u^v, H(u, w) < k. Then H(u, v)<,2k. But this is contrary to assumption.
So the receiver can find the unique encoded word w such that H(v, w) < k.
This must be the correct original word v.
Sec. 6.4]                        Coding Theory                                229
     The problem is to find codes which are efficient. If n is twice m, then the
code takes up 100% more time than the original transmission. So n should be
not too much larger than rn.
EXAMPLE 6.4.5. The example 000,1 1 1 used to encode 0,1 has rate f = 3.
It is not very efficient.
But there are only qn vectors in all in V(n, q) so this quantity does not exceed
q n. This implies the inequahty.                                              □
            <7 “I
called Hamming codes. We consider these for q =2.
DEFINITION 6.4.4. Let A be the (2k — 1) X k matrix such that the /'th row
of A is the number / written in binary-notation.
            ~0      0   f
             0      1   0
             0      1   1
             1      0   0
             1      0   1
             1      1   0
            _1      1   ^
EXAMPLE 6.4.7. Suppose we wish to encode the vector v = (1,1, 0,1). Write
w = (wj, w2,1, vv4, 1, 0, 1), where the components of w are the unknown w2/
together with the entries of v.
wA = [vv4 w2 Wi 4- 1 ]
So let vv4 — 0,w2 = 0, Wj = 1. The encoded vector w is (1, 0,1, 0,1, 0,1).
PROPOSITION 6.4.3. For any vector u there exists a unique vector w such that
wA - 0 and = ut for i not of the form 2/
             2   wh =   0
           h&S
Sec. 6.4]                             Coding Theory                               231
THEOREM 6.4.4. The Hamming code can correct any 1-digit error.
Proof. Suppose that the correctly coded vector is v, and that an error in 1-digit
has been made, resulting in a vector w. Then v — w is a vector u having exactly
one 1. The location of this 1 is the location of the error. Therefore
1 + plog2 p + (1 - p)log2 (1 - p)
Proof. Let C be a code any pair of whose members have Hamming distance at
least t+ 1. Let V be the set of vectors having zeros in places 14-1, t + 2,..., n.
Then all words c + v, cEC, vEV are distinct, else if cx 4-        C c2 + v2 then
232                                Field Theory                              [Ch.6
      This proof used the fact that V is a set of words of weight at most t, closed
under addition.
EXERCISES
As in the preceding section, here m is the length of a message block before
encoding, q the number of possible symbols, n the length of a message block
after encoding and t the number of errors correctible.
Level 1
 1. Define a modulo 3 code by adding a digit such that the sum of all digits is
    divisible by 3. EncodeK) 12 11.
 2. Show the preceding code detects a single error.
 3. Encode 10 0 0 using the Hamming code.
 4. Decode 1 0 11 0 11 in the Hamming code.
 5. If a message 1111111 in the Hamming code is received, how many errors
    occurred (assuming at most 1 did)? Where?
 6. What are the rates of the Hamming codes?
 7. Prove the Gilbert-Varshamov lower bound. There exists a t error-correcting
    code over GF (q) with n code words and
                S (")(*-1)' H>q"
               i= 0
      Assume that q code words have been found having Hamming distance at
      least 2t + 1 from the rest. Show that if the inequality is false then words
      at Hamming distance less than or equal to 21 from existing words do not
      exhaust all words. So a new one can be added, increasing n.
Level 2
 1. Construct a nonperfect code with n = (21 + \)m, m > 1 by repeating each
    block t times. Prove it corrects t errors.
 2. Characterize the set of correctly coded words in the Hamming code.
 3. Define the Hamming codes for q > 2.
 4. For q > 2 prove results analogous to those given in the text for q =2.
 5. Give examples of encoding in the Hamming codes for q> 2.
 6. Give examples of decoding in the Hamming codes for q > 2.
 7. For a perfect code to exist
              s (")(?-!)'
             i= 0
      must be a power of q. For t = 2 give examples of n, q which are ruled out.
Sec. 6.5]                         Cyclic Codes                               233
 8. Fix t, q. Suppose a perfect code existed for n. Show that as n -> 00 the rate
    would approach 1.
Level 3
 1. Prove a code is perfect if and only if every sequence of length m can be
    decoded by the procedure of Theorem 6.4.1.
 2. What is the average Hamming distance between two words of length nl
    This is the same as the average number of nonzero entries of a given word.
 3. Consider a code satisfying the Gilbert-Varshamov lower bound. If £ -» 0
    does the rate approach 1?
 4. Look up and write out in your own words a proof of Shannon’s theorem.
                 F[s]
            (jc"-1)F[x]
Such ideals can be dealt with by specifying a generating polynomial, which can
be chosen to divide (xn — 1).
    Three classes of such codes are the BCH codes, constructed by R. C. Bose
and D.K. Ray-Chaudhuri, and independently by A. Hoquenghem, in 1959, the
Reed-Solomon codes of I. S. Reed and G. Solomon, and the Fire codes of
P. Fire.
PROPOSITION 6.5.1. A code is cyclic if and only if it is an ideal in
                 F[*]
            On- l)F[x]
Proof A linear subspace in this ring is an ideal if and only if it is preserved
under multiplication by x. But this takes a0 + fiiX + ... + an-\Xn~l to
an-\ 4- a0 x + ax x + ... + an_2   which is a cyclic rotation.               □
Proof. An ideal 7 in
                F[x]
            (*”-l)F[x]
234                                      Field Theory                       [Ch.6
gives an ideal I, in F(x), namely all polynomials whose image lies in I. If 17 had
two monic polynomials of lowest degree, their difference would give a monic
polynomial g(x) of lower degree, which is a contradiction. The g.c.d. of this
polynomial and (x” — 1) lies in 17 so this g.c.d. cannot have degree less than
g(x). So it must be g-(x). So g(x)\xn — 1. If f(x) did not divide any member
of I there would be a similar contradiction.                              □
     The problem is to find an ideal which has a large number of elements
and can correct or detect many errors. The number of errors detectible is the
minimum Hamming distance which equals the minimum weight of any poly¬
nomial. The number of members of the ideal is qn~dt^s) sjnce the quotient ring
has basis 1, x,..., xdeg(-^“1, and so has     elements.
     The following lemma is the means'of guaranteeing that polynomials of small
weight are not in the ideal.
Zi z\ ... z?
Z2 z\ ... Z2
Proof For n — 2 this result is correct. Assume it is true for all numbers less
than n. Subtract zn times column n — 1 from column n, zn times column n — 2
from column n — 1, and so on. This will not affect the determinant. We have
Jn 0 ... 0
Expand by minors on the last row, and factor out the quantities in parentheses.
We have (—1)” 1zn(zl — z„) (z2 — z„) ... (z„_1 — z„) times the determinant of
                                     n—l
             Zj      Zf             Zl
                                     n-1
                              ...
Sec. 6.5]                                 Cyclic Codes                       235
                                  n       (zt-Zj)
                             j < i<n
Thus the determinant for the nX n matrix equals the given formula. □
THEOREM 6.5.4. Let d,n, qE Z+, d<n, and (n, q) = 1. Let F be GF(q).
Let E be a field such that F C E and there exists y G E with yn = 1, but no
lower power of y is 1. Suppose g(x) is a monic polynomial over F such that
y,y2,, yd~l are roots of #(*), and#(jc)\xn —1. Then the minimum Hamming
distance between elements of g(y)R(y) is at least d. Here R(y) denotes the
quotient ring where y = x and the set g(y)R(y) is the ideal I in R(y) generated
by g(y).
Proof. Let p(x)Gj. Then £(x)|p(x) and p(y) = p(y2) = ... = p{yd~x) = 0.
We need to show that if p(x) =£ 0 then p{x) has at least d nonzero coefficients.
Let
          p{x) = Cq + CjX + c2 x2 + ... 4- Cn_iXn~l
and    let    v = (c0, cx,..., cn_f). Then the equations p(y) = p(y2) = ... =
P(yd l)      — 0 are equivalent to the matrix equation vA = 0 where A is the
matrix
               "l       1         ... 1
                y       y2            yd-1
      We will show that any (d — 1) rows of this matrix are linearly independent.
236                                         Field Theory                [Ch.6
                                      d—l
               Z\      *1   ■   ..   Z1
                                      d—l
               *2      z\   . • •    z2
                                          d—l
               zd-1    Zd-1 •        za-l
We compute the numbers associated with this code as follows. The numbers
such that there are qm elements in the ideal. It will be n — deg (g(x)).
     The remaining question, is, what choice of g(x) has minimal degree? Let
s(y, F) denote the polynomial of least positive degree of which 7 is a root.
Then s(y, F), s(y2, F),..., s(7d_1, F) must divide g(x). So the best choice of
^(jc) is their least common multiple (l.c.m.).
                    F[*]
             (xn — l)F[x]
generated by
The ideal has two code words 0 and x2 + x + 1. This gives the code 000, 111
which can correct 1-error.
Sec. 6.5]                          Cyclic Codes                                237
Proof. Suppose a code word c(x) has a burst-error b(x) during transmission so
that r(x) = c(x) + b(x) is received. Write b(x) = x7fc(x) where k(x) = 2 ^/x3
of degree at most P — 1 and k0 =£ 0, or b(x) is identically zero.
238                                  Field Theory                              [Ch.6
xa = l(mod p(x))
EXERCISES
In the following exercises, as in the text, q is the number of possible letters or
symbols, m the length of a message block before encoding, n the length of words
in the code, d the number of errors detectible, t the number of errors correctible.
For a Fire code /3 is the size of a burst-error correctible, and c is the degree of a
polynomial p(x) such that p(x) (x2(i — 1) generates the code.
Level 1
 1. For d = n what is the only linear code which has Hamming distance > d
    between any two members?
 2. For d = n — 1 what is the only code with at least two members?
 3. For q - p where p is a prime number, let y generate the extension field
    Z(pk) and be a primitive root. Give an example.
 4. For q = 2, n = 5, there exists y G GF (16) satisfying xs — 1. Its minimum
    polynomial is x4 + x3 + x2 + x + 1. What code results?
                                         i
Sec. 6.5]                          Cyclic Codes                              239
Level 2
 1. Suppose y generates the extension field GF(qn) and is a primitive «th root
    of unity. For d = l,what is m for BCH codes?
 2. Do the BCH codes include any with the same parameters as the Hamming
    codes?
 3. Why must any two of the s(yl, F) be equal or be relatively prime?
 4. Compute a generating polynomial for a Fire code with (3 = 2, q = 2, n = 25,
    c — 4. What is m and the rate?
 5. Compute a generating polynomial for a Fire code with (i = c = 3, q = 2,
    n = 35. Use the same p(x).
 6. Compute a generating polynomial for a Reed-Solomon code correcting one
    error for n — 1. Here y is any member of GF (8)\G.F (2).
 7. Encode 111 0 0 0 in the preceding code.
Level 3
 1. Prove, using the idea of Theorem 6.5.4, that for a BCH code and a word
     r(x) = c(x) + e(x) where c(x) is a code word and e(x) an error having
    at most t nonzero coefficients the 21 quantities S( = ^(7'), i = 1, 2,..., 2t
    depend only on e(x) and uniquely determine e(x). This is one basic idea in
    decoding BCH codes. It reduces the problem of finding the error to solving
    the 21 equations
                    t        inj
            S( =    2 CP 1
                   i =   1
             ~1    2    3_
              2    3     1
             _3    1    2_
DEFINITION 6.6.2. Two Latin squares A, B are orthogonal if and only if the
set of ordered pairs (ay, by) includes every ordered pair of integers from 1 to n.
EXAMPLE 6.6.2. Let A be the matrix of first entries in the 5X5 matrix above
and B be the matrix of second entries.
                  1     2      3   4      5         1      2     3   4     5
                  2     3      4   5      1         3      4     5   1     2
                  3     4      5   1      2    5    5      1     2   3     4
                  4      5     1   2      3         2      3     4   5     1
                  5      1     2   3     4          4      5     1   2     3
THEOREM 6.6.1. Let n = p?1 p”2... Pkk- Let k = inf {pf* — 1}. Then there
exist k mutually orthogonal nXn Latin squares.
EXAMPLE 6.6.3. For n = 5,we take square 1 having (i, ;')-entry i + / modulo
5 and square 2 having (/, /)-entry i + 2/ modulo 5. This gives
242                                           Field Theory                                        [Ch. 6
*0 1 2 3 4 "o 1 2 3 4
              1    2      3           4       0                 2        3       4       0   1
              2    3      4           0       1         9       4        0       1       2   3
              3    4      0           1       2                 1        2       3       4   0
              4    0      1           2       3                 3        4       0       1   2_
                                              —
     For prime powers, this result is best possible. For any number n there
exists a Latin square, the addition table of Zn. For n = l,2,6; G. Tarry in
1900 proved there does not exist any pair of orthogonal Latin squares. In 1782
Euler had proved already there exist a pair of orthogonal Latin squares for
all n ^ 2 (mod 4). The problem of whether orthogonal Latin squares exist for
n = 2 (mod 4) was unsolved until the 1958 work of R. C. Bose, S. S. Shrikhande,
and E. T. Parker.
     Many constructions for Latin squares depend on an equivalent concept,
orthogonal array.
1—*
             "0       1   2
              1    2      0       5       2       0             1
                   o
                                      _!          2             0.
                              1
"0 1 2 1 2 0 2 0 1"
_0 1 2 2 0 1 1 2 0_
by writing out each matrix row by row. The columns include all 9 possible
ordered pairs each exactly once.
Sec. 6.6]                              Latin Squares                       243
     For two rows to be orthogonal means as here that the corresponding entries
of the rows run through all entries of the Cartesian product set.
THEOREM 6.6.3. There exist m mutually orthogonal Latin squares if and only
if there exists an orthogonal array of size (m + 2)X n2 whose entries are from
{1, 2,... ,n}.
                     1       1 . . 1                1       2 . . n
                     2       2 . . 1                1       2 . . n
            A =                        , B =
n n . . n _1 2 . . n
That is, they are A, B. So the other rows regarded as matrices, are matrices
orthogonal to A, B and to each other. So they are mutually orthogonal Latin
squares.                                                                     □
             0       0      0     1     1      1        2    2    2
             0       1      2     0     1      2        0    1    2
             0       1      2     1     2      0        2    0    1
             0       1      2     2     0      1        1    2    0
244                                  Field Theory                           [Ch.6
DEFINITION 6.6.4. Two Latin squares are isotopic if one can be obtained
from the other by changing the labels of elements, permuting the rows, and
permuting the columns.
             a         b   c     c    b      a
             b         c   a t   a    c      b
             cab                 b    a      c
are isotopic. Change labels a, b, c to c, b, a. Then interchange the last two rows.
     Isotopy is an equivalence relation on Latin squares. The number of isotopy
classes ofnXn Latin squares for small values of n is:
n Isotopy classes
                 1-3                  1
                 4-5                  2
                  6                  22
                  7                  563
                  8            1,676,257
EXERCISES
Level 1
 1. Construct two orthogonal 3X3 Latin squares.
 2. Construct four orthogonal 5X5 Latin squares.
 3. Show any 3X3 Latin square can be written as
              a        b   c
              b        c   a
              cab
Level 2
 1. Show that r rows of a Latin square can be extended to r 4- 1 rows if
    and only if the system formed by the complements of the columns has an
    SDR.
 2. Prove there exist exactly two isotopy classes of 4 X 4 Latin squares.
 3. Give two 5X5 Latin squares which are not isotopic.
 4. Let G be any set with a binary operation denoted product, such that
    for all a, b there exists x, y with ax = b and by = a. Show that the
    multiplication table of G is a Latin square.
 5. Count the number of 3 X 3 Latin squares with entries a, b, c. Count 4X4
    Latin squares with entries labelled a, b, c, d.
 6. Prove there is a correspondence between sets of t mutually orthogonal
    q X q Latin squares and codes which can detect f-errors with word length
    n = t + 2 where m — 1. Let M(r) be the Latin squares. Let the coding of
    i, j be the sequence m<l>^, m<2>y,..., m(t){j.
Level 3
 1. Show there exist at most m — 1 pairwise orthogonal Latin squares, for any
    m.
 2. For two groups Glt G2 when are the Latin squares arising from Gh G2
    isotopic?
 3. Show that for n a prime power = 3 (4) there exist two orthogonal m X m
                             3n — 1
    Latin squares where m = —-— (E.T. Parker). Let g generate the multi¬
yt g2i(g + 1) + X g2t + X X
X yt g2i(g + 1) + X g2i + X
Fx X yt g2i(g + 1) + X
(g + 1) + X g2t + X X yt
            x
246                                     Field Theory                                [Ch. 6
                                         /   __ ^   ^2
as x runs through GF(n). Add -— -columns whose entries correspond
PP1. Two distinct points lie on one and only one line.
PP2. Two distinct lines have one and only one point in common.
PP3. There exist four distinct points no three of which lie on any line.
     The standard example of a projective plane has P being the set of points of
the plane together with 1 point at infinity lying on each line through the origin,
and L the lines of the plane, together with the line at infinity, whose points are
the points at infinity. A line m in the plane contains one and only one point at
infinity, the point for the line through the origin parallel to m.
THEOREM 6.7.1. For any field or division ring F exists a projective plane
whose points are the 1-dimensional subspaces of a 3-dimensional vector space
over V and whose lines are the 2-dimensional subspaces of V.
Proof. The intersection of any two distinct 2-spaces must be nonzero since other¬
wise their direct sum. of dimension 4 would be contained in a three-dimensional
space. So it is a space of dimension 1, since its dimension is less than 2. Any two
Sec. 6.7]              Projective Planes and Block Designs                     247
                                                     p3k~ 1          p3k-1
    This theorem gives a projective plane having         points and
                                                 pK-1 r               pK-1
lines, for every prime power pk. Such planes can be characterized by the fact
that the theorem of Desargues holds in them.
     This theorem states that if the following sets of points are collinear:
(a) 0, Au A2, (b) 0, Bu B2, (c) 0, Q, C2 then the three intersections (d) AXBX
intersected with A2B2, (e)v4iCi intersected with A2C2, (f)5iQ intersected
with B2 C2, are collinear.
     Many other projective planes exist in which the theorem of Desargues is not
true. See Hall (1959), Hughes and Piper (1973), and Pickert (1955).
     First, set O = (0,0), U = (1, 1) and assign coordinates (a, a) to the other
points of OU in any 1-1 fashion, where a = 2, 3,..., n — 1. If P & OU U XY,
let P = (a, b) where (b, b) is the intersection of XP and OU and (a, a) is
the intersection of YP and OU. To a point at infinity on the line joining (0, 0)
and (1, m) assign the coordinate (m) (which can be considered a slope of a class
of parallel lines). Assign Y the coordinate (°°).
     Then a ternary operation on 0,1,2,...,«— 1 is defined by y = x • m O b
if and only if the line L through (m) and (0, b) contains the point (x, y). Since
this is the intersection of L and the line joining (°°) and (x, x), a unique y exists.
     This ternary operation has the following properties:
    Conversely it can be proved that any ternary system with these five
properties determines a projective plane.
of lines. By examining the special cases satisfying 1, 2 but not 3 we find that
none satisfies the hypotheses of the proposition.                            □
                          Factor a
                          1      2     3
Factor b 2 3 1
3 1 2
where the value of factor c is in the interior. A more general balanced incomplete
block design would be
1 2
Factor b 2 3
3 1
Here perhaps it is feasible to make only two experiments for each value of
factor b. Only two factors, b, c are involved.
             V
              2
              3
AAt = \J + (r - X)V
and its column sums are each k. Conversely any v X b (0,1)-matrix with these
properties defines a BIBD (b, v, r, h, X).
Proof (1) holds since !g(S)| = |S|. (2) and (3) are unaffected if we take
m copies of each block for any m. Take therefore as blocks all sets g(S) in
which each distinct block occurs a number of times equal to |{g: g(S) = 5}|.
Then (2) follows from transitivity since i G g(S) if and only if h(i) G h(g(sf).
And (3) follows from double transitivity since i, j E g(S) if and only if
HO ,h(j)Eh(g(S)).                                                             □
EXERCISES
In the following exercises, for balanced incomplete block designs, v is the
number of elements in the union of all blocks (rows), b is the number of blocks,
k is the number of elements per block, r is the number of blocks a given element
belongs to, and X is the number of blocks a given pair of elements belongs to.
Level 1
 1. Find a 7 X 7 circulant (0,1)-matrix having 3 ones in each row and column,
    which is a projective plane. Assume these main diagonal entries are all 1 as
    well as the (1, 2)-entry.
 2. Do the same for a 13 X 13 matrix with 4 ones per row. This should be the
    projective plane arising from GF(3).
 3. Construct a BIBD (n, n, n — 1, n, n — 2) for any n.
 4. Construct a BIBD ((£), H,(£lj),               f°r any n> from ah subsets of
    a set of n elements.
 5. Explain why k < v in BIBD.
Level 2
 1. Show that a Veblen-Wedderburn system defines a projective plane. This is
    a set having two binary operations denoted addition and multiplication such
    that (1) addition is an abelian group, (2) multiplication has a unit 1 and
    multiplication by any nonzero element is 1-1 on either side, (3) (a + b)m =
    am + bm, (4) if r     s xr = xs 4- t has a unique solution x.
 2. From the ternary system corresponding to a projective plane explain how
    to obtain n — 1 orthogonal nX n Latin squares. Show how to do the
    reverse also.
 3. What are the parameters of the BIBD of all k-spaces contained in an
    rc-space over GF (#)?
 4. Prove that in a BIBD r > X.
 5. If a system satisfies (PP1) and (PP2) for a projective plane and two distinct
    lines contain respective points (a, b) and (c, d) not equal to their intersection,
    show (PP3) holds.
 6. Consider a system formed by a line L with n > 2 points and single point 0
    not on L, together with all lines OX for X G L. Show (PP1), (PP2) but not
    (PP3) holds.
Level 3
  1. Prove the projective planes arising from lines over GF (q) can be represented
     by a circulant (0, l)-matrix. Represent the 3-space as GF(q3) and use the
     fact that its multiplicative group is cyclic.
  2. Write a matrix for a projective plane of order 4.
  3. Express the general condition on the first row for a circulant matrix to
     represent a projective plane.
252                              Field Theory                            [Ch. 6]
4. Prove that b > v for a BIBD. Compute det (AA1) and note that it is zero if
   b < v since A A1 would have rank < b < v.
5. For all values of b, v, k which are at most 5 such that positive integers X, r
      can be defined by bk = vr, \(v — 1) = r(k — 1) and the inequalities
      k < v, r > X, b > v, try to construct a BIBD.
Open problems
An open problem is a question for which no one has yet been able to provide an
answer and prove it. Most of the open problems listed here are famous, and
have been worked on for many years by many mathematicians. Partial results
have been obtained. This course provides you with enough tools to understand
the problems, so we encourage some of you to solve these problems.
CHAPTER 1
xEA, 10
F: family of sets, 10
  U A, U A, 10
AE F      F
  n A, n A, 10
AEF       F
ACB,BDA, 10
A : complement of a set A, 11
A\B (A — B): relative complement of a set B, 11
 0: empty set, 11
 U: universal set, 11
 \A\: cardinality of a set A, 11
(a, b): ordered pair, 13
 AiX A2X ... X An: Cartesian product, 13
 R: the set of real numbers, 13
 x — y: congruence, 13
 x ~ y: similarity, 13
 S(n, k): Stirling’s number of the second kind, 15
 R o S : composition of relations R and S, 17
f og: composition of functions / and g, 17
t: identity function, 17
1 — 1: one-to-one, 18
f~l\ inverse function of/, 18
xR y : (x,^) E R, 20
Qd: indifference relation, 21
<2S: strict order, 21
(x, y): ordered pair of equivalence classes, 21
8: two element {0,1} Boolean algebra, 26
                            List of Special Symbols       255
CHAPTER 2
V: join (lattice), 41,114
A: meet (lattice), 41,114
En: n-dimensional Euclidean space, 42,101
x: equivalence class of x, 46
AB: {ab: a G A, b £ B], 51
Sl: semigroup with identity, 51
L: Green’s relation, 51
R: Green’s relation, 51
J: Green’s relation, 51
D : Green’s relation, 51
H: Green’s relation, 51
Mn(F): the set of n X n matrices over F, 53
Tn: the set of transformations on an ^-element set, 53
Bn: the set of n X n Boolean matrices, 53
F: field, 53,119
rank(/): rank of/, 55
im (A) : image of A, 59
(S, X, Z, v, 8): finite state machine, 60
v(s, x): next state from state s and input x, 62
5(s, x): output from state s and input x, 62
(TV, T, P,o) : phrase-structure grammar, 64
L(G) : language generated by grammar G, 65
e: identity (group), 68
Z: the set of integers, 68
Q: the set of rational numbers, 68
256                        . List of Special Symbols
CHAPTER 3
V: vector space, 119
Fn: F © F © ... © F, 119
I: index set, 122
(S): span of S, 123
U © V: internal direct sum, 129
dim W: dimension of W, 129
at,™: (i, /)-entry of mth power of Am, 134
Aij- (i, /)-blockof A, 134
A-1: inverse of A, 137
cof(y4): cofactor of A, 145
adj (A): adjoint of A, 145
Tr (A) : trace of A, 146
x • y: inner product, 157
Cn: C©C®... ©C, 159
                             List of Special Symbols         257
CHAPTER 4
R: ring, 163,164
c.d.: common divisor, 163
J: ideal, 164
R/H: quotient ring, 164
Z+: the set of positive integers, 165
V: integral domain, 165
F[x]: ring of polynomial over F, 166
Q[x]: ring of polynomial over Q, 166
g.c.d.: greatest common divisor, 166
(a, b) = 1: a and b are relatively prime, 168
E: Euclidean domain, 168
v(a): degree of polynomial, 168
x~y: similarity (ring), 173
co : primitive rzth root of unity, 178
Rp: division ring, 180
CHAPTER 5
F(G): group ring over F, 184
M: module, 184
R(G): group ring over R, 185
char (F): characteristic of a field, 193
K: maximal proper left ideal, 194
C(G): group ring over C, 195
Mn(C): the set of n X n matrices over C, 195
X: group character, 197
A ® B: tensor product, 198
[G: H]: index of H in the group G, 95, 203
Xfc(M): fcth exterior power, 204
Sfc(M): kth symmetric power, 204
Lln: the set of n X n unitary matrices, 205
ok : A:th elementary symmetric function, 206
rI \ standard representation, 206
CHAPTER 6
BCH: Bose-Chaudhuri-Hoquenghen code, 211
[E : F]: degree of the extension, 211
[C : R]: degree of the complex numbers over the reals, 211
F(5): field generated by S over F, 212
E(x): field generated by x over E, 212
258                      List of Special Symbols
               A                            Character, 197
Absolute value, 165                         Characteristic
Abelian group, 70                              of field, 193,221
Algebra, 179                                   polynomial, 145
Algebraic integer, 200                         subspace, 151
Alternating group, 97                       Circulant, 154,155
Antisymmetric, 20                           Class, 11
Arrow’s Impossibility Theorem, 35           Clique, 56
Artinian ring, 182                          Cluster, 56
Associativity, 11,17                        Code, 228
Automorphism group, 72                      Cofactor, 145
Axiom of Choice, 24                         Column rank, 140
                                            Column space, 140
               B                            Column vector, 134
Balanced incomplete .block design (BIBD),   Commutative ring, 164
       249                                  Commutativity, 11
Basis, 123,128                              Comparable, 22
BCH code, 236                               Complement
Behavior of machine, 67                        of a set, 11
Bilinear Hermitian form, 158                   of a matrix, 27
Bilinear function, 201                         of a subspace, 129
Binary relation, 13                         Complete relation, 22
Binary operation, 16                        Composition
Blockmodel, 57                                 of functions, 41
Block form, 134                                of relations, 17
Block triangular form, 136                  Condorcet Paradox, 32
Boolean algebra, 26                         Congruence
Boolean matrix, 27                             of modules, 192
Boolean vector, 32                             of numbers, 174
Burst code, 237                                of rings, 173
                                               of semigroups, 46
                                               of vector spaces, 130
               C                            Conjugacy
Capacity, 86                                   class, 93
Cardinality, 11                                of elements, 93
Cartesian product, 13                       Conjugation, 93
Cayley-Hamilton Theorem, 146                Containment, 10
Center, 74                                  Context-free grammar, 65
Central idempotent, 180                     Coordinates of a projective plane, 246
Chain, 23                                   Coset, 72
262                                  Index
Cycle (permutation), 80                               F
Cyclic code, 233                        F- algebra,   179
Cyclic group, 69                         Family, 10
                                         Field, 120
             D
                                         Filter, 38
Defining relation, 47                    Finite dimensional algebra, 179
Degree                                   Finite dimensional extension, 211
   of extension, 211                     Finite state machine, 60
   of permutation, 68                    Fire code, 237
De Morgan’s laws, 11                     Flow, 86
D-equivalent, 51                         Ford-Fulkerson algorithm, 87
Derivation, 64                           Free group, 69
Desargues’s Theorem, 247                 Free module, 190
Determinant, 47,144                      Free semigroup, 42
Diagonal matrix, 133                     Full matrix, 86
Dictatorial, 34                          Function, 16
Dihedral group, 104
Dimension of vector space, 119,128                    G
Direct product, 70,128                  Galois field, 226
Direct sum, 128                         Galois group, 218
Direct sum of modules, 192              Galois theory, 210, 217
Directed edge, 30                       Generators
Directed graph, 30                         of a field, 212
Disjoint sets, 11                          of a group, 69
Disjoint cycles, 80                        of an ideal, 173
Distributive lattice, 115                  of a semigroup, 45
Distributivity, 11                      Gilbert-Varshamov bound, 232
Divisibility, 166                       Golay code, 231
Division ring, 180                      Gram-Schmidt process, 188
Domain, 16                              Greatest common divisor, 166
Double negative, 11                     Greatest lower bound, 41
Doubly stochastic matrix, 92            Green’s relations, 52
Doubly transitive, 250                  Group
Duality, 100                               abstract, 67
                                           of symmetries, 103
             E                             representation, 187
Eigenvalue, 102,150                         ring, 185
Eigenvector, 103,150
                                                       H
Element, 10
                                         Hall matrix, 84
Elementary symmetric function, 206
Empty set, 11                            Hall-Koenig Theorem, 90
Entry, 27                                Hamming bound, 229
Epimorphism, 77                          Hamming code, 230
Equality of sets, 10                     Hamming distance, 228
                                         Hasse diagram, 24
Equivalence
                                         H-equivalent, 51
   class, 14
                                         Hermitian matrix, 157
   of representations, 187
   relation, 13                          Homogeneous linear equations, 127
                                         Homomorphism
Error-correcting code, 210,227
                                            general, 16
Error-detecting code, 227
                                            of groups, 76
Euler-Fermat Theorem, 176
                                            of modules, 191
Euclidean domain, 168
                                            of semigroups, 47
Euler’s function, 111,176
                                            of vector spaces, 138
Even permutation, 143
Extension field, 211                                   I
Exterior &th power, 204                  Ideal
External direct sum, 128                    generated by x, 173
                                                Index                               263
DATE DUE
 QA162.K55 1983
 Kim, Ki Hang.
 Applied abstract algebra
 PJUM               83000217
                                             OEMCO
Ki Hang Kim is Professor of Mathematics at the
Alabama State University, Alabama, USA. He is a
graduate of the University of Southern Mississippi
with a B.S. and M.S. in Mathematics, to which he
added an M.Phil. and Ph.D. in Mathematics from
the George Washington University. His Ph.D.
dissertation was written under Gian-Carlo Rota
of Massachusetts Institute of Technology.
His first post was as an Instructor at the University
of Hartford, Connecticut, from 1961 to 1966. He
was Lecturer at the George Washington University
for two years, and Associate Professor of St.
Mary's College of Maryland for a further two
years. He became Associate Professor at Pembroke
State University of North Carolina in 1970, and
Research Professor in Alabama State University in
1974. He was also Visiting Professor at the Institute
de Fisica e Matematica, Lisbon, at the University
of Stuttgart and at the Korean Academy of
Sciences in Pyongyang: he is at present also
Director of the Kiro Research Group, Montgomery.
His research interests are discrete mathematics and
mathematical social sciences.
COMPUTATIONAL MATHEMATICS
T. R. F. NONWEILER, Department of Mathematics, Victoria University of Wellington, New
Zealand
An introduction to the mathematical techniques of numerical analysis for those with a
particular interest in performing calculations, whether by using pocket calculators,
microcomputers, or by large digital computers. Covers the familiar ground of introductory
courses in this subject and embodies the attitude that numerical analysis is an experimental
branch of mathematics. Thus the text is free of algebra and algorithms, and describes the wider
context of the elementary mathematical methods.
published by
ELLIS HORWOOD LIMITED
Publishers             Chichester
                                               9780853125631
Ellis Horwood Library Edition ISBN 0-8531207/99/90-1 Q -in-no q
                                                                                                  ??
Ellis Horwood Student Edition ISBN 0-85312          l a I U UU-o
Halsted Press Paperback Edition ISBN 0-470-
                                                                                                            J