### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 274 Class Note for MA 11100 at Purdue

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 103 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 20 views.

## Similar to Course at Purdue

## Reviews for 274 Class Note for MA 11100 at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Abstract Algebra done Concretely Donu Arapura February 197 2004 Introduction I wrote these notes for my math 453 class since I couldn7t nd a book that covered basic abstract algebra with the level and emphasis that I wanted Rather than spending a lot of time on axiomatics and serious theorem proving I wanted to spend more time with examples simple applications and with making scenic detoursi I may have gotten a bit carried away with the detours and certainly there is more here than can be covered in a semester at a reasonable pacer However a lot of these side topics which I marked with a star can be skipped to save time In order to try to encourage students to play around with examples I tried to include some Maple code now and then But its role is secondary and it can be ignored without losing too much Also since I wanted to emphasize the mathematics rather than the algorithms I didnlt go out of my way to implement these things ef ciently If you nd typos or more serious errors send me email Donu Arapura dVbmathipurdueiedu Contents 1 Natural Numbers 114 Exercises 2 Principles of Counting 217 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 3 Integers and Abelian groups 311 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 4 Divisibility 414 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 5 Congruences 514 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 6 Linear Diophantine equations 617 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 7 Subgroups of Abelian groups 710 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 8 Commutative Rings 818 Exercises 9 A little Boolean Algebra 913 Exercises 10 Fields lOil2Exercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 11 Polynomials over a Field llillExercises i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 12 Quotients of Abelian groups 127 Exercises 12 15 17 18 19 21 22 24 25 27 28 31 32 33 35 36 37 39 41 13 Orders of Abelian groups 139 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 14 Linear Algebra over Zpquot 144 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 15 Nonabelian groups 157 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 16 Groups of Permutations 166 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 17 Symmetries of Platonic Solids 174 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 18 Counting Problems involving Symmetry 189 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 19 Proofs of theorems about group actions 193 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 20 Groups of 2 X 2 Matrices 207 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 21 Homomorphisms between groups 21 21Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 22 Groups of order 1 through 8 224 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 23 The Braid Group 236 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 24 The Chinese remainder theorem 24 11Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 25 Quotients of polynomial rings 257 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 26 The nite Fourier transform 263 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 27 Matrix Representations of Groups 276 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 28 The ring of Quaternions 286 Exercises i i i i i i i i i i i i i i i i i i i i i i i i i 43 44 46 48 50 52 54 57 58 60 62 64 65 66 67 69 70 72 74 75 76 78 79 81 82 83 84 86 87 89 91 29 Quaternions and the Rotation Group 295 Exercises A Sets and Functions B Maple Chapter 1 Natural Numbers We want to start With the basic rules or axioms of arithmetic in the set of natural numbers N 01 2 i i This Will form a model for much of What we will later We can add natural numbers and this operation satis es The commutative law nmmn 11 the associative law mnTmnT 12 the identity property for 0 0 n n 13 and the cancellation law ifmnmTthennT 14 We can now de ne m S n or equivalently n 2 m to mean that the equation n m T has a solution T E N The solution T is unique by the cancellation law and we can de ne n 7 m Ti Lemma 11 The Telatz39zm S satis es 1 The Teflexz39ve pTopeTty n S n 2 The thmsz39tz39ve pTopeTty if n S m and m S T then n S T PToof The equation n 0 n implies that n S n Suppose that n S m and m S T then the equations m n a and Tmb have solutions a b E N Therefore Tmbnabnab which implies n S Ti 1 We impose a few more rules about S which don7t follow from the de nition Antisymmetry mgnandngmimpliesmn 15 Linear ordering For any pair mnENm norn mi 16 Well ordering Any nonempty subset of N has a least element 17 It is this last property which makes the natural numbers speciali Often in proofs or in the construction of algorithms one has a situation where one constructs a decreasing sequence of natural numbers 11 gt 12 gt The well ordering property implies that this sequence will eventually stop We can use well ordering to prove the principle of mathematical inductioni Theorem 12 Let P Q N be a subset 1 fOEP andnl EPwhenevernEP thenPN 2 fOEP andnEP whenever0liunile PthenPN In practice this means that to prove a statement for all natural numbers say nn l T it7s enough to check it for 0 the initial step and then check that the statement holds for n 1 if it holds for n the induction step The second part gives a form of induction that7s less familiar but also usefuli To see this in action let7s prove the above equation using this formi It certainly holds when n 0 Suppose that we know the equation 0l2iiin 012mm W holds for all natural numbers m 01Hin 7 1 Take m n 7 1 above after adding n to both sides and simplifying we establish the equation for hold for m n Therefore it holds for all n Before giving the proof we make a few observations 1 can be de ned to be the least element of the set of nonzero natural numbers If we wanted to be fussy we should really impose the nonemptiness of this set as a ruler Therefore n f 0 implies that n 2 1 from which it follows that n ml for some m E N Proof 1 Suppose that P f N then the complement F N 7 P z E N l z P is nonemptyi Let n E F be the smallest elementi Then n f 0 since 0 6 Pi Therefore it m 1 Since m lt n it follows that m 6 P This implies that m 6 Pi By assumption m 1 would have to lie in Pi But this would be a contradiction 2 We choose F and n E F as above Since it is minimal it follows that 0 1 i i i n 7 1 6 Pi Therefore it E P which is again a contradiction 1 In a more systematic development of natural numbers we would de ne mul tiplication in terms of the more basic operations The idea is that zzzuizntimes To avoid confusion let us denote the right hand side by multh We reformu late this as an inductive or recursive de nition 0 if n 0 multi n 7 1 1 otherwise mum 18 This makes sense because of the following Proposition 13 Given a set A an element a E A and afunction g NgtltA 7gt A there exists a unique function f z N 7gt A satisfying a 0 fn gm 17167 1 otherwise One can make even more elaborate recursive de nitions where is spec i ed for some initial values of n and then a formula for general depending on earlier valuesi Such a recursive de nition is theoretically useful for estab lishing properties of the function It also has practical value in that it leads to a method for computing the function Namely one systematically calculates f0 161 H At each stage the required information for calculating has already been given For example the Fibonacci numbers are given by the sequence 112358m The pattern is that each number in the sequence is the sum of the previous two So the nth Fibonacci number is given by 1 if n 0 or n 1 fzbn fibm 2 fibn 7 1 otherwise 14 Exercises 1 Let multm be de ned as in 118 Prove that multm1n multm n n by induction on n treating m as constant 2 With the help of the previous problem7 prove that multm multn by induction on n treating m as constant This is the commutative laW for multiplication nm mm For the following problems assume all the standard rules of highschool algebra 3 Let Tn1 7 Sn1 ale Where 7 1 x3 7 1 x3 7 5 i 2 a Calculate and Fn by hand for n 0127 and check that Fn for these values b Repeat above for n 345 using Maple7 appendix Bi 4 Prove that Fn for all n E N Chapter 2 Principles of Counting Natural numbers are important because they can be used to count Given a natural number n E N let nzEleltn0l2n71 Let X be a set then we say that X has n elements or that le n if there exists a one to one correspondence f z 7gt X see appendix A for de nitions of these concepts If no such n exists then we say that X is an in nite set The rst problem is to show that le cannot have multiple values This is guaranteed by the following Theorem 21 If there exists a one to one correspondence f z 7gt m then n m Proof We will prove this by induction on the minimum M of n and m Suppose that M is zero Then n 0 or m 0 lfn 0 then 0 so that f z 0 7gt is onto It follows that m 0 If m 0 then f 1 I 0 7gt is onto so that n 0 Assume that M gt 0 and that the theorem holds for M 7 1 Then de ne g n71 7gt 72171 by 2 M if N lt fn 71gt 9 N 71 if N gt M 71gt This is a one to one correspondence therefore m 7 l n 7 l which implies m n D Lemma 22 If a nite set X can be written as a union of two disjoint subsets Y U Z disjoint means their intersection is empty then le lYl Proof Let f z 7gt Y and g z 7gt Z be one to one correspondences De ne h z n m 7gt X by 7 f if i lt n hz7 gi7n ifiZn This is a one to one correspondence D A partition of X is a decomposition of X as a union of subsets X Y1 U Y2 U Yn such that Yi and are disjoint whenever i f j Corollary 23 IfX Y1 U Y2 U Y7 is a partition then le lYll Corollary 24 ff X A Y is afunction then le Z lf 1yl yEY Proof The collection forms a partition of X D Next consider the cartesian product of two nite sets appendix A Theorem 25 IfX and Y are nite sets then lX gtlt Yl Proof Let p X X Y A Y be the projection map de ned by pzy y Then p 1y17y l I 6 X and Ly A I gives a one to one correspondence to X Therefore7 by the previous corollary7 lX X Yl Z lp 1yl lYHXl yEY D We want to outline a second proof For this proof7 we assume that X and Y for some mn E N Then we have to construct a one to one correspondence between gtlt and We de ne a map LqT qn 7 from gtlt A N Since 4 Sine l and 7 S n7 17 we have LqT lt milnnmn So we can regard F is a map from gtlt A which can visualized using the table L 0 l n l The fact that L is a one to one correspondence is proved by the next theorem which is usually called the division algorithm Although it s not an algorithm in the technical sense7 it is the basis of the algorithm for long division that one learns in school 10 Theorem 26 Let an E N with n f 0 then there exists a unique pair of natural numbers qr satisfying a qn r7 r lt n Furthermore ifa lt mn then 4 lt m r is called the remainder of division of a by n Proof Let Ra7qnlq ENand qng a Let r a7 qn be the smallest element of Rf Suppose r 2 n Then a qnr q 1n r 7 n means that r 7 it lies in Rt This is a contradiction therefore r lt n Suppose that a q n r with r lt n Then r E R so r 2 rl Then qn q n r 7 r implies that nq7 q r7 r So r 7r is divisible by n On the other hand 0 S r 7 r lt n But 0 is the only integer in this range divisible by n is 0 Therefore r r and qn q n which implies q 4quot For the last part7 suppose that a lt mni lf 4 2 m7 then a 2 qn 2 mn which is a contradiction D Since the r and 4 above are unique given a and n7 we can view them as func tions ra7 n and La7 ln Maple7 these functions are denoted by irema7 n and iqu0a7 n respectively 27 Exercises 1 Suppose that m n 101i Whatls L 15234 2 Given nite sets Y7 Zr Prove that lY U Zl lYl lZl 7 lY Zli 3 If B Q A7 prove that lA 7 Bl lAl 7 Use this to prove that the set of distinct pairs 11712 E X X X l 11 f 12 has le2 7 le elements 4 Suppose that a dice is rolled twice a In how many ways can a ve or six be obtained on the rst role b In how many ways can a ve or six be obtained in either or both rolls c In how many ways can the same number be rolled twice d In how many ways can different numbers be obtained for each roll 5 Prove corollary 23 by induction 11 Chapter 3 Integers and Abelian groups The set integers Z 7 2 71 0 1 is obtained by adding negative num bers to the set of natural numbers This makes arithmetic easier Addition satis es the rules 11 12 13 as before In addition there is new operation n gt gt in satisfying For each n E Z n in 0 31 The cancellation law becomes redundant as we will see We will now abstract this De nition 31 An Abelian group consists of a set A with an associative com mutative binary operation 96 and an identity element e E A satisfying a x e a and such that any element a has an inverse a which satis es a x a e Abelian groups are everywhere Here list a few some examples Let Q ab l a b E Z b 0 be the set of rational numbers the R the set of real numbers and C the set of complex numbers Example 32 The sets Z Q R or C with x and e 0 are Abelian groups Example 33 The set Qquot or R or C of nonzero rational or real or com plex numbers with x multiplication and e l is an Abelian group The inverse in this case is just the reciprocal Example 34 Let n be a positive integer Let Z al a2 anla1 an E Z We de ne a1anb1bn a1b1anbn and 0 0 Then Z becomes an Abelian group Z can be replaced by Q R or C and these examples are probably familiar from linear algebra Example 35 Let n be a positive integer Zn 0 1 n 7 1 Arrange these on the face of a clock We de ne a new kind of operation 69 called addition mod n To compute aGB b we set the time to a and then count o b hours We ll give a more precise description later Unlike the previous examples this is a nite Abelian group 12 Often especially in later sections we will simply use instead 69 because it easier to write We do this in the diagram below 022 321 123 220 Here s the addition table for Z31 GB 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 Notice that the table is symmetric ire interchanging rows with columns gives the same thing This is because the commutative law holds The fact that that 0 is the identity corresponds to the fact that the row corresponding 0 is identical to the top rowi There is one more notable feature of this table every row contains each of the elements 0 i i i 7 exactly once A table of elements with this property is called a latiu square As we will see this is always true for any Abelian group We can now de ne the precise addition law for Zni Given a b 6 Zn a 69 b Ta b n where 7 is the remainder introduced before When doing calculations in Maple we can use the mod operatori For exam ple to add 32 EB 12 in Z41 we just type 32 12 m0d41 Let n be a positive integer a complex number 2 is called an nth root of unity if z 1 Let Mn be the set of all nth roots of unity For example 2 1 71 and M4 171i7ii Example 36 Mn becomes an Abelizm group under multiplication To see that this statement make sense note that given two elements 21 22 6 Mn their product lies in un since 2122 1 and 121 6 Mn since 13 121 1 We can describe all the elements of Mn With the help of Eulerls formula 1 19 cos 9 isin 9 Lemma 37 Mn eielO 0 27 47 m nn n Proof The equation 2 1 can have at most n solutions since it has degree n we Will prove this later on So it s enough to verify that all of the elements on the right are really solutions Each element is of the form 2 em With 9 Zakn With Is an integer Then 2 Bing cos27rk isin27rk l D The lemmas says that the elements are equally spaced around the unit circle of C Since 6191 192 ei9192 multiplication amounts to adding the angles This sounds suspiciously like the preVious example We Will see they are essentially the same Lemma 38 Cancellation Suppose that A7 966 is an Abelian group Then abac impliesbc Proof By assumption7 there exists a With a 96 a a 96 a 6 Therefore aabaac aabaac 14 ebec bci D Corollary 39 Given a there is a unique element a called the inverse such that a 96 a e Lemma 310 The multiplication table of my Abeliau group A a17 a2 i i forms a symmetric latiu square Proof The symmetry follows from the commutative lawi Suppose that A a17 a2 i i Then the ith row of the table consists of ai ahai a i i H Given a 6 A7 the equation a ai a 96 a shows that a occurs somewhere in this rowi Suppose that it occurs twice7 that is ai aj ai ak a for aj aki Then this would contradict the cancellation lemma 1 Let A7 7 e be a group Given a E A and n E Z de ne a by aaiiiantimesifngt0 a eifn0 aaiiia7ntimesifnlt0 Often the operation on A is written as in which case the inverse of a is usually written as 7a and we write na instead of ant When A Z this noth ing but the definition of multiplication It s possible to prove the associative7 commutative and distributive laws for Z but well skip this 311 Exercises 1 Let A e7 a b with e7 a 12 distinct and the following multiplication table ls A an Abelian group Prove it7 or explain what goes wrong 2 Let A e7a with a f e and the following multiplication table e a e e a a a e 15 Is A an Abelian group Prove it7 or explain what goes wrong i Let A7 9 e be an Abelian groupi Let a denote the inverse of ai Prove that e 67 a a and a b a 96 bquot i With notation as above7 prove that any a for any natural number n by induction This proves a 1 a 1 a as one would hope i Let A7 966 and B7 7 e be two Abelian groupsi Let A X B an l a E Ab E B De ne a17b1 7122 a1 9mg 121 96122 and E e76 Prove that A X B7 E is an Abelian group This is called the direct product of A and Bi For example Z2 Z X Z i Write down the multiplication tables for M27M37M4 and 5 i An element w 6 Mn is called a primitive root if any element can be written as a power of am Check that e2m5 6 M5 is primitivei Determine all the others in this group 16 Chapter 4 Divisibility Given two integers a and b we say a divides b or that b is a multiple of a or alb if there exists an integer q with b aq Some basic properties divisibility are given in the exercises It is a much subtler relation than S A natural number p is called prime if p 2 2 and if the only natural numbers dividing are 1 and p itself Lemma 41 Every natural number n 2 2 is divisible by a prime Proof Let D m 1 mln and m 2 2 D is nonempty since it contains n Let p be the smallest element of D If p is not prime there exists dlp with 2 S d lt p Then d E D by exercise 1 of this chapter but this contradicts the minimality of p D Corollary 42 Euclid There are in nitely many primes Proof Suppose that are only nite many primes say 101102 pn Then con sider N p1p2 Pn 1 Then N must be divisible by a prime which would have to be one of the primes on the list Suppose it7s pk Then by exercise 2 1 N 7 plpg 10 would be divisible by pk but this is impossible 1 The following is half of the fundamental theorem of arithmetic What7s missing is the uniqueness statement and this will be proved later Corollary 43 Every natural number n 2 2 is a product of primes The statement will be proved by induction on n Note that we have to start the induction at n 2 This does not entail any new principles since we can change variables to m n 7 2 and do induction on m 2 0 Proof n 2 is certainly prime By induction we assume that the statement holds for any 2 S n lt n By the lemma n 107 with p prime and n a natural number If n p then we are done Otherwise n 2 2 so that it can be written as a product of primes Therefore the same goes for n pn D 17 The proofs can be turned into a method or algorithm for factoring an integer In fact its the obvious one Start with n try to divide by 2 3 4i i in ll If none of these work then n is prime Otherwise record the rst number say p which divides it its a prime factori Replace n by np and repeat Similarly we get an algorithm for testing whether n is prime by repeatly testing divisibility by 234 i i i n 7 1 Note that we can do slightly better ex 3 44 Exercises 1 Prove that l is transitive and that all implies that a S I provided that b gt 0 2i Prove that all and ale implies alb b 05 for any pair of integers b ci 3i Prove that in the above primality algorithm it7s enough to test divisibility by integers 235 7 i i i k where k is the biggest odd number S Let b 2 2 be an integer A base 1 expansion of a natural number N is a sum N anb an1b 1 i i i a0 where each ai is an integer satisfying 0 S ai lt 12 Base 10 decimal expansions are what we normally use but I 2816 are useful in computer science 4 Show that a0 is the remainder of division of N by 12 5 For any I 2 2 prove that any natural number N has a base 1 expansion by induction Use the division algorithm 6 Turn the proof around to nd a method for calculating the coef cients ail Find a base 8 expansion of 1234 7 The proof of corollary 42 suggests the following strategy for generating primes multiply the rst n consecutive primes and add 1 For example 2 l 2 3 l and 2 3 5 l are all primer Does this always work You can and probably should use a computer for this The isp rimez procedure in Maple can be used to test if z primeli 8 Modify the proof of corollary 42 to prove that for any prime p there exists aprimepltqulli 1Actually it uses a probabilistic test which could fail for really huge values of 1 But that won7t be a problem here 18 Chapter 5 Congruences Fix a positive integer n For doing computations in Zn with paper and pencil7 its very convenient to introduce the E symbol We will say that a En b if a 7 b is divisible by n7 or equivalently if a and 12 One can work with E symbol as one would for thanks to Proposition 51 The follow hold 1 En is reflexive ie 1 En z 2 En is symmetric ie 1 En y implies y En z 5 En is transitive ie 1 En y and y En 2 implies that 1 En z 4 IfaEnb anchn d then acEn bd Proof We prove the transitivity The other statements are left as an exer cise Suppose that 1 En y and y En I then I 7 y na and y7z nb for some ab E Z Then I72 z 7yy72 nab which proves that 1 En 2 1 A relation satisfying the rst three properties above is called an equivalence relation Lemma 52 Given an integer z and a positive integer n there exist a unique element 1 mod n E 01n 7 1 such that 1 En 1 mod n A warning about notation Our use of mad as an operator is consistent with the way its used in Maple but its not the way its used in most math books Typically7 they would write I E y mod n instead of 1 En y Proof First suppose I 2 0 In this case7 there are no surprises The division algorithm gives 1 qn r with r E 0 n 71 1 En r since it divides z 7 r So we can take 1 mod n r 19 Suppose that z lt 0 If I is divisible by n7 then we take zmodn 0 Suppose is z is not divisible by n7 then applying the division algorithm to 71 yields 71 qn T with 0 lt T lt n Therefore z7qn7T7qn7nn7T7qlnn7T with 0 lt n 7 T lt n So we can take 1 mod n n 7 T We leave it as an exercise to check the uniqueness 1 The proof shows that zmodn is just the remainder Tzn when I 2 0 When I lt 07 there doesn7t seem to be any clear consensus on what the remainder should be7 some people think it should be 1 mod n and others think it should be the negative number 7T7z7 n Maplels iTem follows the latter convention I 7gt 1 mod n can be visualized as follows when n 3 7372710123 1111111 0120120 The rule for adding in Zn is now quite easy with this notation Given Lye 017Hin71 relay zym0dn Now we can nally prove Theorem 53 Zn 0 is an Abelz39zm gToup PToof We assume that the variables I y2 E 017Hin 7 l Lets start with the easy properities rsti zEBy1ym0dnyzm0dnyz z0z0m0dnz Set 91 71 mod n Then7 either I 0 in which case 16991 00m0dn 07 or else I f 0 in which case 91 n 7 I so that 16991 1n7zm0dn0i Finally7 we have to prove the associative lawi We have y2 En yzmodn yEBz by de nition Therefore by proposition 5 1 zyz Enzy69z En 1yzm0dnm0dnzyz 20 On the other hand IyEn 1ym0dn IGBy so that zy23n zy23n zyzm0dn Iyz Since I y 2 I y 2 we can combine these congruences to obtain 169 6192 En WNW We can conclude that the two numbers are the same by the uniquess statement of lemma 5 2 1 54 Exercises 1 Given that September 4 2002 is a Wednesday calculate the day of the week of September 4 2012 using arithmetic in Z1 Note that 2004 2008 2012 are leap years 2 Finish the proof of proposition Bill 3 Prove the uniqueness part oflemma 52 ie suppose that y 2 E 0 li i n7 1 both satisfy 1 En y and 1 En z prove that y 2i 4 Prove that if a En b and 5 En d then ac En 12d 5 Let 9 27rni Prove that if z and y are integers such that 1 En y then 6119 ein 21 Chapter 6 Linear Diophantine equations Given two integers a b a common divisor is an integer d such that dla and dlbi The greatest common divisor is exactly that the common divisor greater than or equal to all others it exists since the set of common divisors is nite We denote this by gcdabi Lemma 6 1 Euclid If a b aTe natuTzzl numbeTs then gcda b gcdb a mod 12 PToof Let T amod 12 Then the division algorithm gives a 412 T for some 4 It follows from exercise 2 of the chapter 4 that gcdbTlai Since gcdbTlb we can conclude that gcdbT S gcdabi On the other hand T a 7 41 implies that gcdablTi Therefore gcdab is a common divisor of b and T so gcda b S gcdb T 1 This lemma leads to a method for computing gcdsi For example gcd10040 gcd4020 gcd20 0 20 A Diophantine equation is an equation where the solutions are required to be integers or rationalsi The simplest examples are the linear ones given integers a b 5 nd all integers mn such that am In c If a solution exists then gcda 12 must divide c by exercise 2 of chapter 4 The converse is also true Theorem 62 Given integeTs a b c am bn c has a solution with m n E Z if and only gcda blc PToof Since m n imin is a solution of ian ibm c we may as well assume that a b 2 0 We now prove the theorem for natural numbers ab by induction on the minimum mina b If minab 0 then one of them say I 0 Since a gcdab divides c by assumption ca 0 gives a solution of mm In cl Now assume that am b n c has a solution whenever mina b lt minab and the other 22 conditions are ful lled Suppose I S a7 and let T rab amodb and q qab be given as in theorem 26 Then rm bn c has a solution since minr7 b r lt b mina7 b and gcdbr gcda7 b divides 0 Let m n and n m 7 qn 7 then am In an bm 7 977 bm rn c D Corollary 63 Given ab 6 Z there exists mn E Z such that am In gcdab The proof yields a method for nding a solution For simplicity assume that a 2 b 2 0 Then a solution to am In c is given by m s1abcn s2 a7 12 c where these functions are given recursively 7 ca if b0 81a b C 7 s2 b7 ra7 b7 0 otherwise b 0 if b0 32 a 7 C s10 ra7 b7 c 7 La7 bs2 b7 ra7 b7 0 otherwise This is easy to implement in Maple 51 abc gt if b0 then ca else 52biremabc fi 52 abc gt if b0 then 0 else slb iremabciquoabs2biremabc fi Lemma 64 pr is prime number then for any integers plab implies that pla 0r plb Proof Suppose that p does not divide a7 then we have to show that it divides b By assumption7 we can write ab up for some integer 0 Since p is prime7 and gcdpalp7 gcdp7 a is either 1 or p It must be 17 since gcd p would contradict the rst statement Therefore pm an l for some integers mn Multiply this by b to obtain pbm cn I So plb D Corollary 65 Suppose that plal an then plai for some i The proof of the corollary is left as an exercise We can now nish the proof of the fundamental theorem of arithmetic 23 Theorem 66 A natural number N 2 2 can be expressed as a product of primes in exactly one way What that means if N plpg l l ipn 1142 iqm where p1 S p2 S Hip and q1 S lan are primes then n m andpi qi Proof The existence part has already been done in corollary 43 We Will prove that given increasing nite sequences of primes such that pliupnqliuqm 61 then m n and pi qi by induction on the minimum We Will interpret the initial case 0 to mean that l is not a product of primes and this is clear Now suppose that 61 holds and that 0 lt n S mi Then p1 divides the right side therefore p1 divides some 4quot Since qi is prime p1 qil Similarly ql pj for some jl We can conclude that p1 41 since ql S qi and qi p1 S pj S 41 Canceling p1 from 61 leads to an equation p2 l l ipn qg l l l qmi By induction we are done 1 67 Exercises 1 Carry out the procedure explained after lemma 61 to calculate gcd882 756 Do this by hand 2 Prove that any common divisor of a and b divides gcda b and conversely that any divisor of the gcd is a common divisor 3 The least common multiple lcmab of two natural numbers ab is the smallest element of the set of numbers divisible by both a and bi Prove that lcmab W21 4 Given integers a I determine all integer solutions to am In 0 As suming the existence of one solution m0n0 to am bn 5 determine all the others 5 ln how many ways can you express 10 as a sum of dimes and quarters This is a linear diophantine equation With an obvious constraint 6 Find one solution for 120m lSln 1 either by hand or using Maplei 7i Prove corollary 65 24 Chapter 7 Subgroups of Abelian groups Let7s return to the subject of Abelian groups We introduce a way of producing new examples from old De nition 71 A subset B of an Abelian group A7 e is a subgroup 1 e E B 2 Bis closed under ab 6 B a b E B 5 B is closed under inversion ifa E B then the inverse a E B In fact7 you7ve something like this before in your linear algebra classes This is similar to the notion of subspace Lemma 72 A subgroup of an Abelian group is again an Abelian group Example 73 Z is a subgroup of Q and this is a subgroup of R and this is a subgroup C Example 74 The set of even numbers is a subgroup of Z More generally for any integer n the set of multiples of n denoted by nZ is a subgroup The veri cation is straight forward 0 n0 6 Z If a7 b are integers then na nb na b and ina n7a so nZ is closed under addition and inverses Example 75 an is a subgroup of Cquot In fact we checked all the conditions in the discussion following example 36 Let Z denote the Abelian group of integer vectors Z lmi E Z With addition given by m1mnm1Hm m1m1Hmnm 25 and identity 0 07 0 Example 76 Given integers ah an the set of solutions of the diophantine equation 72117 l alml anmn 0 is a subgroup of Z Example 77 Let Ae be an Abelian group Let a E A then the set of all powers a l n E Z is a subgroup called the subgroup generated by a The previous example nZ is just the subgroup on generated by n We can generalize this construction7 but rst we switch to additive notation7 since it makes it easier to see what s going on Lemma 78 Given a collection of elements a17a27ak of an Abelian group A7 0 the set S n1a1n2a2nkak l ni E Z is a subgroup called the subgroup generated by a17 a2 ak Proof 0 Oal Oak 6 5 Given two elements I y E 5 write them as zn1a1nkak and y m1a1mkak Then zy n1m1a1nhmkak E S and 717n1a177nkak65 Theorem 79 Any subgroup of Z is of the form nZ for some nZ Proof Let S E Z be a subgroup If S 0 then we can take n 0 So assume that 5 contains a nonzero element a We can assume that a gt 07 since otherwise we can replace it by 7a E 5 Therefore the set of strictly positive elements of S is nonempty Let n be the least such We will prove that any I E S is divisible by n If I is nonnegative7 then I qnr with 0 S r lt n But qn nn n E 5 Therefore r ziqn E S It follows that r 07 otherwise r would contradict the minimality of n So n divides I If I is negative7 then the previous argument shows that n divides 71 so it also divides z D 26 710 Exercises 1 Which of the following are subgroups of Z5 A 015 B 03 0 0 2 4 Write down all subgroups of Z4i Check that example 76 is a subgroup Let ab E Z be nonzero integers With gcdab ll Prove that the subgroup S am 1m 0 l mn E Z2 is generated by 127a With the following steps We know ax by 1 has a solution With Ly E Z Suppose that m n E S a Multiply am m 0 by z and after some algebra conclude that m 2721 for some integer 7215 b By a similar argument conlcude that n an for integer n i c Substitute these back into the preVious equationi Let ab E N prove that the subgroup S amlm l mn E Z generated by ab equals CZ Where c gcdabi 27 Chapter 8 Commutative Rings The set of integers Z has two interesting operations addition and multiplication which interact in a nice way De nition 81 A commutative ring consists of a set R with elements 01 6 R and binary operations and such that 1 R0 is an Abelian group 2 is commutative and associative with 1 as the identity I y y z zyzzyzzlz 5 distributes over z y 2 z y 12 Example 82 Z Q R and C with the usual operations are all commutative rings Example 83 Zn is in fact a commutative ring The addition has been dis cussed already The product is the modn product I 9 y my mod n Since the symbols EB and D are fairly cumbersome we will usually use or dinary notation with the understanding that we7re using modn rules For example we write 11 9 11 13 instead of 11 D 911 13 When doing calculations by hand the congruence symbol is very useful For example to see that 1191113211913 in Z15 we can write 1191113 1599143215982152 11 9 13 15 11 7 15 2 To evaluate this in Maple just type 11 96 9 11 13m0d15 To get a better feeling for this we can have Maple generate the addition and multiplication tables for Zn with the following code 28 tables 2 proc n posint local ABij A matrixn1n1 B matrixn1n1 for i from O to n1 do for j from O to n1 do Ai2j2 ij mod n Bi2j2 ij mod n od od A11 B11 for i from O to n1 do A1i2 i Ai21 i B1i2 i Bi21 i od printAB end To get the tables for Z3 type gt tables8 aamewmwo ammawmwoo ONGJWHgtCA3MHH HONGAWHgtLOMM mwoammaww wmwoammaa gtPWMHONOJU101 01HgtWMHONOJOJ mgtgtwmgtaow1w1 The output are matrices Which can With a little imagination be viewed as tables Looking at the second table we can see quite a few zeros Which donlt come from multiplication by 0 A nonzero element a such ab 0 With I f 0 is called a zero divisori The elements 2 4 6 are zero divisors Zero divisors exibit some strange properties for example 41 43 so one canlt cancel the 4 These elements have a more extreme property that they become 0 after multiplying them With themselves enough times OJWHgtCADIOHO 7 000000000 232220 29 0301RgtCA3MHOH OJgtgtMOOJgtgtMOM mm awmwow OHgtOHgtOgtgtOgtgt he wmwaammom MHgtOJOMHgtOJOOJ HMCADgtgtU1 NON The construction of C from R involves adjoining i xil7 and considering all possible expressions abi With a7 12 E R This construction can be generalized Example 84 Let R be a commutative Ting De ne abi l ab6 R with rules abz cdz ab cdz a bi c di ac 7 12d ad bci Lemma 85 is a commutative 7ing For exarnple7 C The other examples of interest to us is the ring of Gaussian integers Zi7 and the Gausian eld We look at some other cases of this in the exercises A polynomial is usually regarded as an expression of the form a0alzanzn Where ai are numbers of some sort We Will actually de ne a polynomial to equal the sequence of its coef cients a0a1 but we Will use the z to help us keep track of things Example 86 The set ofpolynomials z with complex coe cients becomes a commutative 7ing with o 0 denoting the polynomial001 01101m o a0alzb0blza0b0a1b1z 0 a0 alxb0blz a0b0a1b0 a0b1z Most standard identities from high school algebra can be carried out for commutative rings For example Lemma 87 Suppose that R is a commutative Ting Let 71 denote the inverse ofz in R0 Then a Oz0 b 71z7z Proof Therefore 0zz0zlzz0zlzl0z Adding 71 to both sides proves a For b7 it is enough7 by corollary 397 to check that z 71z 0 But 171z171z0z0 30 88 Exercises 1 Prove a 1y2 122zyyQi b1 y1y 12 i y2 hold in any commutative ring R where we de ne z and z 7 y z Check all the steps 21172zzz 2 Write out the addition and multiplication tables for Z2 07 17 i 1 Show that 1 i2 07 which means that it is nilpotent 3 Find all the zero divisors and nilpotent elements in Z121 If you need it7 here7s the multiplication table i 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 2 0 2 4 6 8 10 0 2 4 6 8 10 3 0 3 6 9 0 3 6 9 0 3 6 9 4 0 4 8 0 4 8 0 4 8 0 4 8 5 0 5 10 3 8 1 6 11 4 9 2 7 6 0 6 0 6 0 6 0 6 0 6 0 6 7 0 7 2 9 4 11 6 1 8 3 10 5 8 0 8 4 0 8 4 0 8 4 0 8 4 9 0 9 6 3 0 9 6 3 0 9 6 3 10 0 10 8 6 4 2 0 10 8 6 4 2 11 0 11 10 9 8 7 6 5 4 3 2 1 4 Suppose that gcdmn 1i Prove that m is zero divisor in Zni Sequences of random numbers are often generated on a computer by the following method Choose n7 a b7 10 and consider the sequence 1H1 azi 12 mod n This sequence will eventually repeat itself The period is the smallest k such that zik 11 for all 239 large enough Obviously7 short periods are less usefuli 5i Prove that the period is at most mi 6 Explain why picking a nilpotent in Zn would be a bad choice 31 Chapter 9 A little Boolean Algebra Z2 is the simplest ring there is and an interesting one at that We can View the elements as representing bits on a computer or truefalse in logic Let7s look at the tables 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 Taking 1 true and 0 false the tables imply that and are the exclusive or77 and and operators respectivelyi That is z y is true exactly when one or the other but not both variables are true while I y is true if and only if z and y are both true We introduce few more symbols inclusive or77 V and not de ned by IVyzyzy zz1 While were at it let s introduce the more traditional symbol for and z y z y We can now prove standard facts from logic by translating them into com mutative ring theoryi Note that Z2 has some special properties which makes the algebra quite simple namely 21 0 and 12 1 Lemma 91 De Morgan x V y x y This says for example that the negation of its a duck or it swims77 is it s not bird and it doesn7t swim77i 32 Proof Welll start at both ends an work toward a common value szzyzy1 I1y1 zyzy1 r A y 1 The following is the law of excluded middle and it is the basis of proof by contradiction Lemma 92 x VI 1 Proof zVz z1zzz1 211z2z 121 1 D For really complicated Boolean i e A V n expressions we can have Maple help us out in converting these to polynomialsi For example let7s convert both sides of the equation in lemma 9111 gt convertnot x or y mod2 1zyzy gt convertnot x and not y mod2 1zyzy 93 Exercises 1 Prove the remaining De Morgan law z y r V 2 Prove that V is associative 3 Prove the distributive law I y V 2 z y V I 4 Check that z V V I V 1 either by hand or using Maple 33 5 A commutative ring R is called Boolean if 12 1 holds for each I 6 Bi Prove that 21 0 in any Boolean ringi Hint evaluate I 1 Z2 is Boolean7 for other examples7 see below and the exercises of 24 All the results of this section extend to Boolean rings 6 Let P be the collection of subsets of a xed set Xi Let 0 denote the empty set and 1 Xi For AB E P de ne A B A B the interesection7 and A B to be the symmetric difference AB16Xl ifeitherzEAorzEB but not inboth Check that P7 017 is a Boolean ring 34 Chapter 10 Fields There are actually two Abelian groups associated to a commutative ring R The rst is of course the additive group R0 The second is De nition 101 A unit in R is an element r with a multiplicative inverse That is an element r E R such that rr l The set of units is denoted by Rquot Lemma 102 R l is an Abelian group As a consequence the inverse of r is unique if it exists it is denoted by r l De nition 103 A commutative ring R is a eld if R R 7 0 ie every nonzero element has an inverse Example 104 Q R and C are elds Z isn t We say that two integers a b are relatively prime if gcda b 1 Theorem 105 Z m 6 Zn l m and n are relatively prime Proof If gcdm n 1 then mm nn l or mm 7nn 1 for some integers by corollary 63 After replacing m n by m m nn 7 m for some suitable m we can assume that 0 S m S n Since have mm mod n 1 therefore mm l in Zn The converse follows by reversing these steps 1 Corollary 106 pr is a prime then Z1 is a eld The Euler function is de ned by It follows that p 7 l for p prime For small values of n then inverse of m in Zn can easily be determined by writing out the multiplication table In Maple the inverse can be computed as l m mod n De nition 107 A eld K has nite characteristic if nz 11 z n times is zero for all z E K The characteristic ofK is the smallest such n if it is has nite characteristic or else it is de ned to be 0 35 For example7 the characteristic of Q is zero7 and the characteristic of Z1 is p Lemma 108 A eld K does not have zero divisors That is my 0 implies z 0 or y 0 Let K be eld7 then we can form a ring as in chapter 7 This is a eld precisely When K does not already contain a square root of 71 Lemma 109 is a eld if and only if there is no element 1 E K with 12 71 Proof We prove one direction7 the other is left as an exercise Suppose that there is no element 1 E KWith 12 71 Let abi E be nonzero7 this means that a f 0 or I f 0 We claim that a2 122 f 07 so that it has an inverse in K Suppose that this is zero If a 0 then b2 0 implies b 0 by lemma 108 But this Will contradict the hypothesis Since a f 07 we get a2 7122 Which implies IIa2 71 and this contradicts the original supposition Therefore a2 122 f 0 as claimed It can be checked that the following formula gives the inverse a bi 1 a 7 bia2 b2 1 Example 1010 It follows that the Gaussian eld is a eld Example 1011 ZPM is a eld if and only isz Ep 71 has no integer solutions 1012 Exercises 1 Show that 17 71 i7 7i are the only units in 2 Find a formula for 45102 Where p is a prime Find a formula for 415pq Where p q are primes F90 Find a formula for 2 1 in Z1 Where p is an odd prime Prove it 5 Compute p 7 171 using Maple if necessary in Z1 for p 37 57 71113 Do you notice a pattern Prove it 6 Determine for Which p 2 37 57 7 117 ZPM is a eld 7 Complete the proof of lemma 108 8 Prove that characteristic of a eld is either 0 or a prime number 36 Chapter 11 Polynomials over a Field Let K be a eld We can de ne the commutative ring R of polynomials With coefficients in K as in chapter 7 Suppose f anz 7 Where an 0 and I is the highest power of z in Then n is called the degree of f7 degf7 and aux the leading term A polynomial of degree 0 called a constant polynomial Will be regarded as an element of K It turns out that R behaves much like Z In particular7 one has a version of the division algorithm Theorem 111 Let g 6 R with degg 0 Then theTe exists unique poly nomials q and T such that f 494M deg lt y PToof The proof is by induction on degf lf degf lt degg7 then take 4 0 and T Otherwise7 let a1 and bzm be leading coef cients of f and 9 Set ql ab 1zn m then f2 f 7 419 has degree less than degf Then by induction f2 429 T Therefore f 41 qgg T D Given an element 12 6 K7 E K is de ned by substituting b for z in the expression for We say I is a root of f if 0 Corollary 112 Ifb is a Toot of f then I 7 b divides f PToof Then f g I 7 b T Where T has degree 0 In other words T is an element of K Then T 0 1 Corollary 113 A nonzeTo polynomial of degTee n can have at most n distinct Toots Theorem 114 Lagrange Interpolation Given n 1 paiTs of elements ai bi E h with the ai distinct theTe is exactly one polynomial f 6 Hz of degTee n such that at bi 1727nl 37 Proof Let fj I 7 a1z 7aj11z 7aj11z 7an1 Then 1 ijfmrlfm will satisfy the above conditions exercise Suppose that g is another degree n polynomial satisfying gai 12 Then f 7 g is a degree n polynomial with n 1 zeros ai Therefore f 7 g 0 D With the division algorithm in hand much of the arithmetic of integers can be carried over to polynomials Given two polynomials f and y we say that f divides y if g fq A common divisor of f and y can be de ned as before A polynomial p is called a greatest common divisor or gcd if degp is maximal among all common divisors It s unique up two multiplication by a nonzero element of K To break that ambiguity we will take the gcd to be monic which means that leading coeff is one The analogue of corollary 63 holds Theorem 115 If is a greatest common divisor of fg E Kz then there exists polynomials f1gl E such that ffl 991 p The proof which is a modi cation of the previous one leads to an algorithm which can easily be implemented in Maple when K f1 fg gt if g0 then 1f else g1gremfgx ft g1 fg gt if g0 then 0 else f1g remfgxquofgxg1gremfgx ft ln calculus class one learns about partial fractions There is an implicit assumption that its possible Let7s prove this in special case Corollary 116 Let f g be nonconstant polyomials with 1 as a gcd Then there exists polynomials 104 and s with degp lt f and degg lt 9 such that 38 Proof We have ffl 991 1 Therefore 1 91 f9 f 9 Now apply the division to write 91 qlf r1 and f1 429 r2 and substitute above D The analogue of a prime number is an irreducible polynomial Given a polynomial f7 and a nonzero element a E K we can always factor f as a 1af We will call this a trivial factorization De nition 117 A polynomial f E is irreducible the only factorizations of it are the trivial ones The analogue of the fundamental theorem of arithmetic is the following Theorem 118 Any nonconstant polynomial f E can be factored into a product of irreducible polynomials Furthermore f p1pn ql qm are two such factorizations them n m and after renumbering there 4 s qi aipi where ai E K The concept of irreducibility and factorizations depends very much on the eld K For example 12 4 is irreducible as a polynomial over Q but not over or C The Maple procedures irreducf and fact0rf can be used to test irreducibility and do factorizations in You can also get it to factor in by typing fact0rf7 1 Similarly Irreducfm0dp and Fact0rfm0dp do this over Z141 One of the most important properties of the eld of complex numbers is the the fundamental theorem of algebra Theorem 119 Any nonconstant polynomial in CM has a root Corollary 1110 Any irreducible nonconstant polynomial over C is linear ie it has degree 1 Consequently any nonconstant polynomial can be factored into a product of linear polynomials Proof If f E z is a nonconstant linear polynomial then it has a root b Therefore f I 7 bg Since this must be a trivial factorization 9 must be a nonzero constant 1 1 11 1 Exercises 1 Check that the polynomial f given in the proof of theorem 114 actually works 2 Find polynomials fhgl E such that ffl 991 1 where f 13 7 2 and g 12 z 1 Use this to nd the partial fraction decomposition of 7 970 72x z1gt Over Q 39 Prove that I 1 is not irreducible over if n is oddi Using Maple factor 1 1 in and for n 2 4 6Hi16i Can you make a conjecture for When this is irreducible over Using Maple factor 1 1 over ZQM for various n Use this to nd irreducible polymomials of degree 2 3i i 10 Modify Euclids proof that there are in nitely many primes to prove that there are in nitely many irreducible polynomials over Z1 for any prime p Prove that any nonconstant irreducible polynomial f E Rz is either linear or quadratic a Recall that the conjugate of a complex number is abi a 7 bi Prove that z 7 c I 7 E 6 RM for any complex number or b Prove that for f 6 RM and c E C m In particular if c is a complex root of f then so is E c Let f E Rz be a nonconstant irreducible polynomial factor f over CM and then apply the previous results to prove that f is linear or quadratic 40 Chapter 12 Quotients of Abelian groups Let B be a subgroup of an Abelian group A Given a 6 A7 de ne the coset of a to be aBableB For example e 96 B B Example 121 Let A Z and B 2 Then a B 2 ifa is even and a B is the set of odd numbers if is odd We Write AB for the set of all cosets Although7 this may7 at rst glance7 seem like a bizarre thing to do7 it Will turn out to be a very reasonable con struction Lemma 122 If a1 6 B a2 6 B if and only ifal 6 a E B Proof Let al ea EB ThenforanybEBa1ba2a1agb Ea2B Which implies a1 96 B Q a 96 B Also a2 a l a1 a E B By an argument similar to the one above a 96 B Q a2 96 B Suppose a1 B a2 B then a1 awe a2b for some I E B Multiplying by a yields a1 96 a b 1 Fix n E N Let us denote the coset a nZ by 5 These are often called congruence classes Then Corollary 123 E E if and only if a En b This Will imply that ZnZ is the same as77 Zn This is left as an exercise This says that ZnZ Zn as sets What s missing is the addition rule We do this now Given two subsets XY of an Abelian group A7 e let XYzylz XyEY Lemma 124 a1 6 B 6 a2 6 B a1 6 a2 6 B 41 Proof a1 6 b1 6 a2 6 b2 a1 6 a2 6 b1 6 122 shows that al 6 B 6 a2 6 B Q a1 96 a2 96 B The reverse inclusion a1 96 a2 96 B Q a1 96 B 96 a2 96 B follows froma1a2ba1ea2b D Theorem 125 Let Let B be a subgroup of an Abelian group A7 e Then AB7 96 B is an Abelian group Proof This comes down to the following a1Ba2Ba1a2Ba2a2Ba2Ba2B a1Ba2Ba3Bla1Ba2a3Ba1a2a3B a1a2asBa1Ba2BlasB aBBaB aBaBaaBB D This implies that ZnZ is an Abelian group We will leave it as an exercise that ZnZ Zn as Abelian groups There is one more very natural example Example 126 The circle group is RZ The cosets are of the form I Z where 0 S I lt 1 We can think of taking the closed interval 01 and gluing the end points to get a circle The addition law can be described as follows add two numbers in the usual way and throw away the part to the left of the decimal point 127 Exercises 1 Let A Z5 and B 03 Check that B is a subgroup7 and write down all the cosets in AB7 and write down the addition table 2 Let us revert to using 69 for modular addition in Zn for this exericise Prove that 5 a 69 bin ZnZ 3 Let B be subgroup of an Abelian group A Prove that if two cosets a1B and agB have a nonempty intersection7 then they must coincide 42 Chapter 13 Orders of Abelian groups Given a set X7 recall that the number of elements of X which could be in nity will be denoted by When X is an Abelian group7 le is called its order Theorem 131 Lagrange Let A be on Abelz39oh group of m39te order Then for my subgroup B lAl lBHABl Proof Since A is nite7 there are only a nite number of cosets Let AB erB7 a1 B an B Every element a E A lies in one of these cosets7 namely aA Exercise 3 of the previous chapter shows that A e BUal B U an B is a partition Therefore by corollary 23 lAl le Blla1 Bl law 96 Bl The map from B A ai B given by z gt gt ai z is one to one and onto since it has an inverse given y gt gt aiy Therefore lai Bl lBl which implies that W ABHBL El Corollary 132 The order of my subgroup divides the order of A The order of an element a E A is the order of the subgroup generated by a Lemma 133 The order of n is the least n gt 0 such that a e Corollary 134 The order of a E A divides the order of A An Abelian group A is called cyclic if there is an element a E A called a generator such that every element of A is a power of A For example Zn is cyclic with 1 as it is generator Lemma 135 If lAl p is prime then it s cyclic In fact every element dz ereht from the identity is a generator Proof The order of a E A is either 1 or p If its 17 a e7 otherwise a is a generator D Coronary 136 alAl 1 43 Proof Write lAl mn where m is the order of a Then am Wm e 1 An important special case is the following Lemma 137 Fermat s little theorem If is prime and 0 lt a lt p then ap l 1 This leads to a simple test for compositness nonprimeness which we call the Fermat test to the base a Corollary 138 If ap l 1 mod p for some 0 lt a lt p then p is not prime It may seems strange that one even needs a test other than the obvious one of attempting to divide by successive integers The point is that for very large integers which arise in applications to cryptography7 the obvious test is so slow as to be useless A more practical method would be to might pick several bases at random If it passes each Fermat test7 then p is probably prime7 but if it fails once its de nitely composite Most primality tests used in practice7 including Maple s isp rime procedure use a more accurate variation of this idea Fermat had conjectured that integers of the form P 22 1 were always prime This was shown to be false by Euler7 when n 57 by explicitly factoring it Lets test the next one7 with n 67 using the above method In this case P 18446744073709551617 is big enough that Maple will be unable to compute aP l directly gt P 2 2 61 gt 2 P l Error integer too large in context However7 we only need aP l in the ring Zp and Maple can do this if we tell it to compute P0we7quota7 P 7 1 mod P Trying the Fermat test with base 2 is inconclusive7 but base 3 shows us that P isn7t prime gt Power2 Pl mod P Power3P1 mod P 1 8752249535465629170 139 Exercises 1 Calculate the orders of all elements of Z12 2 Show that Z is cyclic for p 357 711 3 Is Zg cyclic explain 4 Suppose that n passes the Fermat test to base 2 ie 2 1 E 1 mod Prove that n must be odd 44 5 Calculate all the integers between 3 and 25 Which pass the Fermat test to base 2 Are these all prime Use Maple 6 Suppose that a 6 Zn prove that aw En 1 if and only if a E Z 45 Chapter 14 Linear Algebra over Zp For each integer n7 let V Z be set of n tuple of elements of Z 07 17 i i p7 1 Of particular interest for applications7 is the case ofp 2 One might think of the elements of Z as representing strings of bits on a computer Z is an Abelian group With ahagpuanb17b27iubn a1b1uianbn as one might expect The order of this group is pni Let S E V be a subgroup By Lagrange7s theorem 5 must also be a power of pi We Will explain this in a different way by borrowing the notion of a basis from linear algebra Given N E Z1 de ne Na1a2iuan NahNagpuNan This is consistent With our earlier notation Na1a2iuan a17iiian a17iiianuia1iuan N times A collection of elements U1739UQ i i ivk E V is called linearly independent if the only solution to am agvg i Hakvk 07 ai E Z1 is a1a2uiak 0 Recall that U171 i i i Uk 6 S generates S if every element s E S can be Written as a sum s alvl agvg i Hakvk In this context the word spans is also used A collection of elements v1 v2 i i i Uk 6 S is called a basis if it is linearly independent and generates 5 Lemma 141 If U171 i Uk 6 S generate S then S S Equality holds and only this is a basis 46 Proof Let 111112 r ivk E S generate 5 De ne a function 5 Z 7gt S which assigns mm i iakvk E Z to the vector a1 iak E Z The function 5 is onto therefore 5 S lZ pki Suppose that v1 v2 ivk is a basis and suppose that Cal i ak Cal i i a n Then a1 7 a lv1 i i i an 7 a911 alvl i i akvk 7a1v1 i raj161116 0 By linear independence this is only possible if ai a This proves that c is a one to one correspondence in this case Therefore 5 pki Suppose that 5 pkw D An application of these ideas is in the construction of linear error correcting codesi Suppose a message which we think of as a string of bits is to be sent over a noisy mediumi The noise causes some of the bits to be ipped to incorrect values In order to detect those errors and possibly recover the orginal message we can encode the message so as to add redundent check bits The original message can be viewed as a vector in Z The encoded message is vector in a subspace S C Z3 and the function 5 constructed in the above proof can be used to encode the original message We de ne the distance du 1 between two vectors u v E Z to be the number of entries of u and 1 which differ If u is the original encoded message and v the recieved messages du v is the number of errors in transmission The further the distances between distinct code vectors the better our chances of detectingcorrecting errorsi There remains the problem of nding basesi Here we use the technique of Gauss Jordan eliminationi Given a set of vectors v1 a117a127ma1n v2 a217a227ma2n we arrange them in the rows of a matrix all a12 am an agg agn We then apply a sequence of the following operations called elementary row operations 0 Interchange rows 0 Multiply all elements of a row a by nonzero element of Zpi 0 Add a multiple of one row to another The goal is to get the matrix to reduced echelon form which means 47 o The leftmost nonzero entry of any row is 1 called a leading 1 o The leading 1 occurs to the right of any leading 1 above it o A row consisting of 07s occurs at the bottom of the matrix 0 All entries above a leading 1 are 0 it The standard results from linear algebra in our context tells us Theorem 142 Any matrix A over a eld can be taken to a reduced echelon matrix B by a nite sequence of elementary row operations The nonzero rows ofB forms a basis of the sybgroup generated by the nonzero rows of A Corollary 143 Any subgroup of Z has a basis Here s an example in Z7 2304R 115030w2i12w1150 451 451 061 6115 0 Row RowQ 1 0 5 016 016 In Maple this computation can done by gt matrix230 4511 2 3 0 4 5 1 gt Gaussjord o mod 7 1 0 5 0 1 6 144 Exercises 1 The weight of a vector 101 in v E Z is the distance dv0 Show that duv wu 7 v 2 Let S C Z be a subspace Prove that the minimum distance between distinct vectors of S is the minimum of weights of nonzero vectors 1 E S 3 Let S C ZS be the subspace generated by rows of 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 List all the elements of 5 Calculate the minimum distance between dis tinct vectors of S 48 4 Find a basis for the subgroup of Z generated by 172374 2730717 0010 and 3030 49 Chapter 15 Nonabelian groups Lets start With de nition De nition 151 A group consists of a set A with an associative operation 96 and an element e E A satisfying a 6 e e 6 a a7 and such that for every element a E A there exists an element a E A satisfying a 6 a a 6 a e A better title for this chapter would have been not necessarily Abelian groups7 since Abelian groups are in fact groups Lemma 152 An Abelian group is a group Proof The extra conditions e 96 a a 96 e and a 96 a a 96 a follow from the commutative law 1 Before giving more examples7 let s generalize some facts about Abelian groups Lemma 153 Ifabacthenbc Ifbaca thenbc Corollary 154 Given a there is a unique element a called the inverse such thataa aae We want give some examples of genuinely nonabelian groups The next example should already be familiar from linear algebra class Where F is usually taken to be R or maybe C We7ll say more about this example later on Example 155 The set oan n invertible also known as nonsingular matrices over a eld F forms a group denoted by GLnF and called the n X n general linear group The operation is matrix multiplication and the identity element is the identity matrix When n 1 this is just F which is Abelian However this group is not Abelian when n gt 1 50 We want to consider a more elementary example nexti Consider the equi lateral triangle 1 2 We want to consider various motions which takes the triangle to itself chang ing verticesi We can do nothing 1 We can rotate once counterclockwise Rz1gt 2 A 3 H11 We can rotate once clockwise R 1 A 3 A 2 H11 We can also ip it in various ways F1211gt272gt173 xed F1321gt373gt172 xed F2312gt373gt271 xed To multiply means to follow one motion by another For example doing two R rotations takes 1 to 2 and then to 3 etc So RRRR Lets do two flips7 F12 followed by F13 takes 1 A 2 A 27 2 H14 37 3 A 3 H1 so F 12F 13 R Doing this the other way gives F13F12 R Therefore this multiplication is not commutativei The following will be proved in the next section Lemma 156 IR 13 F127F137 F23 is a group with I as the identity It is called the triangle group 51 The full multiplication table can be worked out i l I F12 F13 F23 Ri R I I F12 F13 F23 Ri R F12 F12 I R R7 F13 F 23 F13 F13 R7 1 R F 23 F12 F 23 F 23 R R7 1 F12 F13 Ri Ri F23 F12 F13 R I R R F13 F23 F12 I Ri This is latin square chapter 3 but it isn7t symmetric because the commu tative law failsi Do all latin squares arise this way The answer is no For convenience let s represent a latin square by an n X n matrix M with entries I i i i n Lets say that there is a group G 9111 ign with g e such that M has entry ijth entry k if gi gj gki Since 91 e we would want the rst row and column to be I 2 i i i n Such a latin square is called normalizedi However this is still not enough since the associative law needs to hold I don7t know any way to visualize this Here s a Maple procedure for checking this assoc procnposint Mmatrix ijk associative associative true for i from 1 to 11 do for j from 1 to 11 do for k from 1 to 11 do if MiMjk ltgt MMij k then associative false printfquotg od g odg odg odnquotijkMiMjk printfquot gdgdgdgdnnquot ij kMMij k fi 0d 0d 0d if associative then printquotIt is associativequot fi end Typing assocn M either tells you if M is associative or else reports vio lations to the associative propertyi 157 Exercises II 1 Determine the inverse for every element of the triangle group 52 i Prove lemma 153 i Let G 7 e be a group Prove that the inverse of the product I 96 y y 95 z i i The commutator of z and y is the expression 1 96 y 96 z y i Prove that z 96 y y 96 I if and only if the commutator z 96 y 1 y e i Prove that the multiplication table for a group is always a latin square see the proof of lemma 310 for hints i Test to see if the normalized latin square corresponds to a group 3 U1gtJgtCADIOH 2 1 4 5 3 HgtHmo1 HMWWHgt wwwhum 53 Chapter 16 Groups of Permutations We can generalize the example of the triangle group A permutation of a nite set X is a one to one onto map f X A X Write SX for the set of such permutations We will be mainly interested in X 12 In this case we denote the set by Sn For examples of a permutation in 54 let f1 27 f0 37 f3 17 f4 4 9117921793 47 94 3 It may be helpful to visualize this 1 1 72H372gtl f 3319 334 4H4 4H3 Instead of standard functional notation it ll be more convenient to place func tions to the ght of the argument as in 1f2 Think of the way you would compute sinz on calculator you rst enter 1 and then press the sin key We get new permutations by composition in other words following one by another and by forming the inverse 2f 11 We can visualize this by splicing the pictures or reversing them 1 A 2 A l l A l f 7 2 A 3 A 4 7 2 A 4 9 3 A 1 A 2 3 A 2 4 A 4 A 3 4 A 3 CADIOH 1 ewwm tttt 4 De ne the identity function e by i e i for each i Lemma 161 Sn forms a group under composition with e as the identity The order e number of elements of this group is nl Proof Let fgh 6 Sn and 239 e nun Then if9hifohifyhif9hifgh The proves the associative law fgh fgh ifeifeif iefieif proves that fe ef Let f 1 denote the inverse function Then iff liff 1iie if lfif 1fiie implies that ff lf lf e The last statement is a standard counting argument Given a permutation f 6 Sn there are n choices for 1 f7 n 7 1 choices for 2 Leading to nn 711 choices for 1 Since the triangle group can be identi ed With 53 exercise7 this proves that it7s a group We get more examples of groups by generalizing the de nition from chapter 7 De nition 162 A subset H of a group G t e is a subgroup 1 e E B 2 B is closed under t 5 B is closed under inversion A subgroup of a group is also group Example 163 The symmetry group D4 of the square 55 is the subgroup of permutations of the vertices containg all rotations eg 1 A 2 A 3 A 4 A 1 and flips about the dotted lines e g the vertical flip is 1H2 2H1 3H44gt3 The notation we have been using for Writing down permutations is very cumbersome The most ef cient notation is cycle notation Which is based on the following Lemma 164 Let p 6 Sn then fori E 1 n the sequence ipiop must contain i The pattern i A i p A i p p A is called a cycle and it s donated by p Start With 1 Write down the cycle containing it Pick the next number say Is not in the previous cycle Write down the corresponding cycle Repeat until all numbers are accounted for In cycle notation p1lphhp although normally one omits cycles of length one In the previous examples f 123 y 12347 f9 243 It s possible to multiply permutations in Maple First you have to tell it to load the group theory package gt with group Permutations are entered in Maple s version of cycle notation gt f 123 g 12 34 f I 17 27 3ll 9 I 17 2L 37 4ll 56 gt mulperms f g 27 47 3ll The identity would be denoted by and the inverse is computed by the command invpe rmi 165 Exercises 1 Check that the triangle group coincides With 53 R 123 and F12 12 Check that F12RF12 R1 2 Write down all the elements of D4 Is this an Abelian group 3 Show by example7 that the product of two differents ips in D4 is a rota tion 4 Let c am i i i ak be a cycle of length k in SW Prove that ck e 57 Chapter 17 Symmetries of Platonic Solids There ve polyhedra with perfect symmetryi These are the Platonic solidsi The last book of Euclid is devoted to their study Perfect symmetry means that it is possible to rotate any vertex to any other vertex and any face to any other face Group theory enters at this point The symmetry group G of a polyhedron is the group of rotations which takes takes the polyhedron to itself We will view it as a subgroup of the permutation group of vertices which will be labelled l 2 31 1 11 We can partially capture the notion of perfect symmetry by the following De nition 171 A subgroup C Q Sn is called transitive iffor each pair ij E 1 1 Mn there exists f 6 G such that i f j Let us analyse the symmetry of the tetrahedron 4 1 2 which is the simplest Platonic solidi Let7s try and list the elements There is the identity 11 We have two rotations which turning the base and keeping 4 xed 123 132 There are six more rotations which keeps vertices l 2 and 3 xed 234 243 134 143 124 142 58 But this isn7t all Since T is a group we need to include products For example 1324 123 234 We can do these by hand but instead we get Maple 8 to produce all possible products of these elements actually it suf ces to use 123 234 gt P permgroup4 123 234 gt e1ementsP The output is H 17374ll7 1727 3H7 17 27 4H7 17 372ll7 174l7 273ll7 17 2 37 4H7 17 3L 27 4H7 27 37 4H7 17 47 2H7 17 47 3H7 27 47 3H Certainly P Q T We want to show these are same We need a method for computing the number of elements or order of T in advance First we make a de nitions De nition 172 Given subgroup C Q Sn andi E 1 n the stabilizer ofi isf Glifi The stablizer of 4 for T is the set 17 123 132 with 3 elements Theorem 173 Given a transitive subgroup C Q 57 let H be the stabilizer of some element i then lGl The proof will be postponed until chapter 19 As a corollary we get lTl 4 3 12 Next consider the cube 59 The symmetry group C is the group Which takes the cube to itself This can be Viewed as a subgroup of 53 We need to calculate the stabilizer of 1 Aside from the identity7 the only rotations Which keep 1 xed are those With the line joining 1 and 7 as its axis Thus the stabilizer consists of L 254 3687 245386 Therefore lCl 38 24 174 Exercises 1 Show that T is not Abeliani 2 Calculate the order of the symmetry group for the octrahedron 3 Calculate the order of the symmetry group for the dodecahedron 60 There are 20 vertices7 and 12 pentagonal faces 4 Let G C Sn be a subgroup Prove that the stablizer H of an element 239 is a subgroup of G 61 Chapter 18 Counting Problems involving Symmetry Group theory can be applied to counting problems inVloving symmetry Here are a few such problems Example 181 How many dice can be constructed by labeling the face of a cube by the numbers 1 69 Example 182 Suppose 3 identical decks of 52 cards are combined into a big deck How many 3 card hands can be delt out of the big deck Example 183 How many ways can a necklace be constructed with 2 black and 2 white beads To analyze the rst problem7 let s rst keep track of the order in which cards are dealt Let7s suppose that the kinds of cards are labeled by numbers 1 52 Since we have three decks we can be con dent about not running out of kinds Thus the set of ordered hands can be identi ed with Habc l abcl252 The cardinality of this set is 523 Of course7 we want to disregard order As rst guess7 we might think that we should diVide this by the number of ways of permuting the cards to get 5236 Unfortunately this is not an integer so it doesnlt make sense To explain the correct answer7 we will introduce some more group theory De nition 184 We say that a group Ge acts on a set X if there is an operation z X X G A X satisfying 1 zez 2 zghzgh 62 We7re are really de ning a right action here7 there is also a notion of left action7 but we won t need that De nition 185 Given a group G acting on a set X the orbit ofz E X is the set I G I g l g E G The set of orbits is denoted by XG De nition 186 An element 1 is called a xed point ofg is I g z Returning to example 182 5393 acts on H by moving the positions of the cards For example7 f CADIOH ttt Hoot then a17 a27 a3 f a27 a37 a1 We want to treat two hands as the same if you can permute one to get the other7 ie if they lie in the same orbit Therefore our problem is to count the set of orbits HSg If the rst two cards are repeated7 so a1 a2 then a17 a2a3 is a xed point for 12 Theorem 187 Burnside If G is a nite group acting on a nite set X then 1 XG7 ll 6 Z of xed points of g gEG This will be proved in the next chapter Corollary 188 Suppose that every element other than the identity has no xed points then lXGl Now7 we can solve the problems mentioned earlier For problem 1817 we rst choose an initial labelling7 or marking7 of our blank cube This allows us to talk about the rst face7 second face and so on Let X be the set of labellings of the faces of this marked cube There are 6 choices for the rst face7 5 for the second7 therefore there are 6 720 elements of X G C is the symmetry group for the cube which has order 24 G acts by rotating the cube Clearly there are no xed points for any rotation other than 1 Therefore the number of labellings for a blank cube is 720 7 7 30 24 lXGl Next consider problem 182 Let Hij be the set of ordered triples a17 a27 a3 with ai aj This is the set of x points of Since there only two free choices7 we have le39jl 522 Let H123 be the set of triples where all the cards are the same This is the set of xed points for 123 and 132 Clearly lnggl 52 63 Therefore HSs lHllH12llH13llH23llH123llH123ll HQlH a 23 3522 252 24804 Finally consider problem 1813 Let us rst arrange the beads in sequence There are 6 possibilities 009 000 00 000 000 00 and we let X be the set of these The group in this problem is the symmetry group of the square D4 C 54 which permutes the positions of the beads All of these are xed by the identity The rotations 1234 and 1432 have no xed points The element 12 34 has two xed points namely the leftmost sequences in the above diagrami The remaining 4 elements also have two xed points a piece exercise Therefore XD4 65lt2gt12 189 Exercises 1 Complete the analysis of problem 1813 2 How many necklaces can be constructed using 4 different colored beads 3 1n how many ways can the faces of a tetrahedron be labelled by the num bers 1 2 3 4 4 Suppose 2 identical decks of 52 cards are combined into a big decki How many 3 card hands can be delt out of the big deck 1n the above calculations certain numbers occured multiple times This can be explained with the help of the following de nition Two elements 9192 6 G are conjugate if 92 h 96 91 96 h for some h 6 G1 5 Prove that in 53 12 is conjugate to 13 and 23 and 123 is conjugate to 132 6 Suppose that a nite group G acts on a set Xi Prove that if 91 and 92 are conjugate then the number of xed points of 91 and 92 are the same 64 Chapter 19 Proofs of theorems about group actions We rst prove a strengthened version of theorem 173 Given a a group acting a set X the stabilizer of z is stabzgEGlzgz Theorem 191 Let G be a m39te group acting on a set X then lGl lstabzHzGl Proof For each y 6 1G let Ty9 GlIgy Choose go 6 Ty then the function g 96 go maps stabz A This is a one to one correspondence since it has an inverse f 1h h 96 9071 This implies that lstabzli If y f 2 then Ty and Tz must be disjoint otherwise y I g 2 for g E Ty Every 9 lies in some Ty namely Tz gi Therefore Ty is a partition of Cl By corollary 2 3 lGl 2 WW lIGllStabzl 11610 1 Given a subgroup H of a group G a right coset is a set of the form H g h g l h E H for g 6 Ci The set of cosets is denoted by GHi We can define a right action of G on GH by H9397H97 This is transitive action Which means that there is only one orbit and the stabilizer stabH H exercise Therefore we obtain an extension of 131 to nonabelian groups 65 Theorem 192 Lagrange Let G be a group of nite order Then for my subgroup H lGl We now prove Burnside s theoremi Proof Let CltzggteXxGzgg Consider the map p C A G given by pzg 9 Then an element of 1719 is exactly a fixed point ofgi Therefore corollary 24 applied to p yields lCl Z lp 1gl Z of fixed points of g 191 gEG gEG Next consider the map 4 C A X given by qzg 1 Then q 1z stabzi Therefore corollary 24 applied to 4 yields lCl ZlPAWM lemb1l 61 61 We group the the last sum into orbits C Z lstabzl Z lstabzl i H 16 1st orbit 16 2nd orbit For each orbit 10G has lGllstabzol elements by theorem 191 Furthermore7 for any I E 10G we have lstabzl lstabzoli Therefore lGl stabz stabz stabz G Ego l 1261 on mle on H Consequently lCl W Z 1 lGllXGl orbits Combining this With equation 19il yields lGllXGl Z of fixed points of g gEG Dividing by lGl yields the desired formulai D 193 Exercises 1 Fill in the details in the proof of Lagrange7s theorem a Prove that G acts transitively on GH b Prove that stabH Hi 2 Prove that if G is a group With lGl a prime7 then G is cyclic compare lemma 135 66 Chapter 20 Groups of 2 x 2 Matrices There is one very important example of a group7 that we havenlt talked much about yet This is the group of invertible square matrices over a commutative ring R To simplify things7 we will stick to the 2 X 2 case Given two 2 X 2 matrices b f a e He 93 h with entries ab h E R7 and another element r E R7 the products are 7 ra rb 7 aebg afbh TAiltrc rdgt7AB7ltcedg cfdh he 9 Lemma 201 If ABC are n X n matrices over a commutative ring R and r E R then 1 AI IA A 2 ABC ABC 5 rAB ArB rAB De nition 202 An 2 X 2 matrix A over a commutative ring R is called in vertible if there exists an n X n matrix B over R such that AB BA I The identity matrix Corollary 203 The set of2 X 2 invertible matrices forms a group GL2R The inverse of a matrix A is unique if it exists7 and is denoted by A l There is a criterion for invertibilty for real or complex matrices that one learns in a linear algebra class which works over any commutative ring det lt2 adi bc 67 Lemma 204 Given 2 X 2 matrices AB det AB det A det B Theorem 205 Let A Z b be matrix over a commutative ring R then d A is invertible and only detA E Rquot In this case A 1 detA 1ltd 1 7c a Proof Let A detA7 and let B ltfc Tab Then an easy calculation gives ABBAAI If A E Rquot then A lB Will give the inverse of A by the above equation Conversely suppose A 1 exists7 then apply lemma 204 to AA 1 I This yields detAdetA 1 1 Therefore detA E R B When K Z17 GL2 is nite group7 so it makes sense to talk about its order We can apply the techniques from the previous chapter to compute it Let V Z127 We let7 a b A a 4 act on Ly E V by multiplying A on the right I yA azcy bzdygt For our purposes7 ordered pairs are the same thing as 1 X 2 matrices Theorem 206 lGLg Zp p2 7 1p2 7 p Proof Let G GL2 Z17 and v 17 0 Then vA a b This vector can be anything but 0 Therefore the orbit vG consisists of V7 Consequently lle p2 7 1 The stablizer of v is the set of matrices 1 0 c d With nonzero determinant This means d f 0 There are p choices for c and p 7 1 choices for d Thus the order of the stabilizer is pp 7 1 p2 7 p The theorem now follows from theorem 191 1 68 207 Exercises 1 Using theorem 205 prove that GL2 Z2 consists of the following matrices LGgtvlt igtvltilgtvlt31gtvlt35gt 01 11 ZiSetR 1 1 andFlt0 1 and Check that it is not abeliani gt Verify that GL2Z2 1 R R2 F FR FRQ 3i Prove lemma 201i 4 Prove lemma 204 69 Chapter 21 Homomorphisms between groups When should two groups be considered the same An unenlightening answer is when they are the same A more useful answer is that they should be considered the same if we can set up a one to one correspondence between the elements which takes the multiplication table of one to the other Lets be a little more prec1se De nition 211 Suppose that G e and He are two groups A group isomorphism between G and H is a one to one correpsondence f G A H satisfying fg1 g2 fg1 fg2 and fe 6 It s useful to drop the requirements that f be one to one or onto We say that a function f G A H is a homomorphism fg1 92 91 f92 and 5 5 Welve had examples all along Example 212 Let G C H be a subgroup The map g is a homorphism Example 213 The map f Z A Zn which sends m to mmodn is a homo morphism Example 214 The map Zn A ZnZ given by m gt gt m nZ is an isomomor phism Example 215 The map f Zn A an given by ehimn is an isomor phism Example 216 Let Ae be an Abelian group and n E Z then nth power map p z A A A de ned by pa a is a group homomorphism Example 217 fB Q A is a subgroup of an Abelian group the map f z A A AB taking a gt gt a x B is a homomorphism by lemma 124 Example 218 The exponential map exp C A C where ezpz e2 is homomorphism from C0 to C 961 70 Example 219 Let R be the group of positive real numbers The exponential mop exp R A R is an isomorphism since it has an inverse given by log Example 2110 det GL2 R A Rquot is a homomorphism by lemma 204 Lemma 2111 If f G A H is a homomorphism then the fa fa where a is the inverse De nition 2112 If f G A H is a homomorphism the set herf g E G l e is called the kernel where e is the identity ofB The set l g E G is called the image Note that f gives an onto function from G A Which also denote by f Lemma 2113 Given a homomorphism f G A H herf is a subgroup of G and is a subgroup of H f is one to one and only if herf consists of the identity e C G Proof Certainly fe 6 implies that e E herf lf g1g2 E herf then f9192f91f9266e and M71 f91 6 Therefore herf is Closed under 96 and inverses The proof that is similar and is left for the exercises If f is one to one then herf f 1e can contain only one element and this would have to be e Conversely suppose herf e Then fg1 fg2 would imply that f91 9 f91 f92 5 Therefore g1 g e Which implies that g1 g2 1 Corollary 2114 A homomorphism f G A H is an isomorphism and only if herf e and H Corollary 2115 Let A be an Abelion group then a l a 1 and a l a E A are subgroups Proof These are the kernel and image of the homomorphism given in exam ple 216 1 Proposition 2116 fG is o nite group and f G A H is a homomorphism the 0 lkETUWmUN 71 Proof Let K herf By Lagrange7s theorem 1927 it is enough to set up a one to one correspondence between and GK Any element h E equals for some g E G The set f 1h T E 011 f9 TEGlfT9 rEG rxg hEK rEG rhgeKgKg is a coset Conversely7 any coset K 96 g arises this way as 1 Corollary 2117 A be a nite Abelian group then A Ha a em 1 a 6 AH for any positive integer n Corollary 2118 Let p be an odd prime then the half the elements of Z are squares Group actions can be reinterpreted using homomorphisms Lemma 2119 Given a group G with an action on a set X 11zn de ne the map l A ln by zifg zl g 1 Then is a permutation and this de nes a homomorphism f G A Sn Two groups G and H are isomorphic7 if there exists and isomomorphism f G A H The relation is symmetric and transitive by exercise 8 Theorem 2120 Cayley Any nite group Ge is isomorphic to a sub group of the permutation group Sn where n G Proof G acts on itself by the rule I g 1g Let G 91 692 gn then we get a homomorphism f G A Sn as above Let H Q Sn This is a subgroup of Sn and f G A H is onto Suppose that g E herf Then is the identity Therefore7 e 91 91fg 69 1 which implies that g e By lemma 21137 f G A H is one to one7 and therefore an isomorphism D 2121 Exercises 1 Check example 216 What if A was replaced by a nonabelian group 2 Suppose that A is a cyclic group of order n generated by a Consider the map f Zn A A de ned by am Check that this is an isomorphism Use this to justify examples 214 and 215 72 Prove lemma 2111 Prove that the image of homomorphism is a subgroupi Prove corollary 2118 Prove lemma 2119 Prove that if A is an Abelian group and f z A A G is an onto homomor phism then G is also Abeliani In particular a group is Abelian if it is isomorphic to one i Let f G A H be an isomorphism prove that f 1 H A G is also an isomorphismi Let h H A K be another isomorphismi Prove the composition hf G A K de ned by hfg hfg is an isomorphismi The 2 X 2 special linear group SL2R over a commutative ring R is the set of 2 X 2 matrices With determinat 1 Check that this is a group and calculate its order When K Zpi 73 Chapter 22 Groups of order 1 through 8 Now that we have decided that isomorphic groups should be considered the same it makes sense to ask how many groups are there of a given order say n Lets start with n ll Therels only one of course consisting of the identity and nothing else Next comes n 2 In fact we can deal n 2 3 5 7 at the same time There is only one apiecei The point is these are prime numbers We know from the exercises of chapters 19 and 21 that these groups are all cyclic and such groups are all isomorphic to Zni Let7s deal with n 4 next Theorem 221 There are only two groups of order 4 and they are both abelian Proof Suppose that G e a b c is the group in question with e the identity The possible orders for a 25 are 2 or 4 If one of these has order 4 then G is cyclic so it is isomorphic to Z4 Suppose the orders are all 2 This means a 96 a b 96 b c 96 c er Letls consider the possible values for a 96 12 If a 96 b e then multiplying by a on the left shows I a which is impossible If a 96 b a then multiplying by a on the left shows I e which is impossible If a 96 b b then multiplying by b on the right shows I e which is impossible Therefore a 96 b cl Continuing in this way exercise yields a complete multiplication table This example which is clearly abelian is called the Klein 4 group D The notion of a product of Abelian groups was introduced as in the exercises of chapter 3 The Klein 4 group can also be described as the product Z2 gtlt Z2 Z We won7t attempt to prove the remaining cases since we don7t really have 74 the tools But it is reassuring to know that we have seen many of these examples already Theorem 222 There are only two groups of order 6 Z5 and 55 Theorem 223 There are only 5 groups of order 8 Z3 Z3 Z2 gtlt Z4 D4 and one more The mystery group of order 8 Will be described later in chapter 28 224 Exercises 1 Finish all the details of the proof of theorem 221 2 Prove that the groups Z3 Z3 Z2 gtlt Z4 D4 are not isomorphic 3 In chapter 20 we saW that GL2 Z2 had 6 elements so it has to be iso morphic to Z5 or 53 Which one is it 4 In the preVious exercise construct an explicit isomorphism 75 Chapter 23 The Braid Group We want to switch gears and take a quick look at the mathematics of braidsi This subject is tied up with knot theory and topology Choose two sets of n points labelled 17 i in and connect them by n strings so that every point has exactly one string attached to it This is called a braid with n stringsi Depicted below are 2 braids with 3 strings I 2 T T 12 32 Notice we have taken care to indicate when a string crosses over another one The twist Tin1 is the braid where ith string crosses over the lst7 and THU means the ith string crosses under A braid gives rise to a permutation to see where each element goes7 follow the strings We can mulitply two braids by splicing them 1 2 3 T T 12 32 This is compatible with the rule for multiplying permutationsi lt shouldnlt be too hard to convince oneself that this is associative The identity is just 76 the unbraid 1 indicate below We need to add a rule that two braids are equivalent if you can move the strings without breaking them so to get from the rst picture to the second To put it another way7 a braid is equivalent to an unbraid if you can comb through it Thus two braids indicated below are equivalent 1 2 T T 12 21 This shows that T12 and T21 are inverses ln general7 we have Theorem 231 Artin The set of braids on n strings considered up to equivalence forms a group Bn The map f Bn A Sn which assigns a permuta tion to a braid is a homomorphism The rst nontrivial case is B2 Here we have a complete description Lemma 232 The map Z A B2 which sends n A T17 is an isomorphism of groups For n gt 27 En is more mysterious The key step in understanding it7 is to nd a system of generators Lets take a look at the permutation group rst Theorem 233 Any permutation in Sn is aproduct of the permutations l27 237 n7 17 This can be done in several ways 13gt lt12gtlt23gtlt12gt lt23gtlt12gtlt23gt These results extend to the braid group Theorem 234 Artin The twists Tin1 generate Bn In other words any braid in Bn is a product of a nite number of twists Tin1 and their inverses These satisfy the braid relations Tigti1TiLi2Tigti1 Ti1gti2TM1Ti1gti11 see gure below 77 TTT 122312 TTT 231223 235 Exercises 1 Prove that Bn is nonabelian When n gt 2 Hint use the map to Sn 2 Check theorem 2313 for 53 3 Decomp ose 1 into a product of twists 4 Prove that T12T233 equals 111211231112 78 Chapter 24 The Chinese remainder theorem De nition 241 A map of commutative rings f R A S is a ring homo morphism it s a group homomorphism from R 0 to S0 which also satis es l and fr1 7 2 fr1 fr2 A ring homomorphism is called an isomorphism it is one to one and onto Example 242 Let Z A Zn be given I gt gt z modn is a ring homorphism Example 243 Let K be a eld and a E K The map eva A K de ned by evafz fa is a ring homomorphism We can re ne this a bit Lemma 244 Suppose that nlm then Zm A Zn given by z gt gt zmodn is a ring homorphism De nition 245 Given two or more commutative rings R1 R2 their prod uct R1 gtlt R2 becomes a commutative ring with the operations rhrg7 r hr 7 r1 r 1r2 r2 01177127 TizT vm r1 r 1r2 an 0 07 0 1 11 A collection of integers n17 n2 is called relatively prime if gcdni7 nj l for all pairs i f j Lemma 246 Suppose that n1n2 are relatively prime If an integer z is divisible by all the ni then it is divible by their product nlng Proof 1 79 Theorem 247 Chinese remainder theorem Suppose that n 7Lan n is a product of a relatively prime sequence n1 linr of natural numbers then the map CZZnHan XZM gtlt HZnT given by cz 1 mod n1z mod n2 is an isomorphism of rings Proof it follows from lemma 244 that c is a ring homomorphism and hence a group homomorphisml Suppose that z E kerc Then I is divisible by all the ni and hence by n thanks to the above lemmal Since I 6 Zn it must be 0 Therefore c is one to one by lemma 2113 Since lan nlZn1 XZM gtlt mZml it follows that c must also be onto 1 Corollary 248 Given integers 11 17 there is an integer I such that z Em Ii Proof This follows from the fact that c is onto 1 There is something a little unsatisfying about this proof since it doesnlt tell us how to nd I We can give a more constructive argumentl Let N nllllni71ni1ulnr Then Ni will be a unit in Zn by theorem 105 Therefore there is an integer N which gives the multiplicative inverse to N in anl in other words NiNi En 1 Then setting I szNllNi gives an explicit solution This quite easy to implement in Maple here we take r 2 crt x1x2n1n2 gt x11n2 mod n1n2 x21n1 mod n2n1 Or better yet the following will produce smaller solutions crt x1x2n1n2 gt x11n2 mod n1n2 x21n1 mod n2n1 mod n1n2 Lemma 249 Let RR1R2 H be commutative rings such that there is an isomorphism szERlngxm then the restriction of f to R gives an isomorphism anpqxpgm 80 Corollary 2410 Suppose that n nlngulnr is a product of a relatively prime sequence then cIZquot s nHZmXZMXMZ m is an isomorphism In particular 4571 n1 n2 H 241 1 Exercises 1 Let n be an integer not divisible by 2 or 5 Prove that we can always nd a multiple of n such that the last two digits are 99 Do this explicitly for n 7 2 Suppose that gcdn1n2 17 does corollary 248 hold Either prove it7 or give an example to show that it fails 3 Recall that ring R is Boolean if 12 z for all z E Rl Prove that the ring of bit vectors R Z2 gtlt Z2 gtlt lHZQ n factors is Booleanl 4 Prove lemma 249 5 Suppose that R and S are commutative rings a Prove that the ring R X 5 must have a zero divisorl b Prove that f R A S is an isomorphism of commutative rings7 then R has a zero divisor if an only if S has a zero divisorl c Conclude that a eld cannot not be isomorphic to a product of two rings 81 Chapter 25 Quotients of polynomial rings We want to prove a Chinese remainder theorem for polynomials First we need analogue of Zn Let h be a eld and let 71 fznan1zn a0 be a polynomial We de ne 9 mod f to be the remainder ofg by For example gmod f g exactly degg lt n and 1 mod f 7an1z 1 7 alz 7 a0 De nition 251 is the set of polynomials of degree n 7 l with 0 l and as usual but with multiplication g D h gh mod f Lemma 252 is a commutative ring and the map Mr 7 given by g gt gt gmod f is a homomorphism As a rst example Example 253 7 a is just h and Hz 7 hz 7 a can be identiti ed with eva 243 In general the multiplication is rigged up so that 1 gets replaced by 7an1z 1 7 H 7 alz 7 a0 Example 254 hzz2l is just the set of linear polynomials abz with abz D cdz acadzbczbdz2m0dz2l ac 7 12d ad bcz Aside from a di erence in notation this is just introduced earlier In fact we now have a word for this and hII2 l are isomorphic rings 82 We now state a version of the Chinese remainder theorem Theorem 255 If f I 7 a1z 7 a2 I 7 an with ai distinct then the map 7gt kgtlt kgtlt times given by Cg ga1ga2 is an isomorphism of rings The proof of this similar to the proof of theorem 247 Notice that theorem implies the Lagrange interpolation theorem 114 Let us consider7 the opposite case where f is doesn7t factor In this case7 we have an analogue of corollary 106 Theorem 256 If f is an irreducible polynomial then is a eld Proof If g E is nonzero7 then gcdg 1 By theorem 1157 there exists a polynomials 91 f1 such that flf 919 1 Therefore glg mod f l The division algorithm implies that 91 fqr with deg r lt degf Therefore rg modf glg modf 1 So r is the inverse ofg in D For example7 12 7 2 is irreducible over Q so 7 2 is a eld 12 2 so we can identify 1 7 2 consists of expressions a b2 with a b E We can express the inverse in these terms by multiplying the numerator and denominator by a 7 b2 1 a7b2 a b 7 a2 7 2122 In the general the formula for the inverse is complicated The inverse of g in can be implemented in Maple by inv gf gt remg1fg f x where 91 is given after theorem 115 For example7 13 7 2 is irreducible over Q so 7 2 is a eld The inverse of a 121 512 can be calculated using Mapleas 7120a12b2210271baa272120 a376bca2b3453 257 Exercises 1 Calculate the inverse of 1 z in 7 5 2 Construct elds k Z2 with 4 and 8 elements Calculate the order of z in the multplicative group kl Hint Look at exercise 6 in chapter 11 3 Let k be a eld Given a E k such that 12 7a has no roots in h prove that this polynomial is irreducible The eld HzlIQ 7 a is usually denoted by HM Use this construction to prove the existence of a eld with p2 elements for any odd prime p 83 Chapter 26 The nite Fourier transform Consider the polynomial I 7 1 E We saw that this factors as Inil Ifl17w17w2u17wn71 Where w ehin Therefore the map f 71 A C y 917yw v we is an isomorphism of rings7 Where the right side is given the operations of 245 f is often called the nite or discrete Fourier transform In spite of the name7 these ideas go back to Gauss The product on the left is usually called the convolution In this case7 the inverse can be made explicit by the Fourier inver sion formula To simplify formulas7 we Will index vectors in C so that the rst component starts With a0 or be or Theorem 261 Fourier Inversion f 1a0 an71 bn71zn 1 bn721n 2 120 where 1 n71 V bm g E ajw mj j0 First we need a lemma Lemma 262 Let E be an integer 1 m7 n w0 0 iflnil m0 84 Proof If E 0 this is clear7 so we can assume that Z 17 i i n 7 1 Recall the formula for summing a geometric series 1TT2Hirnil We can apply it when 7 LUZ to get 4 27 mil m0 because w 1 D Proof of theorem Let fao i i bn71zn 1 i H be given by the formula above We have to show that f a0 a07 i i and ff9 y We will just prove the rst part7 the second is similar fquot a1 i i is a vector whose kth component is mewkm ZZajw mjwkm m m j Zajlt2wmwmgt j m ajwltkejgtm ak The last equality follows from lemma 262 D The nite Fourier transform has a number of important applications7 made practical by the fact there is a very fast method for computing it and its inverse see exercise 3 One application that we want to mention is the problem of multiplying two large polynomials f and 9 together The usual algorithm is not the most ef cient method If we view y as elements of 7 l for n gt degf degg7 then it s enough multiply them here because n is large7 the terms won7t wrap around The procedure then 1 Compute and fgi 2 Multiply these this is relatively quick 3 Compute the inverse transformi Similar techniques are available for multiplying large integers7 and these are much than usual method that one learns in school See 4 33 85 263 Exercises To better appreciate What the Fourier transform is let us think of f and f 1 as an operation from vectors b0nibn1 E C to vectors in Cni The kth component of 7020 121 i i is n71 116 E bjw j0 and the kth component of f 1a0 i is 1 mil 7 mj Z j0 1 Let n 2 work out explicit formulas for f and full If you remember your linear algebra it might be easier to Write the vectors in C as column vectors and represent 7 and f 1 by matricesi 2 Do the same for n 4i 3 Show that When n 2m is even 7020 i can be Written as mil V mil V 521 0126 w Z b2j1w2k j0 j0 Since 0J2 ehm this says in effect that 7020 121 i i i 12771 fbob27 11271172 4070117al 11277171 When n is a power of 2 this leads to a recursive procedure for computing 7 called the fast Fourier transformi 86 Chapter 27 Matrix Representations of Groups So far we7ve tried to understand groups by writing down multiplication tables using permutations and by giving generators There is one more important technique that we have been ignoring so far and that is representation of groups by matrices Given a group G a complex real rational n dimensional representation for it is an assigment of an n X n invertible matrix Rg to each g E G such that Rg1g2 is the same as Rg1Rg2i In other words R is a homorphism from G to GLAC If R is one to one then R is called faithful We won t develop the theory We will be content to just look at a few examples This will give us an opportunity to revisit some of the earlier materiali Example 271 Write w e27rin The map m gt gt of is a one dimensional representation of Zn 0 More generally we can consider m gt gt mm for each integer k These examples were operating behind the scenes in the last chapter Before going on we have to settle on some conventions We will identify vectors in C or R if you prefer with l X n matrices Given an n X n matrix A and a vector v E C we get a new vector vA E Cni From linear algebra class youlre probably used to working with column vectors and multiplying matrices on the left However since we have been applying permutations on the right it seems less confusing to do things this way Example 272 We rst encountered 53 as the symmetry group of an equilateral triangle This immediately leads to 2 dimensional real representation Choose equilateral triangle in R2 such as 87 with 101 170 p2 12732 p3 127 2l Salving MEG P27 ERG P1 and 1021393 P37 PSRO 02 22gtRlt23lt 2 Note by theorem 233 the values of R can all other permutations can be de termined from the above two Different choices of triangles will lead to different matrices and hence different representations But are they really so different At a fundamental level nor We can make this precise Two n dimensional rep resentations R and R of the same group G are isomorphic if there exists an invertible n X n matrix M such that R g MRgM 1l The representations for different triangles are isomorphic With a little work7 it can be seen that these are isomorphic to a much simpler representation of 53 leads to Example 273 R12 lt1 gtR23 j The next example7 involving the braid group chapter 237 de nitely does make the group more understandable 88 Example 274 Choose a nonzero complex number t the reduced Burau ma trices are T 7 it 0 T 7 1 it 12 7 71 1 7 23 7 0 it The map Tin1 A ful l de nes a two dimensional representation of B3 Notice when t 1 this reduces to the matrices in the previous example So in this case we get no more information than we could have by using the homomorphism B3 A 53 However for t f 1 this de nitely gives more exercise 3 It is easy to implement this in Maple burau proclis list local iB1 B2 1 B1 matrixt 0 1 11 B2 matrix1 t o t p diag11 for i in lis do if i2 ltgt 0 then if i1 12 then 1 evalmp amp B1 i2 else 1 evalmp amp B2 i2 fi fi od mapsimplify 13 end Given a nite product such as 1122112311in in B3 buraul 2 2 2 3 l 1 2 71 will evaluate its image under the Burau representation Example 275 Let e1 100 0 e2 010 0 be the standard basis vectors in C Given p 6 Sn let Rp be the n X n matrix satisfying eiRp elap This de nes an n dimensional representation of S7 The matrices Rp are called permutation matrices 276 Exercises 1 Since example is a representation and 123 12 23 we should have P1R12R23 P27 P2R12R23 P37 and P3R12R23 01 CheCk this 2 Check the braid relation 712723712 723712723 holds for any t f 0 3 Prove that the element T12T223T12 6 B3 is not 1 Note that the image of this element in S3 is trivial 4 Work out the permutation matrices for S3 and verify that it is a repre sentation 89 Recall the trace of an n X n matrix is the sum of its diagonal entriesi For nite groups7 the following gives a simple test for isomorphism Theorem 27 7 Two representations R and R of a nite group are isomorphic if and only traceRg traceRg for all g E G 5 Apply this to Check that examples 272 and 273 are isomorphic 90 Chapter 28 The ring of Quaternions Quaternions were introduced by Hamilton in an attempt to extend complex numbers Quaterninions can be added and multiplied7 and these operations make it a noncommutative ring De nition 281 A 7ing consists of a set R with elements 01 E R and binary operations and such that R7 0 is an Abelian group is associative with l as the identity and distiibutes over on the left and right zyzzyzz yzyzzz Rings are to commutative rings What nonabelian groups are to Abelian groups There is one very basic example Example 282 The set ofn X n matiices over a eld K forms a ring MnnK7 0I It is not commutative when n gt 1 The next example is the one of interest to us right now Example 283 The 7ing of quaternions is given by H abicjdk l abcdER 00Oi0j0k 11Oi0j0k abicj dk a b ic j d k aa bb i cc j dd k Multiplication is determined by the rules 1 is the identity 12 j2 k2 71 ij7jik jk7kji ki7ikji 91 Many of the constructions from complex arithmetic carry over to H We de ne the conjugate norm and real and imaginary parts of a quaternion by Waibiicjidk labicjdkl W Reabicjdk a Imabicjdk bicjdk Theorem 284 Let L E H then a 34 17 WEE a mm d 45 W e lqlq2ll41llq2l The rst two statements are easy For the last two are left as exercises These are easy to check on a computer once we implement the basic operations in Maple We encode the quaternion a bi cj dk as a list a b c conj q gt q1 q2 q3 q4 qadd procq11ist q21ist q11q21 q12q22 q13q23 q14q24 end In the next procedure we exploit the relationship between quaterionic mul tiplication and the vector cross product to get a short cut See the exercises qmult procq1 1ist q2 1ist local vect vect crossprodq1 2 4 lt12 2 4 vect eva1mvect q11 q22 4 q21 q12 4 q11q21 q12q22 q13q23 ql 4q2 4 vect1 vect 2 vect 3 end In order to use these we need to load the linear algebra package before hand by typing withlinalg Then typing for example qp39rodqp will calculate the product Let H H 7 It is easy to see that q E Hquot if and only if lql 0 As a corollary we get Corollary 285 H forms a group The inverse 71 5 q 7 VIP 92 286 Exercises H i Let L 1 2i Sji Calculate q 5 4 2 and verify that 44 1i 2 Prove part c of 284 using Maple Prove part F90 Prove part e 5 Check that the set 17 71 i7 7i7j ij k7 7k is a subgroup of H and Write down the multiplication table for it This is the missing group in theo rem 223 You have probably encountered the dot product 0 and vector cross product X on R3 before The dot product is an Rvalued operation given by bicjdko ziyjzk bzcydz The cross product is an Rgvalued distributive operation satisfying V X W 7W X v igtltjkjgtltkikgtltiji 6 Show that if V abc and W I y 2 are identi ed With the quater nions bi cj dk and xi yj 2k7 their quaternionic product vwvowvgtltw 7 Is gtlt associative 93 Chapter 29 Quaternions and the Rotation Group In this nal chapter we want to turn our attention to the set of all rotations in 3 dimensions This is certainly important both mathematically and in terms of the physical applications Let r zyz be a nonzero vector in R3 which we may as well take to be a unit vector which means z2y222 1 Let R0tt9 r denote the transformation R3 A R3 which represents a rotation of angle 9 with axis along 7 using the right hand rule R0tt9r is a linear transformation Hence we know by linear algebra that it can be represented by a 3 X 3 matrix However this description can be a bit cumbersomei After all we started with 4 parameters 9 z y z and now we have 9 We will give an alternative based on the ring of quaternionsi As a rst step identify 1 y 2 E R3 with the quaternion xi yj 2k De ne the spin group Spinq Hl l4l1 The rst part of the name comes from physics as in electron spin the last part is justi ed by 94 Lemma 291 Spin 239s subgroup of Hquot Proof This follows from theorem 284 D Lemma 292 If 4 6 Spin and v E H satis es Rev 0 then Re vq 0 Proof Rev 0 implies that 5 71 Therefore v4 q q qu see exercise 1 This implies Re vq 0 1 Since we are identifying R3 with the quaternions q satisfying Req 07 we can de ne a transformation of Rotq R3 A R3 by v Rotq Em for q 6 Spin This is a linear transformation7 therefore it can be represented by a 3 X 3 matrix In fact7 this matrix is invertible Theorem 293 Rotq is a rotation Rotqlqg Rotq1Rotqg For my unit vector r abc ai bj ck Rotcost92 7 sint92r corresponds to Rott97 r Corollary 294 R de nes a homomorphism from Spin A GL3R The image of Rot is called the rotation group Usually this denoted by 503 The 3 refers to 3 X 3 and O to orthogonal The rotation group is not isomorphic to the spin group since the kernel of Rot consists of 17 71 Let7s put this stuff to work in an example Suppose we rotate R3 counter clockwise once around the 2 axis by 90 7 and then around the z axis by 90 This can expressed as a single rotation7 letls determine it The rst and second rotations given by Rotql and Rotqg where ql cos7r4 sin7r4k qg cos7r4 sin7r4i Then with the help of the double angle formulas for sin and cos7 we get 1 44142 11Jkl The theorem implies that 17714 iii l1mql E 14 is the axis of Rotq7 and the angle of rotation is cos 1l2 which is 60 95 295 Exercises 1 Prove that alag i i i an El i i agali 2 Repeat the above example in reverse order 4241 3 Prove directly that lvRql This says that Rq is orthogonali This is the rst step in the proof of theorem 293i 4 Prove directly that if r ai bj ck is a unit vector and 15 satisfy a2 B2 17 then r Ra r r This is the second step in the proof of the theoremi 96 Appendix A Sets and Functions A set is simply a collection of things called elements A set can consist of no elements in the case of the empty set 0 a nite number of elements or an in nite number elgl N A nite set can be speci ed by listing the elements in any order C Ted bluegTeen bluegTeen Ted Sometimes we do want to take order into account instead of a set we use an ordered pair triplew tuple With instead of Ted blue gTeen blue gTeen Ted It s often convenient to specify a set in terms of the properties that elements satisfyl For example C can be speci ed as the set of I such that is a primary color or C I l I is a primary color 6 is elementhood relation so for example Ted 6 Or A subset of C is a set Which contains some or all of the elements of Or The relation is denoted by 9 For example A Tedblue Q C Given sets X and Y we can construct several new sets the union XUY2l26Xor2 Y the intersection X Yzl2 Xand26Y the difference XiYzleXandz Y and the Cartesian product XXYzyleXandyEY 97 A subset R Q X X Y is called a relation between elements of X and Y Usually one writes zRy instead of zy E Rf The symbols g E Q are examples of relations A function also called a map mapping or transformation f z X A Y is often thought of some kind process or formula which yields a de nite outputs in Y for each input in Xi For our purposes we treat a function as the same as its graph which is a relation f E X X Y A relation f is a function if for each I E X there exists a unique y E Y such that zy E Usually write this as y although it will be convenient to use different notation when working with permutationsi A function of two variables is just a function from a Cartesian product f X1 gtlt X2 A Y For example addition amn m n is a function a z N X N A N Any expression can be rewritten in functional notation eigi m n r am an In particular there7s nothing special mathematically about operations they7re just functions written in an unusual way A function f z X A Y is called one to one or injective if and only if fzl implies that 11 12 f is called onto or surjective if for each y E Y there exists I E X such that y A function is a one to one correspondence or a bijection if it s both one to one and onto If f is a one to one correspondence then the relation f 1 y71 l 1706 f is a function f 1 Y A X called the inverse Conversely if f 1 is a function then f is a one to one correspondence Even if f is not a one to one correspon dence we can still de ne f 1y I 6 X l fr y 98 Appendix E Maple This appendix describes Maple V5 or higher I won t get into the details of how you start the program since that varies from machine to machine At a basic level Maple is just a fancy calculatori The nice thing is it does exact arithmetic over Z i H For example to simplify SW 7 g 7 3 3 you can type gt 47 3sqrt 2 quot3 47 3sqrt 2 quot3 4 4 3 3 3 3 gt simplify 7 5580 49 Note lines must end With or z to suppress output means previous expression 96 is the multiplication operator and A is the power operatorl You can use variables Use 2 to assign values gt y 4 2 y I 4 gt x 2 16x y 3 z 716z 43 gt expand 15 1214 3213 712812 7 7681 71024 gt factor z 7 4 z 4gt4 99 Since I has no value the answer will be a polynomial in If It s possible that at some previous stage I had been given a value Maple has command unassign7x7 to deal with this Maple has many data structures analogous to the structures of standard mathematics For example nite sets speci ed by a sequence enclosed in lists speci ed by a sequence enclosed in which are like ordered tuples and matrices speci ed for example as matrizalla12 a21a22 Maple has many built in functions such as exp Big to calculate e2m 37 type gt exp2PiI3 1 1 71 3 22 J You can also create your own functions For simple functions you can use the 7 gt notationi gt cube 2 x gt x 3 cube zgtz gt cube3 27 We will give a brief sample of some of the more advanced features For a detailed explanation you should get hold ofa manual or book eigi We will explain how to program the Fibonacci sequence in couple of ways using Maple V Maple 6 and higher uses a different syntax but it should be backwards compatible First we implement the obvious recursion lifnOornl fibn fibm 7 2 fibn 7 1 otherwise fib n gt if n lt 2 then 1 else fibn1 fibn2 fi Although this works it is extremely inef cienti In fact fib100 would take long time and might even cause Maple to crash The problem is that along the way it computes intermediate values such as fib50 many times over The simplest solution is to tell Maple to remember these values so as not to recompute them each time fib proc n integer option remember 100 if n lt 2 then 1 else fibn 1 fibn 2 fi end ltls even more ef cient to compute fib by iteration using a loop fib proc n integer local f f1 f2 i if n lt 2 then 1 else f1 f2 f for i from 2 to n do f 1 f2 f2 f1 f1 f od f fi end gt fib100 573147844013817084101 For your convenience many of the procedures in these notes are available on the web at In 12v 3939 39quot l nn lJxlll ll Iquot ltl39l 39h39l AlvaLI Illilhl39gt139l gt These can simply pasted into a maple session7 and then run 101 Bibliography 1 M Artin Algebra Prentice Hall 1991 2 T Brocker T tom Dieck Representations of compact Lie groups Springer Verlag 1985 3 A Heck Introduction to Maple SpringerVerlag 1993 4 K Hoffman R Kunze Linear Algebra Prentice Hall 1971 5 K lreland M Rosen A classical introduction to modern number theory SpringerVerlag 1990 6 N Jacobson Basic Algebra 1 W H Freeman and Company 1985 7 V Jones Subfactors and knots American Math Soc 1991 8 D Knuth The Art of Computer Programming 3rd ed AddisonWesely 1998 9 N Koblitz A course in number theory and cryptography SpringerVerlag 1987 10 J van Lint R Wilson A course in combinatorics Cambridge Univ Press 1992 11 H Weyl Symmetry Princeton Univ Press 1952 102

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.