Elements of Abstract and Linear Algebra E. H. Connell  ii E.H. Connell Department of Mathematics University of Miami P.O. Box 249085 Coral Gables, Florida 33124 USA ec@math.miami.edu Mathematical Subject Classifications (1991): 12-01, 13-01, 15-01, 16-01, 20-01 01999 E.H. Connell March 20, 2004  iii Introduction In 1965 I first taught an undergraduate course in abstract algebra. It was fun to teach because the material was interesting and the class was outstanding. Five of those students later earned a Ph.D. in mathematics. Since then I have taught the course about a dozen times from various texts. Over the years I developed a set of lecture notes and in 1985 I had them typed so they could be used as a text. They now appear (in modified form) as the first five chapters of this book. Here were some of my motives at the time. 1) To have something as short and inexpensive as possible. In my experience, students like short books. 2) To avoid all innovation. To organize the material in the most simple-minded straightforward manner. 3) To order the material linearly. To the extent possible, each section should use the previous sections and be used in the following sections. 4) To omit as many topics as possible. This is a foundational course, not a topics course. If a topic is not used later, it should not be included. There are three good reasons for this. First, linear algebra has top priority. It is better to go forward and do more linear algebra than to stop and do more group and ring theory. Second, it is more important that students learn to organize and write proofs themselves than to cover more subject matter. Algebra is a perfect place to get started because there are many "easy" theorems to prove. There are many routine theorems stated here without proofs, and they may be considered as exercises for the students. Third, the material should be so fundamental that it be appropriate for students in the physical sciences and in computer science. Zillions of students take calculus and cookbook linear algebra, but few take abstract algebra courses. Something is wrong here, and one thing wrong is that the courses try to do too much group and ring theory and not enough matrix theory and linear algebra. 5) To offer an alternative for computer science majors to the standard discrete mathematics courses. Most of the material in the first four chapters of this text is covered in various discrete mathematics courses. Computer science majors might benefit by seeing this material organized from a purely mathematical viewpoint.  iv Over the years I used the five chapters that were typed as a base for my algebra courses, supplementing them as I saw fit. In 1996 I wrote a sixth chapter, giving enough material for a full first year graduate course. This chapter was written in the same "style" as the previous chapters, i.e., everything was right down to the nub. It hung together pretty well except for the last two sections on determinants and dual spaces. These were independent topics stuck on at the end. In the academic year 1997-98 I revised all six chapters and had them typed in LaTeX. This is the personal background of how this book came about. It is difficult to do anything in life without help from friends, and many of my friends have contributed to this text. My sincere gratitude goes especially to Marilyn Gonzalez, Lourdes Robles, Marta Alpar, John Zweibel, Dmitry Gokhman, Brian Coomes, Huseyin Kocak, and Shulim Kaliman. To these and all who contributed, this book is fondly dedicated. This book is a survey of abstract algebra with emphasis on linear algebra. It is intended for students in mathematics, computer science, and the physical sciences. The first three or four chapters can stand alone as a one semester course in abstract algebra. However they are structured to provide the background for the chapter on linear algebra. Chapter 2 is the most difficult part of the book because groups are written in additive and multiplicative notation, and the concept of coset is confusing at first. After Chapter 2 the book gets easier as you go along. Indeed, after the first four chapters, the linear algebra follows easily. Finishing the chapter on linear algebra gives a basic one year undergraduate course in abstract algebra. Chapter 6 continues the material to complete a first year graduate course. Classes with little background can do the first three chapters in the first semester, and chapters 4 and 5 in the second semester. More advanced classes can do four chapters the first semester and chapters 5 and 6 the second semester. As bare as the first four chapters are, you still have to truck right along to finish them in one semester. The presentation is compact and tightly organized, but still somewhat informal. The proofs of many of the elementary theorems are omitted. These proofs are to be provided by the professor in class or assigned as homework exercises. There is a non-trivial theorem stated without proof in Chapter 4, namely the determinant of the product is the product of the determinants. For the proper flow of the course, this theorem should be assumed there without proof. The proof is contained in Chapter 6. The Jordan form should not be considered part of Chapter 5. It is stated there only as a reference for undergraduate courses. Finally, Chapter 6 is not written primarily for reference, but as an additional chapter for more advanced courses.  V This text is written with the conviction that it is more effective to teach abstract and linear algebra as one coherent discipline rather than as two separate ones. Teach- ing abstract algebra and linear algebra as distinct courses results in a loss of synergy and a loss of momentum. Also with this text the professor does not extract the course from the text, but rather builds the course upon it. I am convinced it is easier to build a course from a base than to extract it from a big book. Because after you extract it, you still have to build it. The bare bones nature of this book adds to its flexibility, because you can build whatever course you want around it. Basic algebra is a subject of incredible elegance and utility, but it requires a lot of organization. This book is my attempt at that organization. Every effort has been extended to make the subject move rapidly and to make the flow from one topic to the next as seamless as possible. The student has limited time during the semester for serious study, and this time should be allocated with care. The professor picks which topics to assign for serious study and which ones to "wave arms at". The goal is to stay focused and go forward, because mathematics is learned in hindsight. I would have made the book shorter, but I did not have any more time. When using this text, the student already has the outline of the next lecture, and each assignment should include the study of the next few pages. Study forward, not just back. A few minutes of preparation does wonders to leverage classroom learning, and this book is intended to be used in that manner. The purpose of class is to learn, not to do transcription work. When students come to class cold and spend the period taking notes, they participate little and learn little. This leads to a dead class and also to the bad psychology of "O K, I am here, so teach me the subject." Mathematics is not taught, it is learned, and many students never learn how to learn. Professors should give more direction in that regard. Unfortunately mathematics is a difficult and heavy subject. The style and approach of this book is to make it a little lighter. This book works best when viewed lightly and read as a story. I hope the students and professors who try it, enjoy it. E. H. Connell Department of Mathematics University of Miami Coral Gables, FL 33124 ec~math.miami.edu  vi Outline Chapter 1 Background and Fundamentals of Mathematics Sets, Cartesian products 1 Relations, partial orderings, Hausdorff maximality principle, 3 equivalence relations Functions, bijections, strips, solutions of equations, 5 right and left inverses, projections Notation for the logic of mathematics 13 Integers, subgroups, unique factorization 14 Chapter 2 Groups Groups, scalar multiplication for additive groups 19 Subgroups, order, cosets 21 Normal subgroups, quotient groups, the integers mod n 25 Homomorphisms 27 Permutations, the symmetric groups 31 Product of groups 34 Chapter 3 Rings Rings 37 Units, domains, fields 38 The integers mod n 40 Ideals and quotient rings 41 Homomorphisms 42 Polynomial rings 45 Product of rings 49 The Chinese remainder theorem 50 Characteristic 50 Boolean rings 51 Chapter 4 Matrices and Matrix Rings Addition and multiplication of matrices, invertible matrices 53 Transpose 56 Triangular, diagonal, and scalar matrices 56 Elementary operations and elementary matrices 57 Systems of equations 59  vii Determinants, the classical adjoint 60 Similarity, trace, and characteristic polynomial 64 Chapter 5 Linear Algebra Modules, submodules 68 Homomorphisms 69 Homomorphisms on R" 71 Cosets and quotient modules 74 Products and coproducts 75 Summands 77 Independence, generating sets, and free basis 78 Characterization of free modules 79 Uniqueness of dimension 82 Change of basis 83 Vector spaces, square matrices over fields, rank of a matrix 85 Geometric interpretation of determinant 90 Linear functions approximate differentiable functions locally 91 The transpose principle 92 Nilpotent homomorphisms 93 Eigenvalues, characteristic roots 95 Jordan canonical form 96 Inner product spaces, Gram-Schmidt orthonormalization 98 Orthogonal matrices, the orthogonal group 102 Diagonalization of symmetric matrices 103 Chapter 6 Appendix The Chinese remainder theorem 108 Prime and maximal ideals and UFDS 109 Splitting short exact sequences 114 Euclidean domains 116 Jordan blocks 122 Jordan canonical form 123 Determinants 128 Dual spaces 130  viii 1 2 3 4 5 6 7 8 9 11 10 Abstract algebra is not only a major subject of science, but it is also magic and fun. Abstract algebra is not all work and no play, and it is certainly not a dull boy. See, for example, the neat card trick on page 18. This trick is based, not on sleight of hand, but rather on a theorem in abstract algebra. Anyone can do it, but to understand it you need some group theory. And before beginning the course, you might first try your skills on the famous (some would say infamous) tile puzzle. In this puzzle, a frame has 12 spaces, the first 11 with numbered tiles and the last vacant. The last two tiles are out of order. Is it possible to slide the tiles around to get them all in order, and end again with the last space vacant? After giving up on this, you can study permutation groups and learn the answer!  Chapter 1 Background and Fundamentals of Mathematics This chapter is fundamental, not just for algebra, but for all fields related to mathe- matics. The basic concepts are products of sets, partial orderings, equivalence rela- tions, functions, and the integers. An equivalence relation on a set A is shown to be simply a partition of A into disjoint subsets. There is an emphasis on the concept of function, and the properties of surjective, injective, and bijective. The notion of a solution of an equation is central in mathematics, and most properties of functions can be stated in terms of solutions of equations. In elementary courses the section on the Hausdorff Maximality Principle should be ignored. The final section gives a proof of the unique factorization theorem for the integers. Notation Mathematics has its own universally accepted shorthand. The symbol means "there exists" and E! means "there exists a unique". The symbol V means "for each" and - means "implies". Some sets (or collections) are so basic they have their own proprietary symbols. Five of these are listed below. N = Z+ = the set of positive integers = {1, 2, 3, ...} Z = the ring of integers = {..., -2, -1, 0, 1, 2, ...} Q = the field of rational numbers = {a/b: a, b E Z, b / 0} R = the field of real numbers C = the field of complex numbers = {a + bi : a, b E R} (i2 -1) Sets Suppose A, B, C,... are sets. We use the standard notation for intersection and union. A n B = {x : x E A and x E B} = the set of all x which are elements 1  2 Background Chapter 1 of A and B. A U B = {x : x E A or x E B} = the set of all x which are elements of A or B. Any set called an index set is assumed to be non-void. Suppose T is an index set and for each t E T , At is a set. U A {x: E t E T with x E At} tET OA= {x : if t ET, E At} ={x :Vt T, zc At} tET Let 0 be the null set. If A n B = 0, then A and B are said to be disjoint. Definition Suppose each of A and B is a set. The statement that A is a subset of B (A C B) means that if a is an element of A, then a is an element of B. That is, a E A a E B. If A c B we may say A is contained in B, or B contains A. Exercise Suppose each of A and B is a set. The statement that A is not a subset of B means Theorem (De Morgan's laws) Suppose S is a set. If C C S (i.e., if C is a subset of S), let C', the complement of C in S, be defined by C' = S - C = {x E S : x C}. Then for any A, B C S, (AonB)'=A'uB' and (A u B)' =A' n B' Cartesian Products If X and Y are sets, X x Y {(x, y) : xE X and y E Y}. In other words, the Cartesian product of X and Y is defined to be the set of all ordered pairs whose first term is in X and whose second term is in Y. Example R x R = R2 = the plane.  Chapter 1 Background 3 Definition If each of X1, ..., Xn is a set, X1 x - - -"x Xn ={(zi, ..., zx) : x2 E Xi for 1 < i < n} = the set of all ordered n-tuples whose i-th term is in Xi. Example Question R x ... x R = R =real n-space. Is (RxR2)=(R2xR)=R3? Relations If A is a non-void set, a non-void subset R C A x A is called a relation on A. If (a, b) E R we say that a is related to b, and we write this fact by the expression a b. Here are several properties which a relation may possess. 1) 2) 2') 3) If a E A, then a a. Ifa~b, then b~a. If a b and b a, then If a b and b c, then (reflexive) (symmetric) a = b. (anti-symmetric) a c. (transitive) Definition A relation which satisfies 1), 2'), and 3) is called a partial ordering. In this case we write a b as a < b. Then 1) 2') 3) If a E A, then a < a. Ifa f (Xi) # f (x2), i.e., if zi and X2 are distinct elements of X, then f(xi) and f(X2) are distinct elements of Y. 6) f : X - Y is bijective or is a 1-1 correspondence provided f is surjective and injective. In this case, there is function f-1 : Y - X with f-1 o f Ix : X e X and f o f-1 = Iy : Y -Y. Note that f -1 : Y - X is also bijective and (f-1)-1 = f. Examples 1) f : R - R defined by f(x) = sin(x) is neither surjective nor injective. 2) f : R - [-1, 1] defined by f (x) = sin(x) is surjective but not injective. 3) f : [0, 7/2] - R defined by f (x) = sin(x) is injective but not surjective. 4) f : [0, 7/2] - [0, 1] defined by f (x) = sin(x) is bijective. (f-1(x) is written as arcsin(x) or sin-1(z).) 5) f :R - (0, ooD) defined by f (z) =ex is bijective. (f-1(zc) is written as ln(xc).) Note There is no such thing as "the function sin(xc)." A function is not defined unless the domain and range are specified.  8 Background Chapter 1 Exercise Show there are natural bijections from (R x R2) to (R2 x R) and from (R2 x R) to R x R x R. These three sets are disjoint, but the bijections between them are so natural that we sometimes identify them. Exercise Suppose X is a set with 6 elements and Y is a finite set with n elements. 1) There exists an injective f : X - Y iff n 2) There exists a surjective f : X - Y iff n 3) There exists a bijective f : X - Y iff n Pigeonhole Principle Suppose X is a finite set with m elements, Y is a finite set with n elements, and f : X - Y is a function. 1) If m = n, then f is injective iff f is surjective iff f is bijective. 2) If m > n, then f is not injective. 3) If m < n, then f is not surjective. If you are placing 6 pigeons in 6 holes, and you run out of pigeons before you fill the holes, then you have placed 2 pigeons in one hole. In other words, in part 1) for m = n = 6, if f is not surjective then f is not injective. Of course, the pigeonhole principle does not hold for infinite sets, as can be seen by the following exercise. Exercise Show there is a function f Z+ - Z+ which is injective but not surjective. Also show there is one which is surjective but not injective. Exercise Suppose f: [-2, 2] - R is defined by f (x) = x2. Find f1(f([1, 2])). Also find f (f -1([3, 5])). Exercise Suppose f X -- Y is a function, S C X and T C Y. Find the relationship between S and f1(f(S)). Show that if f is injective, S = f1(f(S)). Also find the relationship between T and f(f1(T)). Show that if f is surjective, T = f (f -1(T)). Strips We now define the vertical and horizontal strips of X x Y. If zco E X, {(zo, y) :y E Y} =(ao x Y) is called a vertical strip. If yo E Y, {(x, yo) :c E X} =(X x yo) is called a horizontal strip.  Chapter 1 Background 9 Theorem Suppose S C X x Y. The subset S is the graph of a function with domain X and range Y iff each vertical strip intersects S in exactly one point. This is just a restatement of the property of a graph of a function. The purpose of the next theorem is to restate properties of functions in terms of horizontal strips. Theorem Suppose f : X - Y has graph F. Then 1) Each horizontal strip intersects F in at least one point iff f is . 2) Each horizontal strip intersects F in at most one point iff f is . 3) Each horizontal strip intersects F in exactly one point iff f is . Solutions of Equations Now we restate these properties in terms of solutions of equations. Suppose f : X - Y and yo E Y. Consider the equation f (x) = yo. Here yo is given and x is considered to be a "variable". A solution to this equation is any xo E X with f(xo) = yo. Note that the set of all solutions to f(x) = yo is f-(yo). Also f(x) = yo has a solution iff yo E image(f) iff f-(yo) is non-void. Theorem Suppose f : X - Y. 1) The equation f(x) = yo has at least one solution for each yo E Y iff f is 2) The equation f(x) = yo has at most one solution for each yo E Y iff f is 3) The equation f(x) = yo has a unique solution for each yo E Y iff f is Right and Left Inverses One way to understand functions is to study right and left inverses, which are defined after the next theorem. Theorem Suppose X -$ Y -4 W are functions. 1) If g o f is injective, then f is injective.  10 Background Chapter 1 2) If g o f is surjective, then g is surjective. 3) If g o f is bijective, then f is injective and g is surjective. Example X = W = {p}, Y = {p, q}, f (p) = p, and g(p) = g(q) = p. Here g o f is the identity, but f is not surjective and g is not injective. Definition Suppose f X - Y is a function. A left inverse of f is a function g :Y - X such that g o f = Ix : X - X. A right inverse of f is a function h :Y - X such that f o h Iy Y - Y. Theorem Suppose f : X - Y is a function. 1) f has a right inverse iff f is surjective. Any such right inverse must be injective. 2) f has a left inverse iff f is injective. Any such left inverse must be surjective. Corollary Suppose each of X and Y is a non-void set. Then E an injective f : X -- Y iff E a surjective g : Y - X. Also a function from X to Y is bijective iff it has a left inverse and a right inverse iff it has a left and right inverse. Note The Axiom of Choice is not discussed in this book. However, if you worked 1) of the theorem above, you unknowingly used one version of it. For completeness, we state this part of 1) again. The Axiom of Choice If f X - Y is surjective, then f has a right inverse h. That is, for each y E Y, it is possible to choose an x E f1(y) and thus to define h(y) = x. Note It is a classical theorem in set theory that the Axiom of Choice and the Hausdorff Maximality Principle are equivalent. However in this text we do not go that deeply into set theory. For our purposes it is assumed that the Axiom of Choice and the HMP are true. Exercise Suppose f : X - Y is a function. Define a relation on X by a ~ b if f(a) = f(b). Show this is an equivalence relation. If y belongs to the image of f, then f-1(y) is an equivalence class and every equivalence class is of this form. In the next chapter where f is a group homomorphism, these equivalence classes will be called cosets.  Chapter 1 Background 11 Projections If X1 and X2 are non-void sets, we define the projection maps 11: X1 x X2 X1 and 72 : X1 x X2 X2 by ri(zi, x2) = z. Theorem If Y, X1, and X2 are non-void sets, there is a 1-1 correspondence between {functions f: Y - X1 x X2} and {ordered pairs of functions (fi, f2) where fi: Y - X1 and f2 : Y -_ X2}. Proof Given f, define fi =711 o f and f2 = 72 o f. Given fi and f2 define f : Y -_ X1 x X2 by f(y) = (fi(y), f2(y)). Thus a function from Y to 1 x X2 is merely a pair of functions from Y to X1 and Y to X2. This concept is displayed in the diagram below. It is summarized by the equation f = (fi, f2). Y fi {f f2 X1 -A71 x AX2 72,X2 One nice thing about this concept is that it works fine for infinite Cartesian products. Definition Suppose T is an index set and for each t E T, Xt is a non-void set. Then the product HAXt=t H X is the collection of all sequences {zt}tET {mt} tET where it E Xt. Formally these sequences are functions a from T to U Xt with each a(t) in Xt and written as a(t) = Xt. If T = {1, 2, ... , n} then {xt} is the ordered n-tuple (zi, X2, ... , x). If T = Z+ then {Xt} is the sequence (zi, x2,. ...). For any T and any s in T, the projection map s : H Xt - X is defined by ors({zt}) = ze. Theorem If Y is any non-void set, there is a 1-1 correspondence between {functions f : Y -- H Xt} and {sequences of functions {ft}tET where ft : Y - Xt}. Given f, the sequence {ft} is defined by ft =Wat o f. Given {ft}, f is defined by f (y) ={ft(y)}.  12 Background Chapter 1 A Calculus Exercise Let A be the collection of all functions f [0, 1] - R which have an infinite number of derivatives. Let AO C A be the subcollection of those functions f with f(0) = 0. Define D: AO - A by D(f) = df/dx. Use the mean value theorem to show that D is injective. Use the fundamental theorem of calculus to show that D is surjective. Exercise This exercise is not used elsewhere in this text and may be omitted. It is included here for students who wish to do a little more set theory. Suppose T is a non-void set. 1) If Y is a non-void set, define yT to be the collection of all functions with domain T and range Y. Show that if T and Y are finite sets with m and n elements, then yT has nm elements. In particular, when T = {1, 2, 3}, yT = Y x Y x Y has n3 elements. Show that if n ;> 3, the subset of Y{1,2,3} of all injective functions has n(n - 1)(n - 2) elements. These injective functions are called permutations on Y taken 3 at a time. If T = N, then yT is the infinite product Y x Y x - - - . That is, yN is the set of all infinite sequences (yi, y2, ...) where each y2 E Y. For any Y and T, let Yt be a copy of Y for each t E T. Then YT = H Yt. tET 2) Suppose each of Y1 and Y2 is a non-void set. Show there is a natural bijection from (Y1 x Y2)T to YT x Y2T. (This is the fundamental property of Cartesian products presented in the two previous theorems.) 3) Define P(T), the power set of T, to be the collection of all subsets of T (including the null set). Show that if T is a finite set with m elements, P(T) has 2' elements. 4) If S is any subset of T, define its characteristic function x: T - {0, 1} by letting x/(t) be 1 when t E S, and be 0 when t $ S. Define a : P(T) - {0, 1}T by a(S) =x. Define 3: {0,1}T -- P(T) by /3(f) = f-1(1). Show that if S c T then 13o a(S) = S, and if f : T -- {0, 1} then a o/#(f) = f. Thus a is a bijection and P(T) f> {0,1}T 5) Suppose - : T -- {0, 1}T is a function and show that it cannot be surjective. If t E T, denote 1(t) by 1(t) = ft : T -- {0, 1}. Define f : T -- {0, 1} by f(t) = 0 if ft(t) = 1, and f(t) = 1 if ft(t) = 0. Show that f is not in the image of m and thus m cannot be surjective. This shows that if T is an infinite set, then the set {0, 1}T represents a "higher order of infinity than T". 6) An infinite set Y is said to be countable if there is a bijection from the positive  Chapter 1 Background 13 integers N to Y. Show Q is countable but the following three collections are not. i) P(N), the collection of all subsets of N. ii) {0, 1}N, the collection of all functions f: N - {0, 1}. iii) The collection of all sequences (Yi, Y2, ...) where each yZ is 0 or 1. We know that ii) and iii) are equal and there is a natural bijection between i) and ii). We also know there is no surjective map from N to {0, 1}N, i.e., {0, 1}N is uncountable. Finally, show there is a bijection from {0, 1}N to the real numbers R. (This is not so easy. To start with, you have to decide what the real numbers are.) Notation for the Logic of Mathematics Each of the words "Lemma", "Theorem", and "Corollary" means "true state- ment". Suppose A and B are statements. A theorem may be stated in any of the following ways: Theorem Hypothesis Statement A. Conclusion Statement B. Theorem Suppose A is true. Then B is true. Theorem If A is true, then B is true. Theorem A * B (A implies B ). There are two ways to prove the theorem to suppose A is true and show B is true, or to suppose B is false and show A is false. The expressions "A < B", "A is equivalent to B", and "A is true iff B is true " have the same meaning (namely, that A=> BandB * A). The important thing to remember is that thoughts and expressions flow through the language. Mathematical symbols are shorthand for phrases and sentences in the English language. For example, "x E B " means "x is an element of the set B." If A is the statement "x E Z+" and B is the statement "x2 E Z+", then "A B" means "If x is a positive integer, then x2 is a positive integer". Mathematical Induction is based upon the fact that if S c Z+ is a non-void subset, then S contains a smallest element.  14 Background Chapter 1 Theorem Suppose P(n) is a statement for each n = 1, 2,... . Suppose P(1) is true and for each n > 1, P(n) - P(nm+ 1). Then for each n 1, P(n) is true. Proof If the theorem is false, then E a smallest positive integer m such that P(m) is false. Since P(m - 1) is true, this is impossible. Exercise Use induction to show that, for each n 1, 1+2+ -- -+n = n(n+1)/2. The Integers In this section, lower case letters a, b, c, ... will represent integers, i.e., elements of Z. Here we will establish the following three basic properties of the integers. 1) If G is a subgroup of Z, then E n > 0 such that G = nZ. 2) If a and b are integers, not both zero, and G is the collection of all linear combinations of a and b, then G is a subgroup of Z, and its positive generator is the greatest common divisor of a and b. 3) If n > 2, then n factors uniquely as the product of primes. All of this will follow from long division, which we now state formally. Euclidean Algorithm Given a, b with b / 0, E! m and r with 0 < r <|b| and a = bm + r. In other words, b divides a "m times with a remainder of r". For example, if a = -17 and b = 5, then m = -4 and r = 3, -17 = 5(-4) + 3. Definition If r = 0, we say that b divides a or a is a multiple of b. This fact is written as b a. Note that b| a the rational number a/b is an integer l! m such that a = bm a E bZ. Note Anything (except 0) divides 0. 0 does not divide anything. + 1 divides anything . If n / 0, the set of integers which n divides is nZ = {nm : m E Z} =_{..., -2n, -n, 0, n, 2n, ...}. Also n divides a and b with the same remainder iff n divides (a - b). Definition A non-void subset C c Z is a subgroup provided (g E C -> -g E C) and (gi, g2 E C -> (g1 +g2) E C). We say that C is closed under negation and closed under addition.  Chapter 1 Background 15 Theorem If n E Z then nZ is a subgroup. Thus if n / 0, the set of integers which n divides is a subgroup of Z. The next theorem states that every subgroup of Z is of this form. Theorem Suppose G C Z is a subgroup. Then 1) 0EG. 2) If gi and g2 E G, then (migi + m2g2) E G for all integers mi, m2. 3) E! non-negative integer n such that G = nZ. In fact, if G / {0} and n is the smallest positive integer in G, then G = nZ. Proof Since G is non-void, E g E G. Now (-g) E G and thus 0 = g + (-g) belongs to G, and so 1) is true. Part 2) is straightforward, so consider 3). If G / 0, it must contain a positive element. Let n be the smallest positive integer in G. If g E G, g = nm+r where 0 < r n =+1.  16 Background Chapter 1 2) (a, b) = 1, i.e., the subgroup generated by a and b is all of Z. 3) Elm,n EZ with ma +nb =1. Definition If any one of these three conditions is satisfied, we say that a and b are relatively prime. This next theorem is the basis for unique factorization. Theorem If a and b are relatively prime with a not zero, then albc -> ac. Proof Suppose a and b are relatively prime, c E Z and a | bc. Then there exist m, n with ma + nb = 1, and thus mac + nbc = c. Now a | mac and a |Inbc. Thus a | (mac + nbc) and so a | c. Definition A prime is an integer p > 1 which does not factor, i.e., if p = ab then a = +1 or a = tp. The first few primes are 2, 3, 5, 7, 11, 13, 17,... . Theorem Suppose p is a prime. 1) If a is an integer which is not a multiple of p, then (p, a) = 1. In other words, if a is any integer, (p, a) = p or (p, a) = 1. 2) If p| ab then p | aor p| b. 3) If p aia2 - - - an then p divides some a2. Thus if each a2 is a prime, then p is equal to some a2. Proof Part 1) follows immediately from the definition of prime. Now suppose p | ab. If p does not divide a, then by 1), (p, a) = 1 and by the previous theorem, p must divide b. Thus 2) is true. Part 3) follows from 2) and induction on n. The Unique Factorization Theorem Suppose a is an integer which is not 0,1, or -1. Then a may be factored into the product of primes and, except for order, this factorization is unique. That is, E a unique collection of distinct primes Pi, p2, ..., Pk and positive integers si, s2, ..., sk such that a =+tplpg2 - - . p k. Proof Factorization into primes is obvious, and uniqueness follows from 3) in the theorem above. The power of this theorem is uniqueness, not existence.  Chapter 1 Background 17 Now that we have unique factorization and part 3) above, the picture becomes transparent. Here are some of the basic properties of the integers in this light. Theorem (Summary) 1) Suppose lIa|> 1 has prime factorization a = tpl ... p"k . Then the only divisors of a are of the form tpl -"- - pt where 0 < ft si for i = 1, ..., k. 2) If I a > 1 and | b > 1, then (a, b) = 1 iff there is no common prime in their factorizations. Thus if there is no common prime in their factorizations, E m, n with ma + nb = 1, and also (a2, b2)=1. 3) Suppose lIa|> 1 and |bl> 1. Let {pi,... , Pk} be the union of the distinct primes of their factorizations. Thus a = tpi -"-- p,k where 0 < s2 and b =tpl . . . p where 0 < ti. Let u2 be the minimum of s2 and t2. Then (ab) = pi"1 -"-"-"p$k . For example (23 - 5 - 11, 22.54 - 7) = 22 - 5. 3') Let v2 be the maximum of s2 and t2. Then c = pp... pik is the least (positive) common multiple of a and b. Note that c is a multiple of a and b, and if n is a multiple of a and b, then n is a multiple of c. Finally, if a and b are positive, their least common multiple is c = ab/(a, b), and if in addition a and b are relatively prime, then their least common multiple is just their product. 4) There is an infinite number of primes. (Proof: Suppose there were only a finite number of primes pi, p2, ..., Pk. Then no prime would divide (pip2 .pk +1).) 5) Suppose c is an integer greater than 1. Then c is rational iff c is an integer. In particular, 2 and 3 are irrational. (Proof: If c is rational, E positive integers a and b with /= a/b and (a, b) = 1. If b > 1, then it is divisible by some prime, and since cb2 = a2, this prime will also appear in the prime factorization of a. This is a contradiction and thus b = 1 and c is an integer.) (See the fifth exercise below.) Exercise Find (180,28), i.e., find the greatest common divisor of 180 and 28, i.e., find the positive generator of the subgroup generated by {180,28}. Find integers m and ni such that 180m + 28nm (180, 28). Find the least common multiple of 180 and 28, and show that it is equal to (180.- 28)7(180, 28).  18 Background Chapter 1 Exercise We have defined the greatest common divisor (gcd) and the least com- mon multiple (1cm) of a pair of integers. Now suppose n > 2 and S = {ai, a2, .., an} is a finite collection of integers with laIl > 1 for 1 < i <1n. Define the gcd and the lcm of the elements of S and develop their properties. Express the gcd and the lcm in terms of the prime factorizations of the a2. When is the lcm of S equal to the product a1a2.. an? Show that the set of all linear combinations of the elements of S is a subgroup of Z, and its positive generator is the gcd of the elements of S. Exercise Show that the gcd of S = {90, 70, 42} is 2, and find integers ni, n2, n3 such that 90ni + 70n2 + 42n3 = 2. Also find the lcm of the elements of S. Exercise Show that if each of G1, G2, ..., Gm is a subgroup of Z, then G1 n G2 n" n Gm is also a subgroup of Z. Now let G = (90Z) n (70Z) n (42Z) and find the positive integer n with G = nZ. Exercise Show that if the nth root of an integer is a rational number, then it itself is an integer. That is, suppose c and n are integers greater than 1. There is a unique positive real number x with x" = c. Show that if x is rational, then it is an integer. Thus if p is a prime, its nth root is an irrational number. Exercise Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3. More generally, let a = anan_1 ... ao = an10" + an_110"-1 + - - - + ao where 0 < a2 <9. Now let b = an + an-1 + - - - + ao, and show that 3 divides a and b with the same remainder. Although this is a straightforward exercise in long division, it will be more transparent later on. In the language of the next chapter, it says that [a] = [b] in Z3. Card Trick Ask friends to pick out seven cards from a deck and then to select one to look at without showing it to you. Take the six cards face down in your left hand and the selected card in your right hand, and announce you will place the selected card in with the other six, but they are not to know where. Put your hands behind your back and place the selected card on top, and bring the seven cards in front in your left hand. Ask your friends to give you a number between one and seven (not allowing one). Suppose they say three. You move the top card to the bottom, then the second card to the bottom, and then you turn over the third card, leaving it face up on top. Then repeat the process, moving the top two cards to the bottom and turning the third card face up on top. Continue until there is only one card face down, and this will be the selected card. Magic? Stay tuned for Chapter 2, where it is shown that any non-zero element of Z7 has order 7.  Chapter 2 Groups Groups are the central objects of algebra. In later chapters we will define rings and modules and see that they are special cases of groups. Also ring homomorphisms and module homomorphisms are special cases of group homomorphisms. Even though the definition of group is simple, it leads to a rich and amazing theory. Everything presented here is standard, except that the product of groups is given in the additive notation. This is the notation used in later chapters for the products of rings and modules. This chapter and the next two chapters are restricted to the most basic topics. The approach is to do quickly the fundamentals of groups, rings, and matrices, and to push forward to the chapter on linear algebra. This chapter is, by far and above, the most difficult chapter in the book, because group operations may be written as addition or multiplication, and also the concept of coset is confusing at first. Definition Suppose G is a non-void set and #: G x G - -G is a function. # is called a binary operation, and we will write #(a, b) = a - b or #(a, b) = a+b. Consider the following properties. 1) If a, b, c E G then a - (b - c) = (a - b) - c. If a, b, c E G then a + (b+ c) = (a + b) + c. 2) : e =eG E G such that if a E G ElQ=0G E G such that if a E G e-a=a-e=a. O+a=a+0=a. 3) IfaEG, b EGwitha-b=b-a=e IfaEG, 2bEGwith a+b=b+a=0 (b is written as b = a-1). (b is written as b = -a). 4) If a, b E G, then a - b = b - a. If a, b E G, then a + b = b + a. Definition If properties 1), 2), and 3) hold, (G, #) is said to be a group. If we write #(a, b) = a - b, we say it is a multiplicative group. If we write #(a, b) = a + b, 19  20 Groups Chapter 2 we say it is an additive group. If in addition, property 4) holds, we say the group is abelian or commutative. Theorem Let (G, #) be a multiplicative group. (i) Suppose a, c,Jc E G. Then a - c = a-c c =c. Also c-a = -a c=c. In other words, if f : G - G is defined by f(c) = a - c, then f is injective. Also f is bijective with f -1 given by f -1(c) = a-1 - c. (ii) e is unique, i.e., if e E G satisfies 2), then e = C. In fact, ifa,bEG then (a.b=a) 4 (b=e) and (a.b=b) 4 (a=e). Recall that b is an identity in G provided it is a right and left identity for any a in G. However, group structure is so rigid that if I a E G such that b is a right identity for a, then b = e. Of course, this is just a special case of the cancellation law in (i). (iii) Every right inverse is an inverse, i.e., if a - b = e then b = a-1. Also if b - a = e then b = a-1. Thus inverses are unique. (iv) If a E G, then (a-1)-1 = a. (v) The multiplication ai1- a2 a3=- ai- (a2 sa3)- (a1 - a2) a3 is well-defined. In general, ai1- a2.-.-.- an is well defined. (vi) If a, b E G, (a - b)-1 = b-1-"a-1. Also (a1 - a2 an)-1 = a-1 -1 -i---a-1. (vii) Suppose a E G. Let a0 = e and if n > 0, a" = a - - - a (ntimes) and a-" = a-1" -"-"-a-1 (ntimes). Ifni, n2, ...,mnt E Z then a"1.ant2-...ata=a1±+...+t. Also (aTh)m=anm. Finally, if G is abelian and a, b E G, then (a.- b)" = a"- b". Exercise. Write out the above theorem where G is an additive group. Note that part (vii) states that G has a scalar multiplication over Z. This means that if a is in G and n is an integer, there is defined an element an in G. This is so basic, that we state it explicitly. Theorem. Suppose C is an additive group. If a E C, let a0 =0 and if ni > 0, let anm (a - - +a) where the sum is n times, and a(-n) =(-a) + (-a) --+ (-a),  Chapter 2 Groups 21 which we write as (-a - a - - - a). Then the following properties hold in general, except the first requires that G be abelian. (a + b)n a(n + m) a(nm) al an + bn an + am (an)m a Note that the plus sign is used ambiguously sometimes for addition in G and sometimes for addition in Z. In the language used in Chapter 5, this theorem states that any additive abelian group is a Z-module. (See page 71.) Exercise Suppose G is a non-void set with a binary operation #(a, b) = a - b which satisfies 1), 2) and [ 3') If a E G, b E G with a - b = e]. Show (G, #) is a group, i.e., show b - a = e. In other words, the group axioms are stronger than necessary. If every element has a right inverse, then every element has a two sided inverse. Exercise Suppose G is the set of all functions from Z to Z with multiplication defined by composition, i.e., f - g =f o g. Note that G satisfies 1) and 2) but not 3), and thus G is not a group. Show that f has a right inverse in G iff f is surjective, and f has a left inverse in G iff f is injective (see page 10). Also show that the set of all bijections from Z to Z is a group under composition. Examples Examples G = R, G=Q, or G=Z with #(a, b) = a + b is an additive abelian group. G = R - 0 or G = Q - 0 with #(a, b) = ab is a multiplicative abelian group. G = Z - 0 with #(a, b) = ab is not a group. G = R+ = {r E R : r > 0} with #(a, b) = ab is a multiplicative abelian group. Subgroups Suppose G is a multiplicative group and H C G is a non-void subset Theorem satisfying 1) if a,b E H then a-b E H 2) if a E H then a-1 E H. and  22 Groups Chapter 2 Then e E H and H is a group under multiplication. H is called a subgroup of G. Proof Since H is non-void, da E H. By 2), a-1 E H and so by 1), e E H. The associative law is immediate and so H is a group. Example G is a subgroup of G and e is a subgroup of G. These are called the improper subgroups of G. Example If G = Z under addition, and n E Z, then H = nZ is a subgroup of Z. By a theorem in the section on the integers in Chapter 1, every subgroup of Z is of this form (see page 15). This is a key property of the integers. Exercises Suppose G is a multiplicative group. 1) Let H be the center ofCG, i.e.,H = {he G : g - h = h - g for all g E G}. Show H is a subgroup of G. 2) Suppose H1 and H2 are subgroups of G. Show H1 0 H2 is a subgroup of G. 3) Suppose H1 and H2 are subgroups of G, with neither H1 nor H2 contained in the other. Show H1 U H2 is not a subgroup of G. 4) Suppose T is an index set and for each t E T, Ht is a subgroup of G. Show Ht is a subgroup of G. tET 5) Furthermore, if {Ht} is a monotonic collection, then U Ht is a subgroup of G. tET 6) Suppose G= {all functions f : [0, 1] -- R}. Define an addition on G by (f + g)(t) = f(t) + g(t) for all t E [0, 1]. This makes G into an abelian group. Let K be the subset of G composed of all differentiable functions. Let H be the subset of G composed of all continuous functions. What theorems in calculus show that H and K are subgroups of G? What theorem shows that K is a subset (and thus subgroup) of H? Order Suppose G is a multiplicative group. If G has an infinite number of  Chapter 2 Groups 23 elements, we say that o(G), the order of G, is infinite. If G has n elements, then o(G) = n. Suppose a E G and H = {a2 : i E Z}. H is an abelian subgroup of G called the subgroup generated by a. We define the order of the element a to be the order of H, i.e., the order of the subgroup generated by a. Let f: Z - H be the surjective function defined by f(m) = am. Note that f(k + 1) = f(k) - f(l) where the addition is in Z and the multiplication is in the group H. We come now to the first real theorem in group theory. It says that the element a has finite order iff f is not injective, and in this case, the order of a is the smallest positive integer n with a" = e. Theorem Suppose a is an element of a multiplicative group G, and H = {a2 : i E Z}. If E distinct integers i and j with a = a3, then a has some finite order n. In this case H has n distinct elements, H = {a0, al, ... , a"-1}, and am e iff n m. In particular, the order of a is the smallest positive integer n with a" = e, and f -1(e) = nZ. Proof Suppose j < i and a2 = a3. Then a2-j = e and thus E a smallest positive integer n with a" = e. This implies that the elements of {a0, a1, ..., a"-1} are distinct, and we must show they are all of H. If m E Z, the Euclidean algorithm states that 2integers q and r with 0 < r < n and m = nq + r. Thus am = a"4 - a' = ar, and so H = {a°, al, ..., a"-1}, and am = e iff n1m. Later in this chapter we will see that f is a homomorphism from an additive group to a multiplicative group and that, in additive notation, H is isomorphic to Z or Z,. Exercise Write out this theorem for G an additive group. To begin, suppose a is an element of an additive group G, and H = {ai : i E Z}. Exercise Show that if G is a finite group of even order, then G has an odd number of elements of order 2. Note that e is the only element of order 1. Definition A group G is cyclic if E an element of G which generates G. Theorem If G is cyclic and H is a subgroup of G, then H is cyclic. Proof Suppose G = {a2 : i E Z} is a cyclic group and H is a subgroup of G. If H = e, then H is cyclic, so suppose H f e. Now there is a small- est positive integer m with am E H. If t is an integer with at E H, then by the Euclidean algorithm, m divides t, and thus am generates H. Note that in the case G has finite order n, i.e., G = {a0, a1,....,a"-1}, then a" = e E H, and thus the positive integer m divides ni. In either case, we have a clear picture of the subgroups of C. Also note that this theorem was proved on page 15 for the additive group Z.  24 Groups Chapter 2 Cosets Suppose H is a subgroup of a group G. It will be shown below that H partitions G into right cosets. It also partitions G into left cosets, and in general these partitions are distinct. Theorem If H is a subgroup of a multiplicative group G, then a b defined by a ~ b iff a b-1 E H is an equivalence relation. If a E G, cl(a)={b E G : a b} {h. a : h E H} = Ha. Note that a - b-1 E H iffb - a-1 E H. If H is a subgroup of an additive group G, then a ~ b defined by a b iff (a - b) E H is an equivalence relation. If a E G, cl(a) = {b E G : a ~ b} = {h + a: h E H} = H + a. Note that (a - b) E H iff(b-a) E H. Definition These equivalence classes are called right cosets. If the relation is defined by a ~ b iff b-1 - a E H, then the equivalence classes are cl(a) = aH and they are called left cosets. H is a left and right coset. If G is abelian, there is no distinction between right and left cosets. Note that b-1 -"a E H iff a-1 -b E H. In the theorem above, H is used to define an equivalence relation on G, and thus a partition of G. We now do the same thing a different way. We define the right cosets directly and show they form a partition of G. You might find this easier. Theorem Suppose H is a subgroup of a multiplicative group G. If a E G, define the right coset containing a to be Ha = {h. a : h E H}. Then the following hold. 1) Ha=H iff aEH. 2) If b E Ha, then Hb =Ha, i.e., if h E H,then H(h-a)=(Hh)a =Ha. 3) If Hcn Ha#f 0, then Hc= Ha. 4) The right cosets form a partition of G, i.e., each a in G belongs to one and only one right coset. 5) Elements a and b belong to the same right coset iff a b-1 E H iff b- a-1 E H. Proof There is no better way to develop facility with cosets than to prove this theorem. Also write this theorem for G an additive group. Theorem Suppose H is a subgroup of a multiplicative group G.  Chapter 2 Groups 25 1) Any two right cosets have the same number of elements. That is, if a, b E G, f : Ha -- Hb defined by f(h - a) = h - b is a bijection. Also any two left cosets have the same number of elements. Since H is a right and left coset, any two cosets have the same number of elements. 2) G has the same number of right cosets as left cosets. The function F defined by F(Ha) = a-1H is a bijection from the collection of right cosets to the left cosets. The number of right (or left) cosets is called the index of H in G. 3) If G is finite, o(H) (index of H) = o(G) and so o(H) | o(G). In other words, o(G)/o(H) =the number of right cosets =the number of left cosets. 4) If G is finite, and a E G, then o(a) | o(G). (Proof: The order of a is the order of the subgroup generated by a, and by 3) this divides the order of G.) 5) If G has prime order, then G is cyclic, and any element (except e) is a generator. (Proof: Suppose o(G) = p and a E G, a f e. Then o(a) | p and thus o(a) = p.) 6) If o(G) = n and a E G, then a" = e. (Proof: ao(a) = e and n = o(a) (o(C)/o(a)).) Exercises i) Suppose G is a cyclic group of order 4, G = {e, a, a2, a3} with a4 = e. Find the order of each element of G. Find all the subgroups of G. ii) Suppose G is the additive group Z and H = 3Z. Find the cosets of H. iii) Think of a circle as the interval [0, 1] with end points identified. Suppose G = R under addition and H = Z. Show that the collection of all the cosets of H can be thought of as a circle. iv) Let G = R2 under addition, and H be the subgroup defined by H = {(a, 2a) : a E R}. Find the cosets of H. (See the last exercise on p 5.) ________________ Normal Subgroups We would like to make a group out of the collection of cosets of a subgroup H. In  26 Groups Chapter 2 general, there is no natural way to do that. However, it is easy to do in case H is a normal subgroup, which is described below. Theorem If H is a subgroup of a group G, then the following are equivalent. 1) If a E G, then aHa-1 = H 2) If a E C,then aHa-1 C H 3) If a E G, then aH = Ha 4) Every right coset is a left coset, i.e., if a E G, E b E G with Ha = bH. Proof 1) - 2) is obvious. Suppose 2) is true and show 3). We have (aHa1)a c Ha so aH C Ha. Also a(a-Ha) C aH so Ha C aH. Thus aH = Ha. 3) - 4) is obvious. Suppose 4) is true and show 3). Ha = bH contains a, so bH = aH because a coset is an equivalence class. Thus aH = Ha. Finally, suppose 3) is true and show 1). Multiply aH = Ha on the right by a-1. Definition If H satisfies any of the four conditions above, then H is said to be a normal subgroup of G. (This concept goes back to Evariste Galois in 1831.) Note For any group G, G and e are normal subgroups. If G is an abelian group, then every subgroup of G is normal. Exercise Show that if H is a subgroup of G with index 2, then H is normal. Exercise Show the intersection of a collection of normal subgroups of G is a normal subgroup of G. Show the union of a monotonic collection of normal subgroups of G is a normal subgroup of G. Exercise Let A C R2 be the square with vertices (-1, 1), (1, 1), (1, -1), and (-1, -1), and G be the collection of all "isometries" of A onto itself. These are bijections of A onto itself which preserve distance and angles, i.e., which preserve dot product. Show that with multiplication defined as composition, G is a multiplicative group. Show that G has four rotations, two reflections about the axes, and two reflections about the diagonals, for a total of eight elements. Show the collection of rotations is a cyclic subgroup of order four which is a normal subgroup of G. Show that the reflection about the z-axis together with the identity form a cyclic subgroup of order two which is not a normal subgroup of C. Find the four right cosets of this subgroup. Finally, find the four left cosets of this subgroup.  Chapter 2 Groups 27 Quotient Groups Suppose N is a normal subgroup of G, and C and D are cosets. We wish to define a coset E which is the product of C and D. If c E C and d E D, define E to be the coset containing c - d, i.e., E = N(c.- d). The coset E does not depend upon the choice of c and d. This is made precise in the next theorem, which is quite easy. Theorem Suppose G is a multiplicative group, N is a normal subgroup, and G/N is the collection of all cosets. Then (Na) (Nb) = N(a - b) is a well de- fined multiplication (binary operation) on G/N, and with this multiplication, G/N is a group. Its identity is N and (Na)-1 = (Na-1). Furthermore, if G is finite, o(G/N) = o(G)/o(N). Proof Multiplication of elements in G/N is multiplication of subsets in G. (Na) - (Nb) = N(aN)b = N(Na)b = N(a - b). Once multiplication is well defined, the group axioms are immediate. Exercise Write out the above theorem for G an additive group. In the additive abelian group R/Z, determine those elements of finite order. Example Suppose G = Z under +, n > 1, and N = nZ. Zn, the group of integers mod n is defined by Zn = Z/nZ. If a is an integer, the coset a + nZ is denoted by [a]. Note that [a] + [b] = [a + b], -[a] = [-a], and [a] = [a + nl] for any integer 1. Any additive abelian group has a scalar multiplication over Z, and in this case it is just [a]m = [am]. Note that [a] - [r] where r is the remainder of a divided by n, and thus the distinct elements of Zn are [0], [1], ..., [n - 1]. Also Zn is cyclic because each of [1] and [-1] = [n - 1] is a generator. We already know that if p is a prime, any non-zero element of Z, is a generator, because Z, has p elements. Theorem If n > 1 and a is any integer, then [a] is a generator of Z iff (a, n) = 1. Proof The element [a] is a generator iff the subgroup generated by [a] contains [1] iff E an integer k such that [a]k = [1] iff E integers k and 1 such that ak +nl = 1. Exercise Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3. Note that [10] = [1] in Z3. (See the fifth exercise on page 18.) Homomorphisms Homomorphisms are functions between groups that commute with the group op- erations. It follows that they honor identities and inverses. In this section we list  28 Groups Chapter 2 the basic properties. Properties 11), 12), and 13) show the connections between coset groups and homomorphisms, and should be considered as the cornerstones of abstract algebra. As always, the student should rewrite the material in additive notation. Definition If G and C are multiplicative groups, a function f :G - G is a homomorphism if, for all a, b E G, f(a - b) = f(a) - f(b). On the left side, the group operation is in G, while on the right side it is in G. The kernel of f is defined by ker(f) = f-(s) = {a E G f(a) = s}. In other words, the kernel is the set of solutions to the equation f(x) = s. (If G is an additive group, ker(f) = f-(0) Examples The constant map f : G - defined by f(a) = e is a homomorphism. If H is a subgroup of G, the inclusion i : H -- G is a homomorphism. The function f Z -- Z defined by f(t) = 2t is a homomorphism of additive groups, while the function defined by f(t) = t+2 is not a homomorphism. The function h : Z - R -0 defined by h(t) = 2t is a homomorphism from an additive group to a multiplicative group. We now catalog the basic properties of homomorphisms. These will be helpful later on in the study of ring homomorphisms and module homomorphisms. Theorem Suppose G and C are groups and f : G - G is a homomorphism. 1) f(e)=s. 2) f (a-1) = f (a)-1. The first inverse is in G, and the second is in G. 3) f is injective < ker(f) = e. 4) If H is a subgroup of G, f(H) is a subgroup of G. In particular, image(f) is a subgroup of C. 5) If H is a subgroup of G, f-1(H) is a subgroup of G. Furthermore, if H is normal in G, then f-1(H) is normal in G. 6) The kernel of f is a normal subgroup of G. 7) If g E C, f (g) is void or is a coset of ker(f), i.e., if f(g) = then f-1() =Ng where N= ker(f). In other words, if the equation f(x) = has a  Chapter 2 Groups 29 solution, then the set of all solutions is a coset of N= ker(f). This is a key fact which is used routinely in topics such as systems of equations and linear differential equations. 8) The composition of homomorphisms is a homomorphism, i.e., if h : G ~- is a homomorphism, then h o f: G - G is a homomorphism. 9) If f : G - G is a bijection, then the function f-1 : G - G is a homomorphism. In this case, f is called an isomorphism, and we write G G. In the case G = G, f is also called an automorphism. 10) Isomorphisms preserve all algebraic properties. For example, if f is an isomorphism and H C G is a subset, then H is a subgroup of G iff f(H) is a subgroup of G, H is normal in G iff f(H) is normal in C, G is cyclic iff G is cyclic, etc. Of course, this is somewhat of a cop-out, because an algebraic property is one that, by definition, is preserved under isomorphisms. 11) Suppose H is a normal subgroup of G. Then 7: G -- G/H defined by er(a) = Ha is a surjective homomorphism with kernel H. Furthermore, if f : G - G is a surjective homomorphism with kernel H, then G/H G (see below). 12) Suppose H is a normal subgroup of G. If H C ker(f), then f : G/H - G defined by f(Ha) = f(a) is a well-defined homomorphism making the following diagram commute. G - G/H Thus defining a homomorphism on a quotient group is the same as defining a homomorphism on the numerator which sends the denominator to e. The image of f is the image of f and the kernel of f is ker(f)/H. Thus if H = ker(f), f is injective, and thus G/H image(f). 13) Given any group homomorphism f, domain(f)/ker(f) image(f). This is the fundamental connection between quotient groups and homomorphisms.  30 Groups Chapter 2 14) Suppose K is a group. Then K is an infinite cycle group iff K is isomorphic to the integers under addition, i.e., K z Z. K is a cyclic group of order n iff K Zn. Proof of 14) Suppose CG= K is generated by some element a. Then f : Z - K defined by f(m) = a'm is a homomorphism from an additive group to a multiplicative group. If o(a) is infinite, f is an isomorphism. If o(a) = n, ker(f) = nZ and f : Zn - K is an isomorphism. Exercise If a is an element of a group G, there is always a homomorphism from Z to G which sends 1 to a. When is there a homomorphism from Zn to G which sends [1] to a? What are the homomorphisms from Z2 to Z6? What are the homomorphisms from Z4 to Z8? Exercise Suppose G is a group and g is an element of G, g f e. 1) Under what conditions on g is there a homomorphism f : Z7 - G with f ([1]) = ? 2) Under what conditions on g is there a homomorphism f : Z15 - GCwith f ([1]) = g ? 3) Under what conditions on G is there an injective homomorphism f : Z15 - G? 4) Under what conditions on G is there a surjective homomorphism f : Z15 - GC? Exercise We know every finite group of prime order is cyclic and thus abelian. Show that every group of order four is abelian. Exercise Let G = {h : [0, 1] - R : h has an infinite number of derivatives}. Then G is a group under addition. Define f : G - G by f(h) = ft=h'. Show f is a homomorphism and find its kernel and image. Let g : [0, 1] - R be defined by g(t) = t3 - 3t + 4. Find f-1(g) and show it is a coset of ker(f). Exercise Let G be as above and g E G. Define f : G - G by f(h) = h" + 5h'+ 6t2h. Then f is a group homomorphism and the differential equation h" +5h' +6t2h g has a solution iff g lies in the image of f. Now suppose this equation has a solution and S c C is the set of all solutions. For which subgroup H of C is S an H-coset?  Chapter 2 Groups 31 Exercise Suppose G is a multiplicative group and a E G. Define f : G - C to be conjugation by a, i.e., f (g) = a-1 - g - a. Show that f is a homomorphism. Also show f is an automorphism and find its inverse. Permutations Suppose X is a (non-void) set. A bijection f : X - X is called a permutation on X, and the collection of all these permutations is denoted by S = S(X). In this setting, variables are written on the left, i.e., f = (x)f. Therefore the composition f o g means "f followed by g". S(X) forms a multiplicative group under composition. Exercise Show that if there is a bijection between X and Y, there is an iso- morphism between S(X) and S(Y). Thus if each of X and Y has n elements, S(X) ~ S(Y), and these groups are called the symmetric groups on n elements. They are all denoted by the one symbol Sn. Exercise Show that o(Sn) = n!. Let X = {1, 2, ...,n}, Sn = S(X), and H = {f E Sn : (n)f = n}. Show H is a subgroup of Sn which is isomorphic to Sn_1. Let g be any permutation on X with (n)g = 1. Find g-1Hg. The next theorem shows that the symmetric groups are incredibly rich and com- plex. Theorem (Cayley's Theorem) Suppose G is a multiplicative group with n elements and Sn is the group of all permutations on the set G. Then G is isomorphic to a subgroup of Sn. Proof Let h : G - Sn be the function which sends a to the bijection ha : G - G defined by (g)ha = g - a. The proof follows from the following observations. 1) For each given a, ha is a bijection from G to G. 2) h is a homomorphism, i.e., ha.b = ha o hb. 3) h is injective and thus G is isomorphic to image(h) C Sn. The Symmetric Groups Now let n ;> 2 and let Sn be the group of all permu- tations on { 1, 2, ..., n}. The following definition shows that each element of Sn, may  32 Groups Chapter 2 be represented by a matrix. Definition Suppose 1 < k < n, {ai, a2, ..., ak} is a collection of distinct inte- gers with 1 < ai < n, and {b1, b2, ..., bk} is the same collection in some different order. Then the matrix a1 a2 ... ak represents f E S, defined by (ai)f b for 1 < i < k, The th marix b1 b2 ... b/ and (a)f = a for all other a. The composition of two permutations is computed by applying the matrix on the left first and the matrix on the right second. There is a special type of permutation called a cycle. For these we have a special notation. Definition ( a1 a2...aklak is called a k-cycle, and is denoted by (ai, a2, ..., ak). a2 a3...ak a1/ A 2-cycle is called a transposition. The cycles (ai, ..., ak) and (ci, ..., cP) are disjoint provided ai -/ cj for all 1 < i < k and 1 3, every even permutation is the product of 3-cycles. The following parts are not included in this course. They are presented here merely for reference. 9) For any n f 4, An is simple, i.e., has no proper normal subgroups. 10) Sn can be generated by two elements. In fact, {(1, 2), (1, 2, ..., n)} generates Sn. (Of course there are subgroups of Sn which cannot be generated by two elements). Proof of 4) It suffices to prove if the product of t transpositions is the identity I on {1, 2, ... , n}, then t is even. Suppose this is false and I is written as t transposi- tions, where t is the smallest odd integer this is possible. Since t is odd, it is at least 3. Suppose for convenience the first transposition is (a, n). We will rewrite I as a prod- uct of transpositions 5152... 0t where (n)ui = (n) for 1 < i < t and (n)it n, which will be a contradiction. This can be done by inductively "pushing n to the right" using the equations below. If a, b, and c are distinct integers in {1, 2, ... , n - 1}, then (a,n)(a,n) = I, (a,n)(b,n) = (a,b)(a,n), (a,n)(a,c) = (a,c)(c,n), and (a, n)(b, c) = (b, c)(a, n). Note that (a, n)(a, n) cannot occur here because it would result in a shorter odd product. (Now you may solve the tile puzzle on page viii.) Exercise 1) Write (6 5 4 3 1 7 2 as the product of disjoint cycles. Write (1,5,6,7)(2,3,4)(3,7,1) as the product of disjoint cycles. Write (3,7,1)(1,5,6,7)(2,3,4) as the product of disjoint cycles. Which of these permutations are odd and which are even?  34 Groups Chapter 2 2) Suppose (ai,..., ak) and (c1,... , c ) are disjoint cycles. What is the order of their product? 3) Suppose a E Sn. Show that a1(1, 2, 3)au= ((1)a, (2)a, (3)a). This shows that conjugation by a is just a type of relabeling. Also let T= (4, 5, 6) and find T-1(1, 2, 3, 4, 5)T. 4) Show that H = {c E S6: (6)ac= 6} is a subgroup of S6 and find its right cosets and its left cosets. 5) Let A C R2 be the square with vertices (-1, 1), (1, 1), (1, -1), and (-1, -1), and G be the collection of all isometries of A onto itself. We know from a previous exercise that G is a group with eight elements. It follows from Cayley's theorem that G is isomorphic to a subgroup of S8. Show that G is isomorphic to a subgroup of S4. 6) If G is a multiplicative group, define a new multiplication on the set G by a o b = b - a. In other words, the new multiplication is the old multiplication in the opposite order. This defines a new group denoted by GP, the opposite group. Show that it has the same identity and the same inverses as G, and that f : G - GP defined by f(a) = a-1 is a group isomorphism. Now consider the special case G = Sn. The convention used in this section is that an element of Sn is a permutation on {1, 2, ... , n} with the variable written on the left. Show that an element of SP is a permutation on {1, 2, ... , n} with the variable written on the right. (Of course, either Sn or Sp may be called the symmetric group, depending on personal preference or context.) Product of Groups The product of groups is usually presented for multiplicative groups. It is pre- sented here for additive groups because this is the form that occurs in later chapters. As an exercise, this section should be rewritten using multiplicative notation. The two theorems below are transparent and easy, but quite useful. For simplicity we first consider the product of two groups, although the case of infinite products is only slightly more difficult. For background, read first the two theorems on page 11. Theorem Suppose C1 and C2 are additive groups. Define an addition on C1 x C2 by (ai, a2) + (bi, b2) =(a1 + bi, a2 + b2). This operation makes C1 x C2 into a group. Its "zero" is (01, 02) and -(ai, a2) =(-ai, -a2). The projections wri :C1 x C2 > G1  Chapter 2 Groups 35 and 2 : G1 XG2 - G2 are group homomorphisms. Suppose G is an additive group. We know there is a bijection from {functions f : G - G1 x G2} to {ordered pairs of functions (fi, f2) where fi : G - G1 and f2 : G - 02}. Under this bijection, f is a group homomorphism iff each of fi and f2 is a group homomorphism. Proof It is transparent that the product of groups is a group, so let's prove the last part. Suppose G, G1i, and G2 are groups and f = (fi, f2) is a function from G to G1 x G2. Now f(a + b) = (f1(a + b), f2(a + b)) and f(a) + f(b) (f1(a), f2(a)) + (f1(b), f2(b)) = (f1(a) + f1(b), f2(a) + f2(b)). An examination of these two equations shows that f is a group homomorphism iff each of fi and f2 is a group homomorphism. Exercise Suppose G1 and G2 are groups. Show that G1 x G2 and G2 x G1 are isomorphic. Exercise If o(ai) = m and o(a2) = n, find the order of (ai, a2) in G1 x G2. Exercise Show that if G is any group of order 4, G is isomorphic to Z4 or Z2 x Z2. Show Z4 is not isomorphic to Z2 x Z2. Show Z12 is isomorphic to Z4 x Z3. Finally, show that Zm, is isomorphic to Zm x Z iff (m, n) = 1. Exercise Suppose G1 and G2 are groups and i1 : G1 - G1 x G is defined by i1(gi) = (g1, 02). Show i1 is an injective group homomorphism and its image is a normal subgroup of G1 x G2. Usually G1 is identified with its image under i1, so G1 may be considered to be a normal subgroup of G1 x G2. Let 2 : G1 x G - G2 be the projection map defined in the Background chapter. Show 72 is a surjective homomorphism with kernel G1. Therefore (G1 x G2)7G1 G2 as you would expect. Exercise Let R be the reals under addition. Show that the addition in the product R x R is just the usual addition in analytic geometry. Exercise Suppose n > 2. Is Sn isomorphic to An x G where G is a multiplicative group of order 2? One nice thing about the product of groups is that it works fine for any finite number, or even any infinite number. The next theorem is stated in full generality.  36 Groups Chapter 2 Theorem Suppose T is an index set, and for any t E T, Gt is an additive group. Define an addition on HGt= HGt by {at} + {bt} = {at + bt}. This op- tET eration makes the product into a group. Its "zero" is {0} and -{at} {-at}. Each projection ors: H Gt - G is a group homomorphism. Suppose G is an ad- ditive group. Under the natural bijection from {functions f :G -- H G} to {sequences of functions {ft}tET where ft :G - Gt}, f is a group homomorphism iff each ft is a group homomorphism. Finally, the scalar multiplication on H Gt by integers is given coordinatewise, i.e., {at}nm= {atn}. Proof The addition on H Gtis coordinatewise. Exercise Suppose s is an element of T and : H Gt - G is the projection map defined in the Background chapter. Show wr is a surjective homomorphism and find its kernel. Exercise Suppose s is an element of T and is : G - H Gtis defined by is(a) {at} where at = 0 if t f s and as = a. Show is is an injective homomorphism and its image is a normal subgroup of H Gt. Thus each G may be considered to be a normal subgroup of H C. Exercise Let f: Z - Z30 x Zioo be the homomorphism defined by f(m) ([4m], [3m]). Find the kernel of f. Find the order of ([4], [3]) in Z30 x Z100. Exercise Let f : Z - Z90 x Z70 x Z42 be the group homomorphism defined by f(m) ([m], [m], [m]). Find the kernel of f and show that f is not surjective. Let g Z - Z45 x Z35 x Z21 be defined by g(m) = ([m], [m], [m]). Find the kernel of g and determine if g is surjective. Note that the gcd of {45, 35, 21} is 1. Now let h : Z - Z8 x Z9 x Z35 be defined by h(m) = ([m], [m], [m]). Find the kernel of h and show that h is surjective. Finally suppose each of b, c, and d is greater than 1 and f : Z - Zb x Z, x Zd is defined by f(m) = ([m], [m], [m]). Find necessary and sufficient conditions for f to be surjective (see the first exercise on page 18). Exercise Suppose T is a non-void set, G is an additive group, and GT is the collection of all functions f : T -- G with addition defined by (f +g)(t) = f(t) +g(t). Show GT is a group. For each t E T, let Gt = G. Note that GT is just another way of writing H G. Also note that if T = [0, 1] and G = R, the addition defined on teT CT is just the usual addition of functions used in calculus. (For the ring and module versions, see exercises on pages 44 and 69.)  Chapter 3 Rings Rings are additive abelian groups with a second operation called multiplication. The connection between the two operations is provided by the distributive law. Assuming the results of Chapter 2, this chapter flows smoothly. This is because ideals are also normal subgroups and ring homomorphisms are also group homomorphisms. We do not show that the polynomial ring F[x] is a unique factorization domain, although with the material at hand, it would be easy to do. Also there is no mention of prime or maximal ideals, because these concepts are unnecessary for our development of linear algebra. These concepts are developed in the Appendix. A section on Boolean rings is included because of their importance in logic and computer science. Suppose R is an additive abelian group, R / 0, and R has a second binary operation (i.e., map from R x R to R) which is denoted by multiplication. Consider the following properties. 1) If a, b, c E R, (a - b) - c = a - (b - c). (The associative property of multiplication.) 2) If a,b,cER, a-(b+c) =(ab)+(a-c) and (b+c)-a= (b-a)+(c-a). (The distributive law, which connects addition and multiplication.) 3) R has a multiplicative identity, i.e., there is an element 1=iER such thatifaER, a-1=1-a=a. 4) If a, b E R, a - b = b - a. (The commutative property for multiplication.) Definition If 1), 2), and 3) are satisfied, R is said to be a ring. If in addition 4) is satisfied, R is said to be a commutative ring. Examples The basic commutative rings in mathematics are the integers Z, the 37  38 Rings Chapter 3 rational numbers Q, the real numbers R, and the complex numbers C. It will be shown later that Z., the integers mod n, has a natural multiplication under which it is a commutative ring. Also if R is any commutative ring, we will define R[zi, x2, ..., zn] a polynomical ring in n variables. Now suppose R is any ring, n > 1, and Rn is the collection of all n x n matrices over R. In the next chapter, operations of addition and multiplication of matrices will be defined. Under these operations, Rn is a ring. This is a basic example of a non-commutative ring. If n> 1, Rn is never commutative, even if R is commutative. The next two theorems show that ring multiplication behaves as you would wish it to. They should be worked as exercises. Theorem Suppose R is a ring and a, b E R. 1) a-=-a=O. Since RO, it follows that 1 40. 2) (-a) -b =a- (-b) = -(a -b). Recall that, since R is an additive abelian group, it has a scalar multiplication over Z (page 20). This scalar multiplication can be written on the right or left, i.e., na = an, and the next theorem shows it relates nicely to the ring multiplication. Theorem Suppose a, b E R and n, m E Z. 1) (na) - (mb) = (nm)(a - b). (This follows from the distributive law and the previous theorem.) 2) Let n = nl. For example, 2 = 1 + 1. Then na = n - a, that is, scalar multiplication by n is the same as ring multiplication by n. Of course, n may be 0 even though n / 0. Units Definition An element a of a ring R is a unit provided E an element a-1 E R with a-a-1 =a-1 -a =1. Theorem 0 can never be a unit. 1 is always a unit. If a is a unit, a-1 is also a unit with (a-1)-1 =a. The product of units is a unit with (a.-b- - a-1. More  Chapter 3 Rings 39 generally, if ai, a2, ..., a are units, then their product is a unit with (a1 a2 an) a-1 - a-li - - - a-1. The set of all units of R forms a multiplicative group denoted by R*. Finally if a is a unit, (-a) is a unit and (-a)-1 =--(a-1). In order for a to be a unit, it must have a two-sided inverse. It suffices to require a left inverse and a right inverse, as shown in the next theorem. Theorem Suppose a E R and E elements b and c with b- a b = c and so a is a unit with a-1 =b=c. Proof b= b 1 =b (ac) =(b-a) -c= 1 -c =c. a - c = 1. Then Corollary Inverses are unique. Domains and Fields In order to define these two types of rings, we first consider the concept of zero divisor. Definition Suppose R is a commutative ring. An element a E R is called a zero divisor provided it is non-zero and E a non-zero element b with a - b = 0. Note that if a is a unit, it cannot be a zero divisor. Theorem Then (a.b = from R to R. Suppose R is a commutative ring and a E (R - 0) is not a zero divisor. a - c) - b = c. In other words, multiplication by a is an injective map It is surjective iff a is a unit. Definition A domain (or integral domain) is a commutative ring such that, if a / Q, a is not a zero divisor. A field is a commutative ring such that, if a / 0, a is a unit. In other words, R is a field if it is commutative and its non-zero elements form a group under multiplication. Theorem A field is a domain. A finite domain is a field. Proof A field is a domain because a unit cannot be a zero divisor. Suppose R is a finite domain and a / 0. Then f : R - R defined by f (b) = a - b is injective and, by the pigeonhole principle, f is surjective. Thus a is a unit and so R is a field.  40 Rings Chapter 3 Exercise Let C be the additive abelian group R2. Define multiplication by (a, b) - (c, d) = (ac - bd, ad + bc). Show C is a commutative ring which is a field. Note that 1 = (1, 0) and if i = (0, 1), then i2 =-l. Examples Z is a domain. Q, R, and C are fields. The Integers Mod n The concept of integers mod n is fundamental in mathematics. It leads to a neat little theory, as seen by the theorems below. However, the basic theory cannot be completed until the product of rings is defined. (See the Chinese Remainder Theorem on page 50.) We know from page 27 that Zn is an additive abelian group. Theorem Suppose n > 1. Define a multiplication on Zn by [a] - [b] = [ab]. This is a well defined binary operation which makes Zn into a commutative ring. Proof Since [a + kn] - [b + In] = [ab + n(al + bk + kin)] = [ab], the multiplication is well-defined. The ring axioms are easily verified. Theorem Suppose n > 1 and a E Z. Then the following are equivalent. 1) [a] is a generator of the additive group Zn. 2) (a, n) = 1. 3) [a] is a unit of the ring Z,. Proof We already know from page 27 that 1) and 2) are equivalent. Recall that if b is an integer, [a]b = [a] - [b] [ab]. Thus 1) and 3) are equivalent, because each says E an integer b with [a]b = [1]. Corollary If n > 1, the following are equivalent. 1) Zn is a domain. 2) Zn is a field. 3) n is a prime. Proof We already know 1) and 2) are equivalent, because Z, is finite. Suppose 3) is true. Then by the previous theorem, each of [1], [2],...,[in - 1] is a unit, and thus 2) is true. Now suppose 3) is false. Then in =ab where 1 < a 1, and I = nZ, the ring structure on Zn = Z/nZ is the same as the one previously defined. Homomorphisms Definition Suppose R and R are rings. A function f : R -- R is a ring homo- morphism provided 1) f is a group homomorphism 2) fGlR) -- and 3) if a, b E R then f(a - b) =f(a) - f(b). (On the left, multiplication  Chapter 3 Rings 43 is in R, while on the right multiplication is in R.) The kernel of f is the kernel of f considered as a group homomorphism, namely ker(f) = f -1(0). Here is a list of the basic properties of ring homomorphisms. Much of this work has already been done by the theorem in group theory on page 28. Theorem Suppose each of R and R is a ring. 1) The identity map IR: R - R is a ring homomorphism. 2) The zero map from R to R is not a ring homomorphism (because it does not send lR to 1R). 3) The composition of ring homomorphisms is a ring homomorphism. 4) If f : R - R is a bijection which is a ring homomorphism, then f-1 : R - R is a ring homomorphism. Such an f is called a ring isomorphism. In the case R = R, f is also called a ring automorphism. 5) The image of a ring homomorphism is a subring of the range. 6) The kernel of a ring homomorphism is an ideal of the domain. In fact, if f : R -- R is a homomorphism and I C R is an ideal, then f-1(I) is an ideal of R. 7) SupposeI is an ideal of R, I#/ R, and 7 : R - R/I is the natural projection, er(a) = (a + I). Then 7 is a surjective ring homomorphism with kernel I. Furthermore, if f : R -- R is a surjective ring homomorphism with kernel I, then R/I ~ R (see below). 8) From now on the word "homomorphism" means "ring homomorphism". Suppose f :R -~ R is a homomorphism and I is an ideal of R, I / R. If I c ker(f), then f : R/I -~ I defined by f(a +I) =f(a)  44 Rings Chapter 3 is a well-defined homomorphism making the following diagram commute. f R-R 7r f R/I Thus defining a homomorphism on a quotient ring is the same as defining a homomorphism on the numerator which sends the denominator to zero. The image of f is the image of f, and the kernel of f is ker(f)/I. Thus if I = ker(f), f is injective, and so R/I image (f). Proof We know all this on the group level, and it is only necessary to check that f is a ring homomorphism, which is obvious. 9) Given any ring homomorphism f, domain(f)/ker(f) image(f). Exercise Find a ring R with a proper ideal I and an element b such that b is not a unit in R but (b + I) is a unit in R/I. Exercise Show that if u is a unit in a ring R, then conjugation by u is an automorphism on R. That is, show that f : R - R defined by f(a) = u-1 - a - u is a ring homomorphism which is an isomorphism. Exercise Suppose T is a non-void set, R is a ring, and RT is the collection of all functions f : T - R. Define addition and multiplication on RT point-wise. This means if f and g are functions from T to R, then (f + g)(t) = f(t) + g(t) and (f - g)(t) = f(t)g(t). Show that under these operations RT is a ring. Suppose S is a non-void set and a : S - T is a function. If f : T - R is a function, define a function a*(f) : S - R by a*(f) = f o a. Show a* : RT - RS is a ring homomorphism. Exercise Now consider the case T = [0, 1] and R = R. Let A C RE0']l be the collection of all C~ functions, i.e., A ={f : [0, 1] -~ R : f has an infinite number of derivatives}. Show A is a ring. Notice that much of the work has been done in the previous exercise. It is only necessary to show that A is a subring of the ring RE0'1l.  Chapter 3 Rings 45 Polynomial Rings In calculus, we consider real functions f which are polynomials, f(x) = ao+aix+ - - +anx. The sum and product of polynomials are again polynomials, and it is easy to see that the collection of polynomial functions forms a commutative ring. We can do the same thing formally in a purely algebraic setting. Definition Suppose R is a commutative ring and x is a "variable" or "symbol". The polynomial ring R[x] is the collection of all polynomials f = ao + aix + - -+anz" where a2 E R. Under the obvious addition and multiplication, R[x] is a commutative ring. The degree of a non-zero polynomial f is the largest integer n such that an / Q, and is denoted by n = deg(f). If the top term an = 1, then f is said to be moni. To be more formal, think of a polynomial ao + aix + - - - as an infinite sequence (ao, ai, ...) such that each ai E R and only a finite number are non-zero. Then (ao, air...) + (boybig...) = (ao + bo, ai+ bi, ...) and (ao, ai, ...) - (bo, bi, ...) (aobo, aob1 + aibo, aob2 + aibi + a2bo, ...). Note that on the right, the ring multiplication a - b is written simply as ab, as is often done for convenience. Theorem If R is a domain, R[x] is also a domain. Proof Suppose f and g are non-zero polynomials. Then deg(f)+deg(g) = deg(fg) and thus fg is not 0. Another way to prove this theorem is to look at the bottom terms instead of the top terms. Let aci and byzc be the first non-zero terms of f and g. Then asbjzi+j is the first non-zero term of fg. Theorem (The Division Algorithm) Suppose R is a commutative ring, f E R[x] has degree > 1 and its top coefficient is a unit in R. (If R is a field, the top coefficient of f will always be a unit.) Then for any g E R[x], E! h, r E R[x] such that g= fh + r with r =0 or deg(r) 1 and amis a unit in R. For any g with deg(g) m and the result holds for any polynomial of degree less than  46 Rings Chapter 3 n. Suppose g is a polynomial of degree n. Now E a monomial bzt with t = n - m and deg(g - fbxt) < n. By induction, E hi and r with fh1 + r = (g - fbxt) and deg(r) 0, and g(x) = ao + a1x + --- + anz" is a polynomial of degree n with at least one root in R. Then g has at most n roots. Let ci, c2, .., ck be the distinct roots of g in the ring R. Then E a unique sequence of positive integers n1, n2, .., nk and a unique polynomial h with no root in R so that g(x) = (x - c1)"h1 --- (x - ck)"kh(x). (If h has degree 0, i.e., if h = an, then we say "all the roots of g belong to R". If g = anx, we say "all the roots of g are 0".) Proof Uniqueness is easy so let's prove existence. The theorem is clearly true for n = 1. Suppose n> 1 and the theorem is true for any polynomial of degree less than n. Now suppose g is a polynomial of degree n and ci is a root of g. Then E a polynomial h1 with g(x) = (x - ci)hi. Since h1 has degree less than n, the result follows by induction. Note If g is any non-constant polynomial in C[x], all the roots of g belong to C, i.e., C is an algebraically closed field. This is called The Fundamental Theorem of Algebra, and it is assumed without proof for this textbook. Exercise Suppose g is a non-constant polynomial in R[x]. Show that if g has odd degree then it has a real root. Also show that if g(x) = x2 + bx + c, then it has a real root iff b2 > 4c, and in that case both roots belong to R. Definition A domain T is a principal ideal domain (PID) if, given any ideal I, 2 t E T such that I = tT. Note that Z is a PID and any field is PID. Theorem Suppose F is a field, I is a proper ideal of F[x], and n is the smallest positive integer such that I contains a polynomial of degree n. Then I contains a unique polynomial of the form f = ao + a1x + -- +an_1x"-1 + X" and it has the property that I= fF[x]. Thus F[x] is a PID. Furthermore, each coset of I can be written uniquely in the form (co + cix + . . +c _1x"-1 + I). Proof. This is a good exercise in the use of the division algorithm. Note this is similar to showing that a subgroup of Z is generated by one element (see page 15).  Chapter 3 Rings 47 Theorem. Suppose R is a subring of a commutative ring C and c E C. Then '! homomorphism h : R[x] - C with h(x) = c and h(r) = r for all r E R. It is defined by h(ao + aix +-"- +anx) = ao + a1c + - - +anc", i.e., h sends f (x) to f (c). The image of h is the smallest subring of C containing R and c. This map h is called an evaluation map. The theorem says that adding two polynomials in R[x] and evaluating is the same as evaluating and then adding in C. Also multiplying two polynomials in R[x] and evaluating is the same as evaluating and then multiplying in C. In street language the theorem says you are free to send x wherever you wish and extend to a ring homomorphism on R[x]. Exercise Let C = {a + bi : a, b E R}. Since R is a subring of C, there exists a homomorphism h : R[x] - C which sends x to i, and this h is surjective. Show ker(h) (x2 + 1)R[x] and thus R[x]/(x2 + 1) ~ C. This is a good way to look at the complex numbers, i.e., to obtain C, adjoin x to R and set x2 -1. Exercise Z2[x]/(x2 + x + 1) has 4 elements. Write out the multiplication table for this ring and show that it is a field. Exercise Show that, if R is a domain, the units of R[x] are just the units of R. Thus if F is a field, the units of F[x] are the non-zero constants. Show that [1] + [2]x is a unit in Z4[x]. In this chapter we do not prove F[x] is a unique factorization domain, nor do we even define unique factorization domain. The next definition and theorem are included merely for reference, and should not be studied at this stage. Definition Suppose F is a field and f E F[z] has degree > 1. The statement that g is an associate of f means E a unit u E F[z] such that g = uf. The statement that f is irreducible means that if h is a non-constant polynomial which divides f, then h is an associate of f. We do not develop the theory of F[x] here. However, the development is easy because it corresponds to the development of Z in Chapter 1. The Division Algo- rithm corresponds to the Euclidean Algorithm. Irreducible polynomials correspond to prime integers. The degree function corresponds to the absolute value function. One difference is that the units of F[x] are non-zero constants, while the units of Z  48 Rings Chapter 3 are just +1. Thus the associates of f are all cf with c / Q while the associates of an integer n are just tn. Here is the basic theorem. (This theory is developed in full in the Appendix under the topic of Euclidean domains.) Theorem Suppose F is a field and f E F[x] has degree > 1. Then f factors as the product of irreducibles, and this factorization is unique up to order and associates. Also the following are equivalent. 1) F[x]/(f) is a domain. 2) F[x]/(f) is a field. 3) f is irreducible. Definition Now suppose x and y are "variables". If a E R and n, m > 0, then axym = aymx" is called a monomial. Define an element of R[x, y] to be any finite sum of monomials. Theorem R[x, y] is a commutative ring and (R[x])[y] ~ R[x, y] ~ (R[y])[x]. In other words, any polynomial in x and y with coefficients in R may be written as a polynomial in y with coefficients in R[x], or as a polynomial in x with coefficients in R[y]. Side Comment It is true that if F is a field, each f E F[x, y] factors as the product of irreducibles. However F[x, y] is not a PID. For example, the ideal I = xF[x, y] + yF[z, y] = {f E F[x, y] : f (Q, Q) =Q} is not principal. If R is a commutative ring and n ;> 2, the concept of a polynomial ring in n variables works fine without a hitch. If a E R and vi, v2, ..., vn are non-negative integers, then ax1 x2 -" - -xza is called a monomial. Order does not matter here. Define an element of R[xi, x2, ..., x] to be any finite sum of monomials. This gives a commutative ring and there is canonical isomorphism R[xi, x2, ..., x] (R[xi, x2, ..., x-1])[xz]. Using this and induction on n, it is easy to prove the fol- lowing theorem. Theorem If R is a domain, R[xi, x2, ..., za] is a domain and its units are just the units of R.  Chapter 3 Rings 49 Exercise Suppose R is a commutative ring and f R[x, y] - R[z] is the eval- uation map which sends y to 0. This means f(p(x, y)) = p(x, 0). Show f is a ring homomorphism whose kernel is the ideal (y) = yR[z, y]. Use the fact that "the do- main mod the kernel is isomorphic to the image" to show R[x, y]/(y) is isomorphic to R[x]. That is, if you adjoin y to R[x] and then factor it out, you get R[x] back. Product of Rings The product of rings works fine, just as does the product of groups. Theorem Suppose T is an index set and for each t E T, Rt is a ring. On the additive abelian group J Rt= H Rt, define multiplication by {rt} - {St} ={rt -st}. tET Then H Rt is a ring and each projection orw H R - RS is a ring homomorphism. Suppose R is a ring. Under the natural bijection from {functions f : R -- H Rt} to {sequences of functions {ft}tET where ft : R - Rt}, f is a ring homomorphism iff each ft is a ring homomorphism. Proof We already know f is a group homomorphism iff each ft is a group homo- morphism (see page 36). Note that {1} is the multiplicative identity of H Rt, and f(1R) --{lt} if ft(R) --It for each t E T. Finally, since multiplication is defined coordinatewise, f is a ring homomorphism iff each ft is a ring homomorphism. Exercise Suppose R and S are rings. Note that R x 0 is not a subring of R x S because it does not contain (1R, 1s). Show R x 0 is an ideal and (R x S/R x Q) ~ S. Suppose I C R and J C S are ideals. Show I x J is an ideal of R x S and every ideal of R x S is of this form. Exercise Suppose R and S are commutative rings. Show T = R x S is not a domain. Let e = (1,Q) E R x S and show e2_e, (1-e)2= (1 - e), R x 0 = eT, and O x S = (1- e)T. Exercise If T is any ring, an element e of T is called an idempotent provided e2 = e. The elements 0 and 1 are idempotents called the trivial idempotents. Suppose T is a commutative ring and e E T is an idempotent with 0 f e f 1. Let R = eT and S = (1 - e)T. Show each of the ideals R and S is a ring with identity, and f :T -~ R x S defined by f(t) =(et, (1- e)t) is a ring isomorphism. This shows that a commutative ring T splits as the product of two rings iff it contains a non-trivial idempotent.  50 Rings Chapter 3 The Chinese Remainder Theorem The natural map from Z to Zm x Zn is a group homomorphism and also a ring homomorphism. If m and n are relatively prime, this map is surjective with kernel mnZ, and thus Zmm and Zm x Zn are isomorphic as groups and as rings. The next theorem is a classical generalization of this. (See exercise three on page 35.) Theorem Suppose ni, ..., nt are integers, each n2 > 1, and (n2, n1) = 1 for all i / j. Let fZ : Z - Zn be defined by f2(a) = [a]. (Note that the bracket symbol is used ambiguously.) Then the ring homomorphism f = (fi, .., ft) : Z - Zn1 x - - xZ, is surjective. Furthermore, the kernel of f is nZ, where n = nin2 nt. Thus Zn and Zn1 x -- x Zn are isomorphic as rings, and thus also as groups. Proof We wish to show that the order of f(1) is n, and thus f(1) is a group generator, and thus f is surjective. The element f (1)m = ([1], .., [1])m = ([m], .., [m]) is zero iff m is a multiple of each of ni, .., nt. Since their least common multiple is n, the order of f(1) is n. (See the fourth exercise on page 36 for the case t = 3.) Exercise Show that if a is an integer and p is a prime, then [a] = [aP] in Z, (Fermat's Little Theorem). Use this and the Chinese Remainder Theorem to show that if b is a positive integer, it has the same last digit as b5. Characteristic The following theorem is just an observation, but it shows that in ring theory, the ring of integers is a "cornerstone". Theorem If R is a ring, there is one and only one ring homomorphism f : Z - R. It is given by f(m) = ml = m. Thus the subgroup of R generated by 1 is a subring of R isomorphic to Z or isomorphic to Zn for some positive integer n. Definition Suppose R is a ring and f Z -- R is the natural ring homomor- phism f(m) = ml = m. The non-negative integer n with ker(f) = nZ is called the characteristic of R. Thus f is injective iff R has characteristic 0 iff 1 has infinite order. If f is not injective, the characteristic of R is the order of 1. It is an interesting fact that, if R is a domain, all the non-zero elements of R have the same order. (See page 23 for the definition of order.)  Chapter 3 Rings 51 Theorem Suppose R is a domain. If R has characteristic 0, then each non-zero a E R has infinite order. If R has finite characteristic n, then n is a prime and each non-zero a E R has order n. Proof Suppose R has characteristic 0, a is a non-zero element of R, and m is a positive integer. Then ma = m - a cannot be 0 because m, a / Q and R is a domain. Thus o(a) =co0. Now suppose R has characteristic n. Then R contains Zn as a subring, and thus Zn is a domain and n is a prime. If a is a non-zero element of R, na = n - a O= - a = O and thus o(a)|n and thus o(a) = n. Exercise Show that if F is a field of characteristic 0, F contains Q as a subring. That is, show that the injective homomorphism f Z - F extends to an injective homomorphism f : Q -- F. Boolean Rings This section is not used elsewhere in this book. However it fits easily here, and is included for reference. Definition A ring R is a Boolean ring if for each a E R, a2 =a, i.e., each element of R is an idempotent. Theorem Suppose R is a Boolean ring. 1) R has characteristic 2. If a E R, 2a = a + a = 0, and so a = -a. Proof (a + a) = (a + a)2 = a2 + 2a2 + a2 = 4a. Thus 2a = 0. 2) R is commutative. Proof (a+b)= (a+b)2= a2+(a - b)+(b-"a)+b2 = a+(a.b)-(b.a)+b. Thus a-b=b-a. 3) If R is a domain, R ~ Z2. Proof Suppose a /OQ. Then a - (1 - a) = Q and so a = 1. 4) The image of a Boolean ring is a Boolean ring. That is, if I is an ideal of R with I / R, then every element of R/I is idempotent and thus R/I is a Doolean ring. It follows from 3) that R/I is a domain iff R/I is a field iff R/I ezz Z2. (In the language of Chapter 6, I is a prime ideal iff I is a maximal ideal iff R/I ezz Z2).  52 Rings Chapter 3 Suppose X is a non-void set. If a is a subset of X, let a' = (X -a) be a complement of a in X. Now suppose R is a non-void collection of subsets of X. Consider the following properties which the collection R may possess. 1) a E R - a'ER. 2) a,b E R (anb)ER. 3) a,b E R (aUb)ER. 4) DER and XER. Theorem If 1) and 2) are satisfied, then 3) and 4) are satisfied. In this case, R is called a Boolean algebra of sets. Proof Suppose 1) and 2) are true, and a, b E R. Then a U b = (a'n0 b')' belongs to R and so 3) is true. Since R is non-void, it contains some element a. Then 0 = a 0 a' and X = a U a' belong to R, and so 4) is true. Theorem Suppose R is a Boolean algebra of sets. Define an addition on R by a + b = (a U b) - (a 0 b). Under this addition, R is an abelian group with 0 = 0 and a = -a. Define a multiplication on R by a - b = a n b. Under this multiplication R becomes a Boolean ring with 1 = X. Exercise Let X = {1, 2, ..., n} and let R be the Boolean ring of all subsets of X. Note that o(R) = 2". Define fj : R -- Z2 by fi(a) = [1] iff i E a. Show each f2 is a homomorphism and thus f = (fi, ..., fn) :R - Z2 x Z2 x ""x Z2 is a ring homomorphism. Show f is an isomorphism. (See exercises 1) and 4) on page 12.) Exercise Use the last exercise on page 49 to show that any finite Boolean ring is isomorphic to Z2 x Z2 x" x Z2, and thus also to the Boolean ring of subsets above. Note Suppose R is a Boolean ring. It is a classical theorem that E a Boolean algebra of sets whose Boolean ring is isomorphic to R. So let's just suppose R is a Boolean algebra of sets which is a Boolean ring with addition and multiplication defined as above. Now define a V b = a U b and a /\ b= a 0 b. These operations cup and cap are associative, commutative, have identity elements, and each distributes over the other. With these two operations (along with complement), R is called a Boolean algebra. R is not a group under cup or cap. Anyway, it is a classical fact that, if you have a Doolean ring (algebra), you have a Doolean algebra (ring). The advantage of the algebra is that it is symmetric in cup and cap. The advantage of the ring viewpoint is that you can draw from the rich theory of commutative rings.  Chapter 4 Matrices and Matrix Rings We first consider matrices in full generality, i.e., over an arbitrary ring R. However, after the first few pages, it will be assumed that R is commutative. The topics, such as invertible matrices, transpose, elementary matrices, systems of equations, and determinant, are all classical. The highlight of the chapter is the theorem that a square matrix is a unit in the matrix ring iff its determinant is a unit in the ring. This chapter concludes with the theorem that similar matrices have the same deter- minant, trace, and characteristic polynomial. This will be used in the next chapter to show that an endomorphism on a finitely generated vector space has a well-defined determinant, trace, and characteristic polynomial. Definition Suppose R is a ring and m and n are positive integers. Let Rm,n be the collection of all m x n matrices a1,1 ... a ,n A = (ai,)=al where each entry as E-R. am,1 ... m,n A matrix may be viewed as m n-dimensional row vectors or as n m-dimensional column vectors. A matrix is said to be square if it has the same number of rows as columns. Square matrices are so important that they have a special notation, R = R, R"h is defined to be the additive abelian group R x R x ... x R. To emphasize that R" does not have a ring structure, we use the "sum" notation, R" = R e R (. . .- R. Our convention is to write elements of R" as column vectors, i.e., to identify R" with Rn,1. If the elements of R" are written as row vectors, R" is identified with R1, . 53  54 Matrices Chapter 4 Addition of matrices To "add" two matrices, they must have the same number of rows and the same number of columns, i.e., addition is a binary operation Rm,n X Rm,n - Rm,n The addition is defined by (ai,5)+ (b2,_) = (aij + by,), i.e., the i, j term of the sum is the sum of the i, j terms. The following theorem is just an observation. Theorem Rm,n is an additive abelian group. Its "zero" is the matrix 0 =Q0m,n all of whose terms are zero. Also - (aJ) = (-ai,5). Furthermore, as additive groups, Rm,n ~Rm". Scalar multiplication An element of R is called a scalar. A matrix may be "multiplied" on the right or left by a scalar. Right scalar multiplication is defined by (ai,)c = (ai,j - c). It is a function Rm,n x R - Rm,n. Note in particular that scalar multiplication is defined on R". Of course, if R is commutative, there is no distinction between right and left scalar multiplication. Theorem Suppose A, B E Rm,n and c, d E R. Then (A+B)c =Ac+ Bc A(c+d) =Ac+Ad A(cd) =_(Ac)d and Al = A This theorem is entirely transparent. In the language of the next chapter, it merely states that Rm,n is a right module over the ring R. Multiplication of Matrices The matrix product AB is defined iff the number of columns of A is equal to the number of rows of B. The matrix AB will have the same number of rows as A and the same number of columns as B, i.e., multiplication is a function Rm,n x Rm,p > Rm,p. The product (ai,5)(bi,5) is defined to be the matrix whose (s, t) term is as,1 - b1,t + - - - + asm- bm,t, i.e., the dot product of row s of A with column t of B. a b 2 0 0 1 Exercise Consider real matrices A = , U =1 , V and W =). Find the matrices AU, UA, AV, VA, AW, and WA.  Chapter 4 Matrices 55 Definition The identity matrix In E R, is the square matrix whose diagonal terms are 1 and whose off-diagonal terms are 0. Theorem 1) 2) Theorem Suppose A E Rm,n. p,mA = Op,n AOnl =4m,p ImA = A = AIn (The distributive laws) (A+B)C C(A + B) AC+BC CA + CB and whenever the operations are defined. Theorem (The associative law for matrix multiplication) Suppose A E Rm,n, B E Rn,,, and C E Rp,q. Then (AB)C = A(BC). Note that ABC E Rm,q. Proof We must show that the (s, t) terms are equal. The proof involves writing it out and changing the order of summation. Let (xi,) = AB and (yi,j) = BC. Then the (s, t) term of (AB)C is EZx,ici,t Z= ( as,jbj,)ci,t Z=as, bj,ici,t = Eas, (Zbici,t) =ZEas,jyj,t which is the (s, t) term of A(BC). Theorem For each ring R and integer n ;> 1, Rn is a ring. Proof This elegant little theorem is immediate from the theorems above. The units of Rn are called invertible or non-singular matrices. They form a group under multiplication called the general linear group and denoted by GLn(R) = (Rs)*. Exercise Recall that if A is a ring and a E A, then aA is right ideal of A. Let A = R2 and a = (ai,j) where a1,1 = 1 and the other entries are 0. Find aR2 and R2a. Show that the only ideal of R2 containing a is R2 itself. Multiplication by blocks Suppose A, E E Rn, B, F E Rn,m, C, G E Rm,n, and D, H E Rm. Then multiplication in Rn+m is given by (A fl(B E;F (AE+BC CE +DG AF+BH CF+DH '  56 Matrices Chapter 4 Transpose Notation tative ring. For the remainder of this chapter on matrices, suppose R is a commu- Of course, for n > 1, Rn is non-commutative. Transpose is a function from Rm,n to Rn,m. If A ERm,n, At E Rn,m is the matrix whose (i, j) term is the (j, i) term of A. So row i (column i) of A becomes column i (row i) of At. If A is an n-dimensional row vector, then At is an n-dimensional column vector. If A is a square matrix, At is also square. Theorem 1) (At)t A 2) (A+B)t At+Bt 3) If c E R, (Ac)t Ate 4) (AB)t = BtAt 5) If A E Rn, then A is invertible iff At is invertible. In this case (A-1)t = (At)-1. Suppose A is invertible. Then I = It = (AA-1)t = (A-1)tAt. Proof of 5) Exercise Characterize those invertible matrices A E R2 which have A-1 Show that they form a subgroup of GL2(R). At. Triangular Matrices If A E Rn, then A is upper (lower) triangular provided asj = 0 for all i > j (all j > i). A is strictly upper (lower) triangular provided asj = 0 for all i > j (all j > i). A is diagonal if it is upper and lower triangular, i.e., asj = 0 for all i - j. Note that if A is upper (lower) triangular, then At is lower (upper) triangular. Theorem If A E Rn is strictly upper (or lower) triangular, then A" = o. Proof The way to understand this is just multiply it out for n = 2 and n = 3. The geometry of this theorem will become transparent later in Chapter 5 when the matrix A defines an R-module endomorphism on R" (see page 93). Definition If T is any ring, an element t E T is said to be nilpotent provided En such that t" = 0. In this case, (1 - t) is a unit with inverse 1+ t + t2 + ... + t"-1 Thus if T = Rn and B is a nilpotent matrix, I - B is invertible.  Chapter 4 Matrices Exercise Let R = Z. 57 1 2 -3 Find the inverse of 0 1 4. 0 0 1 Exercise Suppose A a1 a2 0 0- is a diagonal matrix, B E Rm,n, \ anl and C E Rn,p. Show that BA is obtained from B by multiplying column i of B by a2. Show AC is obtained from C by multiplying row i of C by a2. Show A is a unit in R iff each a2 is a unit in R. Scalar matrices A scalar matrix is a diagonal matrix for which all the diagonal terms are equal, i.e., a matrix of the form cIn. The map R - Rn which sends c to cIn is an injective ring homomorphism, and thus we may consider R to be a subring of R . Multiplying by a scalar is the same as multiplying by a scalar matrix, and thus scalar matrices commute with everything, i.e., if B E Rn, (cIn)B = cB = Bc B(cIn). Recall we are assuming R is a commutative ring. Exercise Suppose A E Rn and for each B E Rn, AB = BA. Show A is a scalar matrix. For n > 1, this shows how non-commutative Rn is. Elementary Operations and Elementary Matrices Suppose R is a commutative ring and A is a matrix over R. There are 3 types of elementary row and column operations on the matrix A. A need not be square. Type 1 Multiply row i by some unit a E R. Type 2 Interchange row i and row j. Type 3 Add a times row j to row i where i / j and a is any element of R. Multiply column i by some unit a E R. Interchange column i and column j. Add a times column i to column j where i / j and a is any element of R.  58 Matrices Chapter 4 Elementary Matrices Elementary matrices are square and invertible. There are three types. They are obtained by performing row or column operations on the identity matrix. Type 1 Type 2 Type 3 1 B = a 1 1 0 0 1 1 1 0 1 where a is a unit in R. B= 1 0 1 1 1 1 B = 1 aiJ 1 1 0 1 1 where i - j and as is any element of R. In type 1, all the off-diagonal elements are zero. In type 2, there are two non-zero off-diagonal elements. In type 3, there is at most one non-zero off-diagonal element, and it may be above or below the diagonal. Exercise Show that if B is an elementary matrix of type 1,2, or 3, then B is invertible and B-1 is an elementary matrix of the same type. The following theorem is handy when working with matrices. Theorem Suppose A is a matrix. It need not be square. To perform an elemen- tary row (column) operation on A, perform the operation on an identity matrix to obtain an elementary matrix B, and multiply on the left (right). That is, BA = row operation on A and AB = column operation on A. (See the exercise on page 54.)  Chapter 4 Matrices 59 Exercise Suppose F is a field and A E Fm,n. 1) Show E invertible matrices B E Fm and C E Fn such that BAC = (d2,i) where d,1 1 -c-i t= dtt= 1 and all other entries are 0. The integer t is called the rank of A. (See page 89 of Chapter 5.) 2) Suppose A E Fn is invertible. Show A is the product of elementary matrices. 3) A matrix T is said to be in row echelon form if, for each 1 1 and each commutative ring R, determinant is a function from Rn to R. For n = 1, | (a) |=a. For n = 2, a =) =ad - bc. Definition Let A = (ai,5) E Ra. If a- is a permutation on {1, 2, ..., n}, let sign(c-)= 1 if o- is an even permutation, and sign(o-) =--1 if o- is an odd permutation. The determinant is defined by |A |= sign(o-) a1,,(1) - a2,(2 - n,() Check that for all u n = 2, this agrees with the definition above. (Note that here we are writing the permutation functions as o-(i) and not as (i)o-.)  Chapter 4 Matrices 61 For each a, ai, (1) - a2, (2) an, (n) contains exactly one factor from each row and one factor from each column. Since R is commutative, we may rearrange the factors so that the first comes from the first column, the second from the second column, etc. This means that there is a permutation T on {1, 2, ... , n} such that a1, (1) - - - an,(n) aT(1),1 - - - aT(T),T. We wish to show that T = a-1 and thus sign(u) = sign(T). To reduce the abstraction, suppose a(2) = 5. Then the first expression will contain the factor a2,5. In the second expression, it will appear as aT(5),5, and so T(5) = 2. Anyway, T is the inverse of a and thus there are two ways to define determinant. It follows that the determinant of a matrix is equal to the determinant of its transpose. Theorem |Al = sign(a)a1,,(1) . a2,,(2) ... an, ( = sign(T)aT(1),1 . aT(2),2...T all y allT Corollary |A l Atl. You may view an n x n matrix A as a sequence of n column vectors or as a sequence of n row vectors. Here we will use column vectors. This means we write the matrix A as A = (A1, A2, ... , An) where each AZ E Rn,1= R". Theorem If two columns of A are equal, then |Al = 0. Proof For simplicity, assume the first two columns are equal, i.e., A1= A2. Now |A = sign(T)aT(1),1 . aT(2),2 - - a"T(T),T and this summation has n! terms and all T n! is an even number. Let y be the transposition which interchanges one and two. Then for any T, aT(1),1 . aT(2),2."" a"T(T),Th = aTy(1),1 - aTy(2),2... aT-y(T),T. This pairs up the n! terms of the summation, and since sign(T)=-sign(Ty), these pairs cancel in the summation. Therefore Al= 0. Theorem Suppose 1 2 and the theorem is true for matrices in Rn_1. Suppose A E Rn is upper triangular. The result follows by expanding by the first column. An elementary matrix of type 3 is a special type of upper or lower triangular matrix, so its determinant is 1. An elementary matrix of type 2 is obtained from the identity matrix by interchanging two rows or columns, and thus has determinant -1. Theorem (Determinant by blocks) Suppose A E Rn, B E Rn,m, and DE Rm. Then the determinant of (O D is AD. Proof Expand by the first column and use induction on n. The following remarkable theorem takes some work to prove. We assume it here without proof. (For the proof, see page 130 of the Appendix.) Theorem i.e., if A, B |C-1AC |= Corollary The determinant of the product is the E Rn, |AB| =| A|| B|.Thus| AB| = ACC-1|= A|. product of the determinants, BA| and if C is invertible, If A is a unit in Rn, then |A Iis a unit in R and |A- l=|Al-1 Proof 1 = Il AA AllA-1|. One of the major goals of this chapter is to prove the converse of the preceding corollary. Classical adjoint Suppose R is a commutative ring and A E Ra. The classical adjoint of A is (C,)t, i.e., the matrix whose (j, i) term is the (i, j) cofactor. Before  64 Matrices Chapter 4 we consider the general case, let's examine 2 x 2 matrices. If A a s)then (C2, ) _ ( a)and so (Ci,5)t ( _ ). Then A(C,)=(C ,)tA ( | A| ) | A| I. Thus if |A| is a unit in R, A is invertible and A-1 A |-1 (C,)t. In particular, if | A 1, A-1 ( . Here is the general case. Theorem If R is commutative and A E R., then A(CJ)t = (c,)tA Al I. Proof We must show that the diagonal elements of the product A(C2,J)t are all A l and the other elements are 0. The (s, s) term is the dot product of row s of A with row s of (C2,) and is thus |A l (computed by expansion by row s). For s / t, the (s, t) term is the dot product of row s of A with row t of (Ci,i). Since this is the determinant of a matrix with row s = row t, the (s, t) term is 0. The proof that (C,5)tA =|A|I is similar and is left as an exercise. We are now ready for one of the most beautiful and useful theorems in all of mathematics. Theorem Suppose R is a commutative ring and A E Ra. Then A is a unit in Rn iff | A| is a unit in R. (Thus if R is a field, A is invertible iffI A | / 0.) If A is invertible, then A-1 A |-1 (Ci,5)t. Thus if A 1, A-1 = (Ci,5)t, the classical adjoint of A. Proof This follows immediately from the preceding theorem. Exercise Show that any right inverse of A is also a left inverse. That is, suppose A, B E Rn and AB = I. Show A is invertible with A-1 = B, and thus BA = I. Similarity Suppose A, B E Rs. B is said to be similar to A if E an invertible C E Rn such that B =WC1AC, i.e., B is similar to A iff B is a conjugate of A. Theorem B is similar to B.  Chapter 4 Matrices 65 B is similar to A iff A is similar to B. If D is similar to B and B is similar to A, then D is similar to A. "Similarity" is an equivalence relation on Rs. Proof This is a good exercise using the definition. Theorem Suppose A and B are similar. Then |A B I and thus A is invertible iff B is invertible. Proof Suppose B = C-1AC. Then | B| =W|IC-1AC |I=|ACC-1| =| A|. Trace Suppose A = (as,5) E R . Then the trace is defined by trace(A) a2,2 + - - + an,.. That is, the trace of A is the sum of its diagonal terms. a1,1 + One of the most useful properties of trace is trace(AB) = trace(BA) whenever AB and BA are defined. For example, suppose A = (ai, a2, ..., an) and B = (bi, b2, ..., bn)t. Then AB is the scalar a1bi + - - - + anbn while BA is the n x n matrix (bia3). Note that trace(AB) = trace(BA). Here is the theorem in full generality. Theorem Suppose A E Rm,n and B E Rn,m. Then AB and BA are square matrices with trace(AB) = trace(BA). Proof This proof involves a change in the order of summation. By definition, trace(AB) =_ ai,1bi,i +. -. +ai,nbn,i = ai, by,i- =1 by,1a1, + . . + bj,mam,j = 1 1. Define a function a : HomR(R", M) -_ M" which is a R-module isomorphism. Summands One basic question in algebra is "When does a module split as the sum of two modules?". Before defining summand, here are two theorems for background. Theorem Consider M1 =Mi (D0 as a submodule of Mi o(DM2. Then the projection map r2 : Mi M2 - M2 is a surjective homomorphism with kernel M1. Thus (M1 (D M2)/M1 is isomorphic to M2. (See page 35 for the group version.) This is exactly what you would expect, and the next theorem is almost as intuitive. Theorem Suppose K and L are submodules of M and f: K (D L - M is the natural homomorphism, f(k, 1) = k + 1. Then the image of f is K + L and the kernel of f is {(a, -a) : a E K n L}. Thus f is an isomorphism iff K + L = M and K n L = 0. In this case we write K (D L = M. This abuse of notation allows us to avoid talking about "internal" and "external" direct sums. Definition Suppose K is a submodule of M. The statement that K is a summand of M means I a submodule L of M with K (D L = M. According to the previous theorem, this is the same as there exists a submodule L with K + L = M and K n L = 0. If such an L exists, it need not be unique, but it will be unique up to isomorphism, because L ~ M/K. Of course, M and 0 are always summands of M. Exercise Suppose M is a module and K = {(m, m) : m E M} C M (D M. Show K is a submodule of M (D M which is a summand. Exercise R is a module over Q, and Q c R is a submodule. Is Q a summand of R? With the material at hand, this is not an easy question. Later on, it will be easy.  78 Linear Algebra Chapter 5 Exercise Answer the following questions about abelian groups, i.e., Z-modules. (See the third exercise on page 35.) 1) Is 2Z a summand of Z? 2) Is 2Z4 a summand of Z4? 3) Is 3Z12 a summand of Z12? 4) Suppose m, n > 1. When is nZmn a summand of Zmn? Exercise If T is a ring, define the center of T to be the subring {t :ts st for all s E T}. Let R be a commutative ring and T = Rn. There is a exercise on page 57 to show that the center of T is the subring of scalar matrices. Show R" is a left T-module and find HomT(R", R"h). Independence, Generating Sets, and Free Basis This section is a generalization and abstraction of the brief section Homomor- phisms on R"h. These concepts work fine for an infinite index set T because linear combination means finite linear combination. However, to avoid dizziness, the student should first consider the case where T is finite. Definition Suppose M is an R-module, T is an index set, and for each t E T, st E M. Let S be the sequence {st}tET {st}- The statement that S is dependent means I a finite number of distinct elements t1, ..., t in T, and elements r1, .., rn in R, not all zero, such that the linear combination str1i + -- +st,0rn = . Otherwise, S is independent. Note that if some st 0=0, then S is dependent. Also if I distinct elements t1 and t2 in T with st1 = st2, then S is dependent. Let SR be the set of all linear combinations st r1+ - -+strn. SR is a submodule of M called the submodule generated by S. If S is independent and generates M, then S is said to be a basis or free basis for M. In this case any v E M can be written uniquely as a linear combination of elements in S. An R-module M is said to be a free R-module if it is zero or if it has a basis. The next two theorems are obvious, except for the confusing notation. You might try first the case T = {1, 2, ..., n} and DRt = R" (see p 72). Theorem For each t E T, let R= RR and for each c E T, let ec EDRt = )e teT be ec {rt} where rc> 1 and rt =0 if t f c. Then {ec}cET is a basis for EIRt Called the canonical basis or standard basis.  Chapter 5 Linear Algebra 79 Theorem Suppose N is an R-module and M is a free R-module with a basis { st}. Then E a 1-1 correspondence from the set of all functions g:{st} - N and the set of all homomorphisms f : M - N. Given g, define f by f (stiri + -- +strn) g(st1)r1 + - - +g(stn)rn. Given f, define g by g(st) = f(st). In other words, f is completely determined by what it does on the basis S, and you are "free" to send the basis any place you wish and extend to a homomorphism. Recall that we have already had the preceding theorem in the case S is the canon- ical basis for M = R" (p 72). The next theorem is so basic in linear algebra that it is used without comment. Although the proof is easy, it should be worked carefully. Theorem Suppose N is a module, M is a free module with basis S = {St}, and f : M - N is a homomorphism. Let f(S) be the sequence {f(st)} in N. 1) f(S) generates N iff f is surjective. 2) f(S) is independent in N iff f is injective. 3) f(S) is a basis for N iff f is an isomorphism. 4) If h : M - N is a homomorphism, then f = h iff f | S = h S. Exercise Let (A1, .., An) be a sequence of n vectors with each Ai E Z". Show this sequence is linearly independent over Z iff it is linearly independent over Q. Is it true the sequence is linearly independent over Z iff it is linearly independent over R? This question is difficult until we learn more linear algebra. Characterization of Free Modules Any free R-module is isomorphic to one of the canonical free R-modules EDRt. This is just an observation, but it is a central fact in linear algebra. Theorem A non-zero R-module M is free iff E an index set T such that M e Rt. In particular, M has a finite free basis of n elements iff M R". tET Proof If M is isomorphic to DRt then M is certainly free. So now suppose M has a free basis {st}. Then the homomorphism f: M -~ eRe with f(st)= et sends the basis for M to the canonical basis for EDRt. Dy 3) in the preceding theorem, f is an isomorphism.  80 Linear Algebra Chapter 5 Exercise Suppose R is a commutative ring, A E R., and the homomorphism f : R" - R" defined by f(B) = AB is surjective. Show f is an isomorphism, i.e., show A is invertible. This is a key theorem in linear algebra, although it is usually stated only for the case where R is a field. Use the fact that {ei, .., en} is a free basis for R". The next exercise is routine, but still informative. Exercise Let R=Z, A 2 =0 and f: Z3-Z2 be the group homo- 3 2 -5 morphism defined by A. Find a non-trivial linear combination of the columns of A which is 0. Also find a non-zero element of kernel(f). If R is a commutative ring, you can relate properties of R as an R-module to properties of R as a ring. Exercise Suppose R is a commutative ring and v E R, v 0. 1) v is independent iff v is 2) v is a basis for R iff v generates R iff v is Note that 2) here is essentially the first exercise for the case n = 1. That is, if f : R - R is a surjective R-module homomorphism, then f is an isomorphism. Relating these concepts to matrices The theorem stated below gives a summary of results we have already had. It shows that certain concepts about matrices, linear independence, injective homo- morphisms, and solutions of equations, are all the same they are merely stated in different language. Suppose A E Rm,n and f : R" Rm is the homomorphism associ- ated with A, i.e., f(B) = AB. Let v1, .., on E Rm be the columns of A, i.e., f(e2) = v2 = column i of A. Let B = . represent an element of R" and C = .  Chapter 5 Linear Algebra 81 represent an element of R'. Theorem 1) The element f(B) is a linear combination of the columns of A, that is f (B) = f (eibi + -.- +enbn) = vib1 +-.- +vnbn. Thus the image of f is generated by the columns of A. (See bottom of page 89.) 2) {vi, .., vn} generates Rm iff f is surjective iff (for any C E Rm, AX = C has a solution). 3) {vi, .., vn} is independent iff f is injective iff AX = 0 has a unique solution iff ( C E Rm such that AX = C has a unique solution). 4) {vi, .., vn} is a basis for Rm iff f is an isomorphism iff (for any C E Rm, AX = C has a unique solution). Relating these concepts to square matrices We now look at the preceding theorem in the special case where n = m and R is a commutative ring. So far in this chapter we have just been cataloging. Now we prove something more substantial, namely that if f : R" - R" is surjective, then f is injective. Later on we will prove that if R is a field, injective implies surjective. Theorem Suppose R is a commutative ring, A E Rn, and f : R" - R" is defined by f(B) = AB. Let v1, .., vn E R" be the columns of A, and w1, .., w E R" = R1,n be the rows of A. Then the following are equivalent. 1) f is an automorphism. 2) A is invertible, i.e., | A | is a unit in R. 3) {v1, .., vn} is a basis for R"h. 4) {v1, .., vn} generates R". 5) f is surjective. 2t) At is invertible, i.e., |At |is a unit in R. 3t) {w1, .., wn} is a basis for R"h.  82 Linear Algebra Chapter 5 4t) {wi, .., wn} generates R". Proof Suppose 5) is true and show 2). Since f is onto, u1, ..., un E- R" with f(u2) = e2. Let g : R" - R" be the homomorphism satisfying g(e2) = u2. Then f o g is the identity. Now g comes from some matrix D and thus AD = I. This shows that A has a right inverse and is thus invertible. Recall that the proof of this fact uses determinant, which requires that R be commutative (see the exercise on page 64). We already know the first three properties are equivalent, 4) and 5) are equivalent, and 3) implies 4). Thus the first five are equivalent. Furthermore, applying this result to At shows that the last three properties are equivalent to each other. Since A =| At , 2) and 2t) are equivalent. Uniqueness of Dimension There exists a ring R with R2 ~ R3 as R-modules, but this is of little interest. If R is commutative, this is impossible, as shown below. First we make a convention. Convention For the remainder of this chapter, R will be a commutative ring. Theorem If f : Rm R" is a surjective R-module homomorphism, then m > n. Proof Suppose k = n - m is positive. Define h : (Rm Rk = R") - R" by h(u, v) = f(u). Then h is a surjective homomorphism, and by the previous section, also injective. This is a contradiction and thus m > n. Corollary If f : Rm - R" is an isomorphism, then m = n. Proof Each of f and f-1 is surjective, so m = n by the previous theorem. Corollary If {vi, .., Vm} generates R", then m > n. Proof The hypothesis implies there is a surjective homomorphism Rm - R". So this follows from the first theorem. Lemma Suppose M is a f.g. module (i.e., a finite generated R-module). Then if M has a basis, that basis is finite.  Chapter 5 Linear Algebra 83 Proof Suppose U C M is a finite generating set and S is a basis. Then any element of U is a finite linear combination of elements of S, and thus S is finite. Theorem Suppose M is a f.g. module. If M has a basis, that basis is finite and any other basis has the same number of elements. This number is denoted by dim(M), the dimension of M. (By convention, 0 is a free module of dimension 0.) Proof By the previous lemma, any basis for M must be finite. M has a basis of n elements iff M R". The result follows because R" R~' if n = m. Change of Basis Before changing basis, we recall what a basis is. Previously we defined generat- ing, independence, and basis for sequences, not for collections. For the concept of generating it matters not whether you use sequences or collections, but for indepen- dence and basis, you must use sequences. Consider the columns of the real matrix {2 3 2 A ( 1 4 ). If we consider the column vectors of A as a collection, there are only two of them, yet we certainly don't wish to say the columns of A form a basis for R2. In a set or collection, there is no concept of repetition. In order to make sense, we must consider the columns of A as an ordered triple of vectors, and this sequence is dependent. In the definition of basis on page 78, basis is defined for sequences, not for sets or collections. Two sequences cannot begin to be equal unless they have the same index set. Here we follow the classical convention that an index set with n elements will be { 1, 2, .., n}, and thus a basis for M with n elements is a sequence S = {ui, .., un} or if you wish, S = (ui, .., ut) E M". Suppose M is an R-module with a basis of n elements. Recall there is a bijection a : HomR(R", M) - M" defined by a(h) (h(ei), .., h(en)). Now h : R" - M is an isomorphism iff a(h) is a basis for M. Summary The point of all this is that selecting a basis of n elements for M is the same as selecting an isomorphism from R" to M, and from this viewpoint, change of basis can be displayed by the diagram below. Endomorphisms on R" are represented by square matrices, and thus have a de- terminant and trace. Now suppose M is a f.g. free module and f : M - M is a homomorphism. In order to represent f by a matrix, we must select a basis for M (i.e., an isomorphism with R"). We will show that this matrix is well defined up to similarity, and thus the determinant, trace, and characteristic polynomial of f are well-defined.  84 Definition Suppose M is a free module, S = f :M - M is a homomorphism. The matrix A S is defined by f (u) = u1a1,2 + - - +unan,2. (Note the usual matrix associated with f). Linear Algebra Chapter 5 { 1, .., utt} is a basis for M, and (ai,5) E R of f w.r.t. the basis that if M = R" and u = e, A is Theorem Suppose T = {v1, .., vn} is another basis for M and B E Rn is the matrix of f w.r.t. T. Define C = (c,5) E R by vi = u1c1,i + - - +uncni. Then C is invertible and B - C-1AC, i.e., A and B are similar. Therefore |Al - |BI, trace(A)=trace(B), and A and B have the same characteristic polynomial (see page 66 of chapter 4). Conversely, suppose C = (c,5) E R is invertible. Define T = {v1, .., vn} by v2 = u1c1,i + - - +uncni. Then T is a basis for M and the matrix of f w.r.t. T is B = C-1AC. In other words, conjugation of matrices corresponds to change of basis. Proof The proof follows by seeing that the following diagram is commutative. B Rn Rn ev e2 Vi f M M C u29 U e2 A The diagram also explains what it means for A to be the matrix of f w.r.t. the basis S. Let h : R"h - M be the isomorphism with h(e2) = ui for 1 < i < n. Then the matrix A E Rn is the one determined by the endomorphism h1o f o h : R" - R". In other words, column i of A is h-1(f (h(ei))). An important special case is where M = R" and f: R"h - R" is given by some matrix W. Then h is given by the matrix U whose ith column is i and A U-1WU. In other words, W represents f w.r.t. the standard basis, and U-1WU represents f w.r.t. the basis {u1, .., un}. Definition Suppose M is a f.g. free module and f : M - M is a homomorphism. Define |fl to be |Al, trace(f) to be trace(A), and CPf(x) to be CPA(x), where A is  Chapter 5 Linear Algebra 85 the matrix of f w.r.t. some basis. By the previous theorem, all three are well-defined, i.e., do not depend upon the choice of basis. Exercise Let R Z and f Z2 - Z2 be defined by f(D) (= 0 1)D. Find the matrix of f w.r.t. the basis Exercise Let L C R2 be the line L = {(r, 2r)t r E R}. Show there is one and only one homomorphism f R2 - R2 which is the identity on L and has f((-1, 1)t) =_(1, -1)t. Find the matrix A E R2 which represents f with respect to the basis {(1, 2)t, (-1, 1)t}. Find the determinant, trace, and characteristic polynomial of f. Also find the matrix B E R2 which represents f with respect to the standard basis. Finally, find an invertible matrix C E R2 with B = C-1AC. Vector Spaces So far in this chapter we have been developing the theory of linear algebra in general. The previous theorem, for example, holds for any commutative ring R, but it must be assumed that the module M is free. Endomorphisms in general will not have a determinant, trace, or characteristic polynomial. We now focus on the case where R is a field F, and show that in this case, every F-module is free. Thus any finitely generated F-module will have a well-defined dimension, and endomorphisms on it will have well-defined determinant, trace, and characteristic polynomial. In this section, F is a field. F-modules may also be called vector spaces and F-module homomorphisms may also be called linear transformations. Theorem Suppose M is an F-module and v E M. Then v /Q iff v is independent. That is, if v E V and r E F, yr 0= implies v 0= in M or r 0= in F. Proof Suppose yr 0=0 and r / Q. Then Q= (vr)r-1 = v1i= v. Theorem Suppose M / 0 is an F-module and v E M. Then v generates M iff v is a basis for M. Furthermore, if these conditions hold, then M ~ FF, any non-zero element of M is a basis, and any two elements of M are dependent.  86 Linear Algebra Chapter 5 Proof Suppose v generates M. Then v 0 and is thus independent by the previous theorem. In this case M ~ F, and any non-zero element of F is a basis, and any two elements of F are dependent. Theorem Suppose M 0 is a finitely generated F-module. If S = {vi, .., Vm} generates M, then any maximal independent subsequence of S is a basis for M. Thus any finite independent sequence can be extended to a basis. In particular, M has a finite free basis, and thus is a free F-module. Proof Suppose, for notational convenience, that {v1, .., vn} is a maximal inde- pendent subsequence of S, and n < i < m. It must be shown that v2 is a linear combination of {v1, .., vn}. Since {v1, .., vn, v2} is dependent, E ri, ..., rn, r not all zero, such that v1r1+- -+vnrn+vir2 = 0. Then r2 / 0 and v2 = -(vir1 +-' -+vnrn)r1. Thus {v1, .., vn} generates S and thus all of M. Now suppose T is a finite indepen- dent sequence. T may be extended to a finite generating sequence, and inside that sequence it may be extended to a maximal independent sequence. Thus T extends to a basis. After so many routine theorems, it is nice to have one with real power. It not only says any finite independent sequence can be extended to a basis, but it can be extended to a basis inside any finite generating set containing it. This is one of the theorems that makes linear algebra tick. The key hypothesis here is that the ring is a field. If R = Z, then Z is a free module over itself, and the element 2 of Z is independent. However it certainly cannot be extended to a basis. Also the finiteness hypothesis in this theorem is only for convenience, as will be seen momentarily. Since F is a commutative ring, any two bases of M must have the same number of elements, and thus the dimension of M is well defined (see theorem on page 83). Theorem Suppose M is an F-module of dimension n, and {vi, ..., Vm} is an independent sequence in M. Then m < n and if m = n, {Vi, .., Vm} is a basis. Proof {vi, .., Vm} extends to a basis with n elements. The next theorem is just a collection of observations. Theorem Suppose M and N are finitely generated F-modules.  Chapter 5 Linear Algebra 87 1) M = F" iffdim(M) = n. 2) M = N iff dim(M) = dim(N). 3) Fm F" iff n = m. 4) dim (M (D N) = dim (MA) + dim(N). Here is the basic theorem for vector spaces in full generality. Theorem Suppose M -/ 0 is an F-module and S = {Vt}teT generates M. 1) Any maximal independent subsequence of S is a basis for M. 2) Any independent subsequence of S may be extended to a maximal independent subsequence of S, and thus to a basis for M. 3) Any independent subsequence of M can be extended to a basis for M. In particular, M has a free basis, and thus is a free F-module. Proof The proof of 1) is the same as in the case where S is finite. Part 2) will follow from the Hausdorff Maximality Principle. An independent subsequence of S is contained in a maximal monotonic tower of independent subsequences. The union of these independent subsequences is still independent, and so the result follows. Part 3) follows from 2) because an independent sequence can always be extended to a generating sequence. Theorem Suppose M is an F-module and K C M is a submodule. 1) K is a summand of M, i.e., E a submodule L of M with K D L = M. 2) If M is f.g., then dim(K) < dim(M) and K = M iff dim(K) = dim(M). Proof Let T be a basis for K. Extend T to a basis S for M. Then S-T generates a submodule L with K (D L = M. Part 2) follows from 1). Corollary Q is a summand of R. In other words, E a Q-submodule V C R with Q (D V = R as Q-modules. (See exercise on page 77.) Proof Q is a field, R is a Q-module, and Q is a submodule of R. Corollary Suppose M is a f.g. F-module, N is an F-module, and f : M -~ N is a homomorphism. Then dim(M) =dim(ker(f)) + dim(image(f)).  88 Linear Algebra Chapter 5 Proof Let K = ker(f) and L C M be a submodule with K (D L = M. Then f | L : L - image(f) is an isomorphism. Exercise Suppose R is a domain with the property that, for R-modules, every submodule is a summand. Show R is a field. Exercise Find a free Z-module which has a generating set containing no basis. Exercise The real vector space R2 is generated by the sequence S {(r, 0), (2, 1), (3, 2)}. Show there are three maximal independent subsequences of S, and each is a basis for R2. (Row vectors are used here just for convenience.) The real vector space R3 is generated by S = {(1, 1, 2), (1, 2, 1), (3, 4, 5), (1, 2, 0)}. Show there are three maximal independent subsequences of S and each is a basis for R3. You may use determinant. Square matrices over fields This theorem is just a summary of what we have for square matrices over fields. Theorem Suppose A E Fn and f : F" - F" is defined by f(B) = AB. Let vi,.., vn E F" be the columns of A, and wi, .., w E F"= F1,n be the rows of A. Then the following are equivalent. 1) {v1, .., vn} is independent, i.e., f is injective. 2) {v1, .., vn} is a basis for F", i.e., f is an automorphism, i.e., A is invertible, i.e., | A I f 0. 3) {v1, .., vn} generates F", i.e., f is surjective. it) {wi, .., wn} is independent. 2t) {Wi, .., Wm} is a basis for F", i.e., At is invertible, i.e., |At |f 0. 3t) {wi, .., wn} generates F".  Chapter 5 Linear Algebra 89 Proof Except for 1) and 1t), this theorem holds for any commutative ring R. (See the section Relating these concepts to square matrices, pages 81 and 82.) Parts 1) and 1t) follow from the preceding section. Exercise Add to this theorem more equivalent statements in terms of solutions of n equations in n unknowns. Overview Suppose each of X and Y is a set with n elements and f: X - Y is a function. By the pigeonhole principle, f is injective iff f is bijective iff f is surjective. Now suppose each of U and V is a vector space of dimension n and f: U - V is a linear transformation. It follows from the work done so far that f is injective iff f is bijective iff f is surjective. This shows some of the simple and definitive nature of linear algebra. Exercise Let A = (A1, .., An) be an n x n matrix over Z with column i = AZ E Z"h. Let f : Z" - Z" be defined by f(B) = AB and f : R" - R" be defined by f(C) = AC. Show the following are equivalent. (See the exercise on page 79.) 1) f : Z" - Z" is injective. 2) The sequence (A1, .., An) is linearly independent over Z. 3) |A# O. 4) f : R" - R" is injective. 5) The sequence (A1, .., An) is linearly independent over R. Rank of a matrix Suppose A E Fm,n. The row (column) rank of A is defined to be the dimension of the submodule of F" (Fm) generated by the rows (columns) of A. Theorem If C E Fm and D E Fn are invertible, then the row (column) rank of A is the same as the row (column) rank of CAD. Proof Suppose f :F"m - Fm is defined by f(B) =AB. Each column of A is a vector in the range Fm, and we know from page 81 that each f(B) is a linear  90 Linear Algebra Chapter 5 combination of those vectors. Thus the image of f is the submodule of Fm generated by the columns of A, and its dimension is the column rank of A. This dimension is the same as the dimension of the image of g o f o h : F" - Fm, where h is any automorphism on F" and g is any automorphism on Fm. This proves the theorem for column rank. The theorem for row rank follows using transpose. Theorem If A E Fm,n, the row rank and the column rank of A are equal. This number is called the rank of A and is 1. Since the constant term of CPf(x) is 0, the determinant of f is Q. Thus E a basis of V such that the matrix A representing f has its first column zero. Let B E Fn_1 be the matrix obtained from A by removing its first row and first column. Now CPA(x) --1n ccxCPB(x). Thus CPB(x) c- 1 and by induction on n, B is nilpotent and so E C such that C-1BC is strictly upper triangular. Then /1 0..Oj /0 ..*j \ /1 0.0j 0 * 0- 0 0 - C-1 B- C = - C-1BC \0 0 0 0 is strictly upper triangular. Exercise Suppose F is a field, A E F3 is a strictly lower triangular matrix of 0 0 0 rank 2, and B =(1 0 0 . Using conjugation by elementary matrices, show there 0 1 0 is an invertible matrix C so that C-1AC = B. Now suppose V is a 3-dimensional vector space and f : V - V is a nilpotent endomorphism of rank 2. We know f can be represented by a strictly lower triangular matrix. Show there is a basis {v1, v2, v3} for V so that B is the matrix representing f. Also show that f(vi) = v2, f(v2) = v3, and f(v3) = 0. In other words, there is a basis for V of the form {v, f(v), f2(v)} with f3(v) 0. Exercise Suppose V is a 3-dimensional vector space and f : V - V is a nilpotent endomorphism of rank 1. Show there is a basis for V so that the matrix representing f is 1 0 01. 0 0 0  Chapter 5 Linear Algebra 95 Eigenvalues Our standing hypothesis is that V is an n-dimensional vector space over a field F and f : V - V is a homomorphism. Definition An element A E F is an eigenvalue of f if E a non-zero v E V with f(v) = Av. Any such v is called an eigenvector. Ea C V is defined to be the set of all eigenvectors for A (plus 0). Note that E = ker(AI - f) is a subspace of V. The next theorem shows the eigenvalues of f are just the characteristic roots of f. Theorem If A E F then the following are equivalent. 1) A is an eigenvalue of f, i.e., (AI - f) : V - V is not injective. 2) |1(AI - f) |=Q. 3) A is a characteristic root of f, i.e., a root of the characteristic polynomial CPf(x) =| (xI - A) 1, where A is any matrix representing f. Proof It is immediate that 1) and 2) are equivalent, so let's show 2) and 3) are equivalent. The evaluation map F[x] - F which sends h(x) to h(A) is a ring homomorphism (see theorem on page 47). So evaluating (xI - A) at x = A and taking determinant gives the same result as taking the determinant of (xI - A) and evaluating at x= A. Thus 2) and 3) are equivalent. The nicest thing you can say about a matrix is that it is similar to a diagonal matrix. Here is one case where that happens. Theorem Suppose A1, .., Ak are distinct eigenvalues of f, and v2 is an eigenvector of Ai for 1 < i < k. Then the following hold. 1) {v1, .., vk} is independent. 2) If k = n, i.e., if CPf(x) = (x - A1) - - - (x -fAn), then {vi,..,v}is a basis for V. The matrix of f w.r.t. this basis is the diagonal matrix whose (i, i) term is Ai. Proof Suppose {v1, .., vk} is dependent. Suppose t is the smallest positive integer such that {vi, .., Vt} is dependent, and viri + - - +vtre 0 is a non-trivial linear combination. Note that at least two of the coefficients must be non-zero. Now (f - At)(vir1 + - +Vtre) =v1(A1 - At)r1+ ~- - +vt_1(At_1 - At)rt_1+ 0 =0 is a shorter  96 Linear Algebra Chapter 5 non-trivial linear combination. This is a contradiction and proves 1). Part 2) follows from 1) because dim(V) = n. Exercise Let A (= E R2. Find an invertible C E C2 such that C-1AC is diagonal. Show that C cannot be selected in R2. Find the characteristic polynomial of A. Exercise Suppose V is a 3-dimensional vector space and f : V - V is an endo- morphism with CPf(x) =_(x - A)3. Show that (f - AI) has characteristic polynomial x3 and is thus a nilpotent endomorphism. Show there is a basis for V so that the A 0 0 A 0 0 A 0 0 matrix representing f is 1A 0 ,1A 0 or 0A 0 0 1 A 0 0 A 0 0 A We could continue and finally give an ad hoc proof of the Jordan canonical form, but in this chapter we prefer to press on to inner product spaces. The Jordan form will be developed in Chapter 6 as part of the general theory of finitely generated modules over Euclidean domains. The next section is included only as a convenient reference. Jordan Canonical Form This section should be just skimmed or omitted entirely. It is unnecessary for the rest of this chapter, and is not properly part of the flow of the chapter. The basic facts of Jordan form are summarized here simply for reference. The statement that a square matrix B over a field F is a Jordan block means that I A E F such that B is a lower triangular matrix of the form /A 0\ 1 A B = - . B gives a homomorphism g : Fm - Fm with g(em) = Aem 0 1 A and g(ej) =esi1 + Aes for 1 Oandu"u=0iff u=0 for all u E V. Theorem Suppose V has an inner product. 1) If v E V, f : V -- R defined by f(u) v= - o is a homomorphism. Thus 0-v=0. 2) Schwarz' inequality. If u, v E V, (u . v)2 < (u . u)(v - v). Proof of 2) Let a = -v. vand b = u - u. If a or b is 0, the result is obvious. Suppose neither a nor b is 0. Now 0 < (ua + vb) - (ua + vb) = (u - u)a2 + 2ab(u -"v)+ (v -v)b2 = b2a2+2ab(u -v)+a2b2. Dividing by 2ab yields 0 < ab+k (u -v) or | u-v |I 1). Show 1) -> 2). Suppose A is a symmetric 2 x 2 matrix. Let A be an eigenvalue for A and {vi, v2} be an orthonormal basis for R2 with Avi = Av1. Then w.r.t this basis, the transformation determined by A is represented by ( d ). Since this matrix is symmetric, b = 0. Now suppose by induction that the theorem is true for symmetric matrices in Rt for t < n, and suppose A is a symmetric n x n matrix. Denote by A1, .., Ak the distinct eigenvalues of A, k 1 such that It = Ito for all t > to. Proof Suppose 1) is true and show 3). The ideal I = I1 U I2 U ... is finitely generated and E to > 1 such that Ito contains those generators. Thus 3) is true. Now suppose 2) is true and show 1). Let I be an ideal of R, and consider the collection of all finitely generated ideals contained in I. By 2) there is a maximal one, and it must be I itself, and thus 1) is true. We now have 2)=1)=3), so suppose 2) is false and show 3) is false. So there is a collection of ideals of R such that any ideal in the collection is properly contained in another ideal of the collection. Thus it is possible to construct a sequence of ideals I1 c I2 C I... with each properly contained in the next, and therefore 3) is false. (Actually this construction requires the Hausdorff Maximality Principle or some form of the Axiom of Choice, but we slide over that.) Definition If R satisfies these properties, R is said to be Noetherian, or it is said to satisfy the ascending chain condition. This property is satisfied by many of the classical rings in mathematics. Having three definitions makes this property useful and easy to use. For example, see the next theorem. Theorem A Noetherian domain is a FD. In particular, a PID is a FD. Proof Suppose there is a non-zero non-unit element that does not factor as the finite product of irreducibles. Consider all ideals dR where d does not factor. Since R is Noetherian, 2 a maximal one cR. The element c must be reducible, i.e., c =ab where neither a nor b is a unit. Each of aR and bR properly contains cR, and so each  Chapter 6 Appendix 113 of a and b factors as a finite product of irreducibles. This gives a finite factorization of c into irreducibles, which is a contradiction. Corollary A PID is a UFD. So Z is a UFD and if F is a field, F[z] is a UFD. You see the basic structure of UFDS is quite easy. It takes more work to prove the following theorems, which are stated here only for reference. Theorem If R is a UFD then R[xi, ..., x] is a UFD. Thus if F is a field, F[zi, ..., x] is a UFD. (This theorem goes all the way back to Gauss.) If R is a PID, then the formal power series R[[xi, ..., x]] is a UFD. Thus if F is a field, F[[xi, ..., x]] is a UFD. (There is a UFD R where R[[x]] is not a UFD. See page 566 of Commutative Algebra by N. Bourbaki.) Theorem Germs of analytic functions on C" form a UFD. Proof See Theorem 6.6.2 of An Introduction to Complex Analysis in Several Vari- ables by L. Hbrmander. Theorem Suppose R is a commutative ring. Then R is Noetherian =- R[xi, ..., zn] and R[[xi, ..., x]] are Noetherian. (This is the famous Hilbert Basis Theorem.) Theorem If R is Noetherian and I C R is a proper ideal, then R/I is Noetherian. (This follows immediately from the definition. This and the previous theorem show that Noetherian is a ubiquitous property in ring theory.) Domains With Non-unique Factorizations Next are presented two of the standard examples of Noetherian domains that are not unique factorization domains. Exercise Let R = Z(5) = {n + m 5: n, m E Z}. Show that R is a subring of R which is not a UFD. In particular 2 - 2 = (1 - 5) - (-1 - 5) are two distinct irreducible factorizations of 4. Show R is isomorphic to Z[z]/(x2 - 5), where (xc2 - 5) represents the ideal (xc2 - 5)Z[z], and R/(2) is isomorphic to Z2[z]/(x2 - [5])= Z2[z]/(x2 + [1]), which is not a domain.  114 Appendix Chapter 6 Exercise Let R = R[x, y, z]/(x2 - yz). Show x2 - yz is irreducible and thus prime in R[x, y, z]. If u E R[x, y, z], let u E R be the coset containing u. Show R is not a UFD. In particular 2 - 2x= y - 2 are two distinct irreducible factorizations of 22. Show R/(z-) is isomorphic to R[y, z]/(yz), which is not a domain. An easier approach is to let f R[x, y, z] - R[x, y] be the ring homomorphism defined by f(x) xy, f(y) = x2, and f(z) = y2. Then S = R[xy, x2,y2] is the image of f and S is isomorphic to R. Note that xy, x2, and y2 are irreducible in S and (xy)(xy) = (x2)(y2) are two distinct irreducible factorizations of (xy)2 in S. Exercise In Group Theory If G is an additive abelian group, a subgroup H of G is said to be maximal if H f G and there are no subgroups properly between H and G. Show that H is maximal iff G/H ~ Z, for some prime p. For simplicity, consider the case G = Q. Which one of the following is true? 1) If a E Q, then there is a maximal subgroup H of Q which contains a. 2) Q contains no maximal subgroups. Splitting Short Exact Sequences Suppose B is an R-module and K is a submodule of B. As defined in the chapter on linear algebra, K is a summand of B provided E a submodule L of B with K+ L B and KOn1L = 0. In this case we write K(D L = B. When is K a summand of B? It turns out that K is a summand of B iff there is a splitting map from B/K to B. In particular, if B/K is free, K must be a summand of B. This is used below to show that if R is a PID, then every submodule of R" is free. Theorem 1 Suppose R is a ring, B and C are R-modules, and g: B -- C is a surjective homomorphism with kernel K. Then the following are equivalent. 1) K is a summand of B. 2) g has a right inverse, i.e., E a homomorphism h : C - B with g o h = I: C - C. (h is called a splitting map.) Proof Suppose 1) is true, i.e., suppose E a submodule L of B with K D L = B. Then (g|L) L -- C is an isomorphism. If i : L - B is inclusion, then h defined by h =i o (g|L)-1 is a right inverse of g. Now suppose 2) is true and h :C -~ B is a right inverse of g. Then h is injective, K + h(C) =B and K 0 h(C) =0. Thus K eh(C) =B.  Chapter 6 Appendix 115 Definition Suppose f: A - B and g: B - C are R-module homomorphisms. The statement that 0 - A L B C - 0 is a short exact sequence (s.e.s) means f is injective, g is surjective and f(A) = ker(g). The canonical split s.e.s. is A - A e C - C where f = i1 and g =wgr2. A short exact sequence is said to split if E an isomorphism B - A e C such that the following diagram commutes. 0- A -B g C -0 21 7T2 We now restate the previous theorem in this terminology. Theorem 1.1 A short exact sequence 0 - A - B - C - 0 splits iff f(A) is a summand of B, iff B - C has a splitting map. If C is a free R-module, there is a splitting map and thus the sequence splits. Proof We know from the previous theorem f(A) is a summand of B iff B - C has a splitting map. Showing these properties are equivalent to the splitting of the sequence is a good exercise in the art of diagram chasing. Now suppose C has a free basis T C C, and g: B - C is surjective. There exists a function h: T - B such that g o h(c) = c for each c E T. The function h extends to a homomorphism from C to B which is a right inverse of g. Theorem 2 If R is a domain, then the following are equivalent. 1) R is a PID. 2) Every submodule of RR is a free R-module of dimension < 1. This theorem restates the ring property of PID as a module property. Although this theorem is transparent, 1)-2) is a precursor to the following classical result. Theorem 3 If R is a PID and A C R" is a submodule, then A is a free R-module of dimension 1 and the theorem is true for submodules of R"-1. Suppose A c R"h is a submodule.  116 Appendix Chapter 6 Consider the following short exact sequences, where f : R"-1 - R"-1( R is inclusion and g =w7 : R"-1 D R -- R is the projection. 0 -R"-1 _f )R"-1 (D R -+R 0 A n-1 ) A (A) 0 By induction, A n R"-1 is free of dimension < n - 1. If 7(A) =Q, then A C R"-1. If 7(A) / 0, it is free of dimension 1 and thus the sequence splits by Theorem 1.1. In either case, A is a free submodule of dimension #(r) < #(b) which is impossible. Thus r 0= and a E bR so I = bR. Theorem 2 If R is a Euclidean domain and a, b E R - 0, then #(1) is the smallest integer in the image of #. a is a unit in R iff #(a) =(1). a and b are associates - #(a) - #(b). Proof This is a good exercise. However it is unnecessary for Theorem 3 below. The following remarkable theorem is the foundation for the results of this section. Theorem 3 If R is a Euclidean domain and (a,5) E Rn, is a non-zero matrix, then by elementary row and column operations (ai,5) can be transformed to ( d1 0 0 d2 o \ dm 0 \ 0 0J) where each d2 0, and dIld2+1 for 1 < i < m. Also d1 generates the ideal of R generated by the entries of (ai,i). Proof Let I C R be the ideal generated by the elements of the matrix A = (aj,). If E E Rn, then the ideal J generated by the elements of EA has J C I. If E is invertible, then J= I. In the same manner, if E E Rt is invertible and J is the ideal generated by the elements of AE, then J = I. This means that row and column operations on A do not change the ideal I. Since R is a PID, there is an element d1 with I = d1R, and this will turn out to be the d1 displayed in the theorem. The matrix (ai,5) has at least one non-zero element d with #(d) a miminum. However, row and column operations on (ai,5) may produce elements with smaller  118 Appendix Chapter 6 # values. To consolidate this approach, consider matrices obtained from (ai,5) by a finite number of row and column operations. Among these, let (b2,i) be one which has an entry di l 0 with #(di) a minimum. By elementary operations of type 2, the entry di may be moved to the (1, 1) place in the matrix. Then di will divide the other entries in the first row, else we could obtain an entry with a smaller # value. Thus by column operations of type 3, the other entries of the first row may be made zero. In a similar manner, by row operations of type 3, the matrix may be changed to the following form. di 0 ... 0 0 cii 0 Note that di divides each c2,j, and thus I = d1R. The proof now follows by induction on the size of the matrix. This is an example of a theorem that is easy to prove playing around at the blackboard. Yet it must be a deep theorem because the next two theorems are easy consequences. Theorem 4 Suppose R is a Euclidean domain, B is a finitely generated free R- module and A C B is a non-zero submodule. Then E free bases {ai, a2, ..., at} for A and {b1, b2, ..., bn} for B, with t t. The composition Rt A B R" e v2 w2 e2 is represented by a matrix (ai,5) E Ra where vi ai,iwi + a2,iw2 + - - - + ania Dy the previous theorem, 2 invertible matrixes U E Ra and V E Re such that  Chapter 6 Appendix 119 di 0 ... 0 0 d2 0 U(assV= : 0 '". dit \ 0 -.-.-0 / with d2ld2+1. Since changing the isomorphisms Rt A and B R" corresponds to changing the bases {v1, v2, ..., Vt} and {w1, w2, ..., wn}, the theorem follows. Theorem 5 If R is a Euclidean domain and M is a finitely generated R-module, then M z R/d1(D R/d2 D"" "(D-R/dt(DR'" where each d 0, and diIdi+1 for 1 1. Then the R-module R/ps has no proper submodule which is a summand. Torsion Submodules This will give a little more perspective to this section. Definition Suppose M is a module over a domain R. An element m E M is said to be a torsion element if E r E R with r -/ 0 and mr = 0. This is the same as saying m is dependent. If R = Z, it is the same as saying m has finite order. Denote by T(M) the set of all torsion elements of M. If T(M) = 0, we say that M is torsion free. Theorem 7 Suppose M is a module over a domain R. Then T(M) is a submodule of M and M/T(M) is torsion free. Proof This is a simple exercise. Theorem 8 Suppose R is a Euclidean domain and M is a R-module which is torsion free. Then M is a free R-module, i.e., Proof This follows immediately from Theorem 5. Theorem 9 Suppose R is a Euclidean domain and M is a R-module. Then the following s.e.s. splits. finitely generated M ~Rm. finitely generated 0 - T(M) - M - M/T(M) -) 0 Proof By Theorem 7, M/T(M) is torsion free. By Theorem 8, M/T(M) is a free R-module, and thus there is a splitting map. Of course this theorem is transparent anyway, because Theorem 5 gives a splitting of M into a torsion part and a free part.  Chapter 6 Appendix 121 Note It follows from Theorem 9 that E a free submodule V of M such that T(M) + V = M. The first summand T(M) is unique, but the complementary summand V is not unique. V depends upon the splitting map and is unique only up to isomorphism. To complete this section, here are two more theorems that follow from the work we have done. Theorem 10 Suppose T is a domain and T* is the multiplicative group of units of T. If G is a finite subgroup of T*, then G is a cyclic group. Thus if F is a finite field, the multiplicative group F* is cyclic. Thus if p is a prime, (Z,)* is cyclic. Proof This is a corollary to Theorem 5 with R = Z. The multiplicative group G is isomorphic to an additive group Z/di l+ Z/d2 e+ o""" D Z/dt where each d2 > 1 and d ldi+1 for 1 < i < t. Every u in the additive group has the property that udt = 0. So every g E G is a solution to xdt - 1 = 0. If t > 1, the equation will have degree less than the number of roots, which is impossible. Thus t = 1 and so G is cyclic. Exercise For which primes p and q is the group of units (Z, x Zq)* a cyclic group? We know from Exercise 2) on page 59 that an invertible matrix over a field is the product of elementary matrices. This result also holds for any invertible matrix over a Euclidean domain. Theorem 11 Suppose R is a Euclidean domain and A E Rn is a matrix with non-zero determinant. Then by elementary row and column operations, A may be transformed to a diagonal matrix /di 0\ d2 \0 do where each di / 0 and dildi for 1 i < ni. Also di generates the ideal generated by the entries of A. Furthermore A is invertible iff each di is a unit. Thus if A is invertible, A is the product of elementary matrices.  122 Appendix Chapter 6 Proof It follows from Theorem 3 that A may be transformed to a diagonal matrix with dljd2+1. Since the determinant of A is not zero, it follows that each d2 0. Furthermore, the matrix A is invertible iff the diagonal matrix is invertible, which is true iff each d2 is a unit. If each d2 is a unit, then the diagonal matrix is the product of elementary matrices of type 1. Therefore if A is invertible, it is the product of elementary matrices. 3 11 3 11 Exercise Let R Z, A ( J0 4 and D .4Perform elementary operations on A and D to obtain diagonal matrices where the first diagonal element divides the second diagonal element. Write D as the product of elementary matri- ces. Find the characteristic polynomials of A and D. Find an elementary matrix B over Z such that B-1AB is diagonal. Find an invertible matrix C in R2 such that C-1DC is diagonal. Show C cannot be selected in Q2. Jordan Blocks In this section, we define the two special types of square matrices used in the Rational and Jordan canonical forms. Note that the Jordan block B(q) is the sum of a scalar matrix and a nilpotent matrix. A Jordan block displays its eigenvalue on the diagonal, and is more interesting than the companion matrix C(q). But as we shall see later, the Rational canonical form will always exist, while the Jordan canonical form will exist iff the characteristic polynomial factors as the product of linear polynomials. Suppose R is a commutative ring, q = ao + a1x + - - - + an_1x"-1 + Xz E R[x] is a monic polynomial of degree n ;> 1, and V is the R[x]-module V = R[x]/q. V is a torsion module over the ring R[x], but as an R-module, V has a free basis {1, x, x2,..., x"-1}. (See the last part of the last theorem on page 46.) Multipli- cation by x defines an R-module endomorphism on V, and C(q) will be the ma- trix of this endomorphism with respect to this basis. Let T : V - V be defined by T(v) v=oz. If h(x) E R[x], h(T) is the R-module homomorphism given by multiplication by h(x). The homomorphism from R[x]/q to R[x]/q given by multiplication by h(x), is zero iff h(x) E qR[x]. That is to say q(T) = a0I+ a1T+ - - - + T"n is the zero homomorphism, and h(T) is the zero homomorphism iff h(xc) E qR[zc]. All of this is supposed to make the next theorem transparent. Theorem Let V have the free basis {1, , x2, ..., x"-1}. The companion matrix  Chapter 6 Appendix 123 representing T is C(q) [ 0 1 0 0 ... ... 0 -ao 0 ... 0 -a1 1 0 -a2 ... .... 1 -an_1 The characteristic polynomial of C(q) is q, R[x], h(C(q)) is zero iff h(x) E qR[x]. and |C(q)|= (-1)" ao. Finally, if h(x) E Theorem {1, (x - A), (x Suppose A E R and q(x) = (x - A)". Let V have the free basis - A)2,..., (x - A)"-1}. Then the matrix representing T is B(q)_ = A 1 0 0 0 A 1 0 A ... o ...o0 1 A I The characteristic polynomial of B(q) is q, and h(x) E R[x], h(B(q)) is zero iff h(x) E qR[x]. Note For n = 1, C(ao + z) = B(ao + z)b=z(- block matrix may be the zero matrix. |B(q)|= A" (-1)"ao. Finally, if -ao). This is the only case where a Note In B(q), if you wish to have the 1 above the diagonal, reverse the order of the basis for V. Jordan Canonical Form We are finally ready to prove the Rational and Jordan forms. Using the previous sections, all that's left to do is to put the pieces together. (For an overview of Jordan form, read first the section in Chapter 5, page 96.)  124 Appendix Chapter 6 Suppose R is a commutative ring, V is an R-module, and T V - V is an R-module homomorphism. Define a scalar multiplication V x R[z] - V by v(ao + aix + ---"+ arxr) =vao+T(v)a1+ ---"+T'(v)ar. Theorem 1 Under this scalar multiplication, V is an R[x]-module. This is just an observation, but it is one of the great tricks in mathematics. Questions about the transformation T are transferred to questions about the module V over the ring R[x]. And in the case R is a field, R[x] is a Euclidean domain and so we know almost everything about V as an R[x]-module. Now in this section, we suppose R is a field F, V is a finitely generated F-module, T : V -- V is a linear transformation and V is an F[x]-module with vxz= T(v). Our goal is to select a basis for V such that the matrix representing T is in some simple form. A submodule of VF[z] is a submodule of VF which is invariant under T. We know VF[z] is the sum of cyclic modules from Theorems 5 and 6 in the section on Euclidean Domains. Since V is finitely generated as an F-module, the free part of this decomposition will be zero. In the section on Jordan Blocks, a basis is selected for these cyclic modules and the matrix representing T is described. This gives the Rational Canonical Form and that is all there is to it. If all the eigenvalues for T are in F, we pick another basis for each of the cyclic modules (see the second theorem in the section on Jordan Blocks). Then the matrix representing T is called the Jordan Canonical Form. Now we say all this again with a little more detail. From Theorem 5 in the section on Euclidean Domains, it follows that VF[z] ~F[x]/d1 D F[x]/d2 D ... D F[x]/dt where each d2 is a monic polynomial of degree;> 1, and dIl di+1. Pick {1, x, .. . , X"m-1} as the F-basis for F[z]/di where m is the degree of the polynomial d2. Theorem 2 With respect to this basis, the matrix representing T is C(di) C(d2) C(de)  Chapter 6 Appendix 125 The characteristic polynomial of T is p = did2... dt and p(T) of canonical form but it does not seem to have a name. 0. This is a type Now we apply Theorem 6 to each F[x]/di. This gives VF[z] F[x]/p' . ..-e F[z]/psr where the p2 are irreducible monic polynomials of degree at least 1. The p2 need not be distinct. Pick an F-basis for each F[z]/p2i as before. Theorem 3 With respect to this basis, the matrix representing T is C(p1) C(p2) 0 0 C(ps) The characteristic polynomial of T is p the Rational canonical form for T. pi ... pSr and p(T) 0. This is called Now suppose the characteristic polynomial of T factors in F[z] as the product of linear polynomials. Thus in the Theorem above, pi = x - Ai and VF[z] Z F[z]/(x - A1)" D... F[z]/(x - A,)'r is an isomorphism of F[z]-modules. Pick {1, (x - AZ), (x - A)2,..., (x the F-basis for F[z]/(x - AZ)si where m is si. AZ)'m-1} as Theorem 4 With respect to this basis, the matrix representing T is ( B((x - A1)s1) 0 B((x - A2)2) 0 B((x - 8A)r) )  126 Appendix Chapter 6 The characteristic polynomial of T is p = (x - A1)81 ... ( - Ar)Sr and p(T) =Q. This is called the Jordan canonical form for T. Note that the )2 need not be distinct. Note A diagonal matrix is in Rational canonical form and in Jordan canonical form. This is the case where each block is one by one. Of course a diagonal matrix is about as canonical as you can get. Note also that if a matrix is in Jordan form, its trace is the sum of the eigenvalues and its determinant is the product of the eigenvalues. Finally, this section is loosely written, so it is important to use the transpose principle to write three other versions of the last two theorems. Exercise Suppose F is a field of characteristic 0 and T E Fn has trace(T) 0=0 for 0 < i < n. Show T is nilpotent. Let p E F[z] be the characteristic polynomial of T. The polynomial p may not factor into linears in F[x], and thus T may have no conjugate in Fn which is in Jordan form. However this exercise can still be worked using Jordan form. This is based on the fact that there exists a field F containing F as a subfield, such that p factors into linears in F[x]. This fact is not proved in this book, but it is assumed for this exercise. So E an invertible matrix U E F so that U-1TU is in Jordan form, and of course, T is nilpotent iff U-1TU is nilpotent. The point is that it sufficies to consider the case where T is in Jordan form, and to show the diagonal elements are all zero. So suppose T is in Jordan form and trace (Ti) 0= for 1 < i < n. Thus trace (p(T)) = aon where ao is the constant term of p(x). We know p(T) 0= and thus trace (p(T)) = 0, and thus aon = 0. Since the field has characteristic 0, ao = 0 and so 0 is an eigenvalue of T. This means that one block of T is a strictly lower triangular matrix. Removing this block leaves a smaller matrix which still satisfies the hypothesis, and the result follows by induction on the size of T. This exercise illustrates the power and facility of Jordan form. It also has a cute corollary. Corollary Suppose F is a field of characteristic 0, n > 1, and (A1, A2, .., An) E F" satisfies Al + A2 + - - +A = Q0for each 1 2, and B1, B2, ... , B, is a sequence of R-modules. Definition A map f : B1 e B2 " -". - - B - C is R-multilinear means that if 1 < i < n, and b3 E B3 for j - i, then fl(bi, b2,..., B ,..., bn) defines an R-linear map from BZ to C. Theorem The set of all R-multilinear maps is an R-module. Proof From the first exercise in Chapter 5, the set of all functions from Bi e B2 E9 - - - @ Bn to C is an R-module (see page 69). It must be seen that the R-multilinear maps form a submodule. It is easy to see that if fi and f2 are R-multilinear, so is fi + f2. Also if f is R-multilinear and r E R, then (fr) is R-multilinear. From here on, suppose B1 = B2 =- - - = B= =B. Definition 1) f is symmetric means f (bi, . .. , be) =f (bT(1), ... , br~s) for all permutations T on {1, 2, . .. , n}. 2) f is skew-symmetric if f (bi, . .. , be) =sign(T)f (bT(), . .. , b<~s) for all T.  Chapter 6 Appendix 129 3) f is alternating if f(b1,. . . , bn) = 0 whenever some b = b3 for i-j. Theorem i) Each of these three types defines a submodule of the set of all R-multilinear maps. ii) Alternating - skew-symmetric. iii) If no element of C has order 2, then alternating < skew-symmetric. Proof Part i) is immediate. To prove ii), assume f is alternating. It sufficies to show that f(bi, ..., bn) = -f(bT(l), ..., bT(n)) where T is a transposition. For simplicity, assume T = (1,2). Then 0 = f(b1 + b2, b1 + b2, b3, ..., bn) = f (bi, b2, b3, ..., bn) + f (b2, b1, b3, ..., bn) and the result follows. To prove iii), suppose f is skew symmetric and no element of C has order 2, and show f is alternating. Suppose for convenience that b1 = b2 and show f (bi, bi, b3, ... , bn) = 0. If we let T be the transposition (1, 2), we get f(b1, b1, b3,. . . , b) = -f (bi,b1,b3,. . .,bn), and so 2f(bi,b1,b3,. . .,b) = , and the result follows. Now we are ready for determinant. Suppose C = R. In this case multilinear maps are usually called multilinear forms. Suppose B is R" with the canonical basis {ei, e2, ... , en}. (We think of a matrix A E Rn as n column vectors, i.e., as an element of B ( B ( - - -" B.) First we recall the definition of determinant. Suppose A = (as,5) E R. Define d : BBB " . -e B - R by d(a1,1e1+a2,1e2+- - an,1en, ....., ainei + a2,ne2 +... + an,Zen)all Tsign(T)(aT(1),1aT(2),2... aT(n),n) =A The next theorem follows from the section on determinants on page 61. Theorem d is an alternating multilinear form with d(ei, e2, ... , en) = 1. If c E R, dc is an alternating multilinear form, because the set of alternating forms is an R-module. It turns out that this is all of them, as seen by the following theorem. Theorem Suppose f : B eD B eB ... B - R is an alternating multilinear form. Then f = dff(ei, e2, ... , en). This means f is the multilinear form d times the scalar f (ei, e2, ..., en). In other words, if A =(ai,5) E R., then f (ai,1ei + a2,1e2 + - - + .n1n .., ai,se2 + a2,ne2 + - - + ansn = A lf (ei, e2, ..., en). Thus the set of alter- nating forms is a free R-module of dimension 1, and the determinant is a generator.  130 Appendix Chapter 6 Proof For n = 2, you can simply write it out. f(ai,iei + a2,1e2, a1,2e1 + a2,2e2) a1,1ai,2f (ei, ei) + a1,1a2,2f(ei, e2) + a2,1ai,2f (e2, ei) + a2,1a2,2f (e2, e2) = (ai,1a2,2- ai,2a2,i)f(ei, e2) =|A lf (ei, e2). For the general case, f(ai,iei + a2,1e2 + -- + an,1en, ....., ainei + a2,ne2+ - - - + an, en) = a21,1ai2,2 .. - annf (e e2, -..., en) where the sum is over all1 < i1 M* with respect to the dual bases, is given by At.  Chapter 6 Appendix 133 Proof Note that g*(w2) is a homomorphism from M to R. Evaluation on v gives g*(w2)(vj) =_(w og)(vj) = w2(g(vj)) = w(ai, jwi+---+an wn) = asj. Thus g*(w2) - a2,1v* + - - - + ai,mv,, and thus g* is represented by At. Exercise If U is an R-module, define # : U* e U - R by #u(f, u) = f(u). Show that #bU is R-bilinear. Suppose g: M - N is an R-module homomorphism, f E N* and v E M. Show that #N9(f ,Mg9(v))-(g*(f)v) Now suppose M N = R" and g : R" - R" is represented by a matrix A E R . Suppose f E (R")* and v E R". Use the theorem above to show that #q: (R")* eR" - R has the property #(f, Av) =q#(Atff, v). This is with the elements of R" and (R")* written as column vectors. If the elements of R" are written as column vectors and the elements of (RTh)* are written as row vectors, the formula is #(f, Av) =q#(fA, v). Of course this is just the matrix product fAv. Dual spaces are confusing, and this exercise should be worked out completely. Definition "Double dual" is a "covariant" functor, i.e., if g : M- N is a homomorphism, then g** : M** > N**. For any module M, define a : M -M** by a(m) : M* - R is the homomorphism which sends f E M* to f(m) E R, i.e., a(m) is given by evaluation at m. Note that a is a homomorphism. Theorem If M and N are R-modules and g : M - N is a homomorphism, then the following diagram is commutative. a M-M** 9{g** a N-N** Proof On M, a is given by a(v) =OM(-, v). On N, a(u)=u) The proof follows from the equation bN(f M(V)) -(g*(f), v). Theorem If M is a free R-module with a finite basis {v1,...,v}, then a : M -~ M** is an isomorphism. Proof {a(v1), . .. , a(vn)} is the dual basis of {v*, . .. , v*}, i.e., a(vi) =(ov )*.  134 Appendix Chapter 6 Note Suppose R is a field and C is the category of finitely generated vector spaces over R. In the language of category theory, a is a natural equivalence between the identity functor and the double dual functor. Note For finitely generated vector spaces, a is used to identify V and V**. Under this identification V * is the dual of V and V is the dual of V*. Also, if {v1,... , vn} is a basis for V and {v2, . . . , v*} its dual basis, then {v1,. . . , vn} is the dual basis for {v*, . .. , v*}. In general there is no natural way to identify V and V*. However for real inner product spaces there is. Theorem Let R = R and V be an n-dimensional real inner product space. Then #3: V - V* given by /3(v) = (v, -) is an isomorphism. Proof 3 is injective and V and V * have the same dimension. Note If 3 is used to identify V with V *, then #v : V* e V - R is just the dot product V eD V - R. Note If {v1,. . . , vn} is any orthonormal basis for V, {3(v1),... , 3(vn)} is the dual basis of {v1,. . . , vn}, that is 3(v2) v= o2. The isomorphism 3 : V - V* defines an inner product on V*, and under this structure, 3 is an isometry. If {v1,... , vn} is an orthonormal basis for V, {v*,..., v*} is an orthonormal basis for V*. Also, if U is another n-dimensional IPS and f : V - U is an isometry, then f* : U* -V* is an isometry and the following diagram commutes. V - V _ _ f* U -U Exercise Suppose R is a commutative ring, T is an infinite index set, and for each t E T, Rt = R. Show (eRt)* is isomorphic to RT =HfJRt. Now let teT teT T =Z+, R= R, and M =eR. Show M* is not isomorphic to M. tET  Index Abelian group, 20, 71 Algebraically closed field, 46, 97 Alternating group, 32 Ascending chain condition, 112 Associate elements in a domain, 47, 109 Automorphism of groups, 29 of modules, 70 of rings, 43 Axiom of choice, 10 Basis or free basis canonical or standard for R", 72, 79 of a module, 78, 83 Bij ective or one-to-one correspondence, 7 Binary operation, 19 Boolean algebras, 52 Boolean rings, 51 Cancellation law in a group, 20 in a ring, 39 Cartesian product, 2, 11 Cayley's theorem, 31 Cayley-Hamilton theorem, 66, 98, 125 Center of group, 22 Change of basis, 83 Characteristic of a ring, 50 Characteristic polynomial of a homomorphism, 85, 95 of a matrix, 66 Chinese remainder theorem, 50, 108 Classical adjoint of a matrix, 63 Cofactor of a matrix, 62 Comaximal ideals, 108, 120 Commutative ring, 37 Complex numbers, 1, 40, 46, 47, 97, 104 Conjugate, 64 Conjugation by a unit, 44 Contravariant functor, 131 Coproduct or sum of modules, 76 Coset, 24, 42, 74 Cycle, 32 Cyclic group, 23 module, 107 Determinant of a homomorphism, 85 of a matrix, 60, 128 Diagonal matrix, 56 Dimension of a free module, 83 Division algorithm, 45 Domain euclidean, 116 integral domain, 39 of a function, 5 principal ideal, 46 unique factorization, 111 Dual basis, 132 Dual spaces, 130 Eigenvalues, 95 Eigenvectors, 95 Elementary divisors, 119, 120 Elementary matrices, 58 135  136 Index Elementary operations, 57, 122 Endomorphism of a module, 70 Equivalence class, 4 Equivalence relation, 4 Euclidean algorithm, 14 Euclidean domain, 116 Evaluation map, 47, 49 Even permutation, 32 Exponential of a matrix, 106 Factorization domain (FD), 111 Fermat's little theorem, 50 Field, 39 Formal power series, 113 Fourier series, 100 Free basis, 72, 78, 79, 83 Free R-module, 78 Function or map, 6 bijective, 7 injective, 7 surjective, 7 Function space yT as a group, 22, 36 as a module, 69 as a ring, 44 as a set, 12 Fundamental theorem of algebra, 46 Gauss, 113 General linear group GL, (R), 55 Generating sequence in a module, 78 Generators of Z, 40 Geometry of determinant, 90 Gram-Schmidt orthonormalization, 100 Graph of a function, 6 Greatest common divisor, 15 Group, 19 abelian, 20 additive, 20 cyclic, 23 multiplicative, 19 symmetric, 31 Hausdorff maximality principle, 3, 87, 109 Hilbert, 113 Homogeneous equation, 60 Homormophism of groups, 23 of rings, 42 of modules, 69 Homomorphism of quotient group, 29 module, 74 ring, 44 Ideal left, 41 maximal, 109 of a ring, 41 prime, 109 principal, 42, 46 right, 41 Idempotent element in a ring, 49, 51 Image of a function, 7 Independent sequence in a module, 78 Index of a subgroup, 25 Index set, 2 Induction, 13 Injective or one-to-one, 7, 79 Inner product spaces, 98 Integers mod n, 27, 40 Integers, 1, 14 Invariant factors, 119 Inverse image, 7 Invertible or non-singular matrix, 55 Irreducible element, 47, 110 Isometries of a square, 26, 34 Isometry, 101 Isomorphism  Index 137 of groups, 29 of modules, 70 of rings, 43 Jacobian matrix, 91 Jordan block, 96, 123 Jordan canonical form, 96, 123, 125 Kernel, 28, 43, 70 Least common multiple, 17, 18 Linear combination, 78 Linear ordering, 3 Linear transformation, 85 Matrix elementary, 58 invertible, 55 representing a linear transformation, 84 triangular, 56 Maximal ideal, 109 independent sequence, 86, 87 monotonic subcollection, 4 subgroup, 114 Minimal polynomial, 127 Minor of a matrix, 62 Module over a ring, 68 Monomial, 48 Monotonic collection of sets, 4 Multilinear forms, 129 Multiplicative group of a finite field, 121 Nilpotent element, 56 homomorphism, 93 Noetherian ring, 112 Normal subgroup, 26 Odd permutation, 32 Onto or surjective, 7, 79 Order of an element or group, 23 Orthogonal group 0(n), 102 Orthogonal vectors, 99 Orthonormal sequence, 99 Partial ordering, 3 Partition of a set, 5 Permutation, 31 Pigeonhole principle, 8, 39 Polynomial ring, 45 Power set, 12 Prime element, 110 ideal, 109 integer, 16 Principal ideal domain (PID), 46 Principal ideal, 42 Product of groups, 34, 35 of modules, 75 of rings, 49 of sets, 2, 11 Projection maps, 11 Quotient group, 27 Quotient module, 74 Quotient ring, 42 Range of a function, 6 Rank of a matrix, 59, 89 Rational canonical form, 107, 125 Relation, 3 Relatively prime integers, 16 elements in a PID, 119 Right and left inverses of functions, 10 Ring, 38 Root of a polynomial, 46 Row echelon form, 59 Scalar matrix, 57  138 Index Scalar multiplication, 21, 38, 54, 71 Self adjoint, 103, 105 Short exact sequence, 115 Sign of a permutation, 60 Similar matrices, 64 Solutions of equations, 9, 59, 81 Splitting map, 114 Standard basis for R", 72, 79 Strips (horizontal and vertical), 8 Subgroup, 14, 21 Submodule, 69 Subring, 41 Summand of a module, 77, 115 Surjective or onto, 7, 79 Symmetric groups, 31 Symmetric matrix, 103 Torsion element of a module, 121 Trace of a homormophism, 85 of a matrix, 65 Transpose of a matrix, 56, 103, 132 Transposition, 32 Unique factorization, in principal ideal domains, 113 of integers, 16 Unique factorization domain (UFD), 111 Unit in a ring, 38 Vector space, 67, 85 Volume preserving homomorphism, 90 Zero divisor in a ring, 39