PUMaC 2023 Power Round Solutions Frank Lu April 2023 1 Rings and Fields 1.1 Rings and Ideals Problem 1.1.1. Here are some more examples, and a non-example, of rings:

1. Show that 2 Z , the set of even integers, is not a ring. (Hint: which property does it fail? In general, for questions of this nature, it is helpful to go through the properties and figure out which ones are or are not satisfied).
2. Show that C [ x ] , the set of polynomials in one variable x with complex coefficients, is a ring (under the standard addition and multiplication operations of polynomials)
3. Show that the subset of polynomials in C [ x ] whose x coefficient is 0 forms a ring (with the same addition and multiplication as for C [ x ]). Solution. 1. We claim that the set of even integers does not have a multiplicative identity. Suppose for the sake of contradiction such an identity e existed. Then, we would require that 2 e = 2 . But then this requires that e = 1 , which is not an even integer. This yields the desired contradiction, and so 2 Z is not a ring under the typical addition and multiplication operations.
4. We show that the set of polynomials with complex coefficients form a ring, by checking each of n P i the conditions. For the first condition, for any polynomials f, g ∈ C [ x ] , we can write f ( x ) = f x i i =0 m P i and g ( x ) = g x , where f , g ∈ C . We may furthermore suppose that n = m, by adding more i i i i =0 n P i i terms of the form 0 x to these polynomials. Then, we observe that f ( x ) + g ( x ) = ( f + g ) x and i i i =0       n n n i 2 n n 2 n X X X X X X X X   i + j i i i       f ( x ) · g ( x ) = f g x = ( f g ) x + ( f g ) x = f g x i j j i − j j i − j j i − j   i =0 j =0 i =0 j =0 i = n +1 j = i − n i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n which are both polynomials with complex coefficients. We could have stopped at the expression n n P P i + j f g x , but it is useful to have the explicit formula for the coefficients written out. i j i =0 j =0 1

n n P P i i For associativity, suppose we are given three polynomials f ( x ) = f x , g ( x ) = g x , h ( x ) = i i i =0 i =0 n P i h x (again, by the above argument, we can suppose that the sums are over the same range by i i =0 i adding additional 0 x terms). Then, n n n X X X i i i ( f ( x ) + g ( x )) + h ( x ) = ( f + g ) x + h x = (( f + g ) + h ) x i i i i i i i =0 i =0 i =0 n n n X X X i i i = ( f + ( g + h )) x = f x + ( g + h ) x i i i i i i i =0 i =0 i =0 = f ( x ) + ( g ( x ) + h ( x )) . Similarly, we can check that     2 n n X X X     i i     ( f ( x ) · g ( x )) · h ( x ) = f g x · h x j i − j i     i =0 0 ≤ j ≤ n i =0 0 ≤ i − j ≤ n   3 n X X X   i   = ( f g ) h x k j − k i − j   i =0 0 ≤ j ≤ 2 n 0 ≤ k ≤ n 0 ≤ i − j ≤ n 0 ≤ j − k ≤ n   3 n X X X   i   = f g h x k j − k i − j   i =0 0 ≤ j ≤ 2 n 0 ≤ k ≤ n 0 ≤ i − j ≤ n 0 ≤ j − k ≤ n     3 n X X   i   = f g h x , k j − k i − j     i =0 0 ≤ k ≤ n 0 ≤ i − j ≤ n 0 ≤ j − k ≤ n the last equality coming from the fact that 0 ≤ k, j − k ≤ n implies that 0 ≤ j ≤ 2 n. But then we can rewrite this as     3 n 3 n X X X X X X     i i     f g h x = f ( g h ) x k j − k i − j k j − k i − j     i =0 0 ≤ k ≤ n 0 ≤ i − j ≤ n i =0 0 ≤ k ≤ n 0 ≤ i − j ≤ n 0 ≤ i − k ≤ 2 n 0 ≤ j − k ≤ n 0 ≤ i − k ≤ 2 n 0 ≤ j − k ≤ n   n 2 n X X X   i i   = f x · ( g h ) x = f ( x ) · ( g ( x ) · h ( x )) . i i − j j   i =0 i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n This gives us associativity. 2

Next, for commutativity, we can quickly check that, given any polynomials f, g, which we can write in the form above, that n n X X i i f ( x ) + g ( x ) = ( f + g ) x = ( g + f ) x = g ( x ) + f ( x ) i i i i i =0 i =0 and         2 n 2 n X X X X         i i         f ( x ) · g ( x ) = f g x = g f x = g ( x ) · f ( x ) , j i − j j i − j         i =0 0 ≤ j ≤ n i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n 0 ≤ i − j ≤ n where the second-to-last equality arises from replacing the index j with i − j. Using these formulas, we can check that the polynomial 0 is the additive identity, as n n n X X X i i i 0 + f x = (0 + f ) x = f x , i i i i =0 i =0 i =0     2 n P P     i and 1 is the multiplicative identity, as 1 · f ( x ) = a f x , where a is 1 for     j i − j j i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n n P i j = 0 and 0 otherwise. But then this is just f x . i i =0 n n P P i i For additive inverse, we note that given f ( x ) = f x , the polynomial ( − f ) x is the additive i i i =0 i =0 n P i inverse, as adding f ( x ) to this yields ( f − f ) x = 0 . Finally, for the distributive law, we note i i i =0 that     n 2 n X X X     i i     f ( x ) · ( g ( x ) + h ( x )) = f ( x ) · ( g + h ) x = f ( g + h ) x i i j i − j i − j     i =0 i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n         2 n 2 n X X X X         i i         = f g ) x + f h ) x j i − j j i − j         i =0 0 ≤ j ≤ n i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n 0 ≤ i − j ≤ n = f ( x ) · g ( x ) + f ( x ) · h ( x ) . Having verified all of the conditions for the set of polynomials with complex coefficients, we thus see that this forms a ring with the typical addition and multiplication operations. 3. We note that we have done a lot of the work already: we just need to check that conditions 1, 4, and 5 hold for this subring, since the associativity, commutativity, and distributivity come from the work we did in part 2. Furthermore, we can quickly check 4, since 0 , 1 both are polynomials with x coefficient 0 . 3

n n P P i i For 5, the additive inverse of a polynomial f x is ( − f ) x . But the former lies in the set i i i =0 i =0 of polynomials whose x coefficient is 0 if and only if f = 0 , which holds if and only if − f = 0 . i i Thus, any polynomial f in our set has its additive inverse in the set. We thus just need to check that condition 1 is satisfied. n n P P i i Notice that given polynomials f x and g x in our set, we have f = g = 0 , and their i i 1 1 i =0 i =0 sum equals n X i ( f + g ) x , i i i =0 where the coefficient at i = 1 is f + g = 0 + 0 = 0 , so this lies in the set of polynomials with 1 1   2 n P P   i x coefficient 0 . Similarly, their product is f g x , and the coefficient at i = 1 is   j i − j i =0 0 ≤ j ≤ n 0 ≤ i − j ≤ n f g + f g = 0 + 0 = 0 , so this set is also closed under multiplication. 0 1 1 0 We have therefore shown that the set of polynomials whose x coefficient is 0 forms a ring, which is what we wanted to show. Problem 1.1.2. ( points) Let Z /n Z be the set of remainders of integers upon division by n, where addition and multiplication are defined modulo n. For instance, when n = 6 , we have that 4+5 = 3 , and 4 · 5 = 2 . Prove that this is a ring. Solution. We check through the properties of a ring. For property 1, we note that we can add and multiply remainders to get another remainder, by the definition of these operations. Prop- erties 2 and 3 follow from the associativity and commutativity of addition in Z . For instance, for associativity, ( r + r ) + r is equal to ( r + r ) + r (mod n ) , which is equal to r + ( r + r ) 1 2 3 1 2 3 1 2 3 (mod n ) . Property 4 follows by using 0 and 1 for the additive and multiplicative identities, respectively. Indeed, adding a multiple of n to an integer does not change its remainder upon divison by n, and given an integer m with remainder r (so m = qn + r for some integer q ), if x is remainder 1 , so ′ ′ ′ ′ ′ x = q n + 1 for some integer q , thhen mx = ( qn + r )( q n + 1) = r + n ( rq + q + qq n ) , which has remainder r. Property 5 follows by considering n − r for each remainder r (unless r = 0 , where we can take 0), since n − r + r is 0 modulo n. Finally, property 6 follows from the distributivity law on Z , similarly to properties 2 and 3. Indeed, given remainders r , r , r , we have r ( r + r ) ≡ r r + r r (mod n ) . Therefore, it follows 1 2 3 1 2 3 1 2 1 3 that Z /nZ is a ring, with addition and multiplication defined modulo n. Problem 1.1.3. Given a ring R, show that there exists an element x ∈ R such that for all r ∈ R, r + xr = 0 . What element is this? Solution. We claim that this element x is the additive inverse of the additive identity 1 ∈ R. Such an element exists by condition 5 in the definition of a ring. By conditions 4 and 6, we thus have that for all r ∈ R, r + xr = 1 · r + x · r = (1 + x ) · r = 0 · r. But by the above proposition, 0 · r = 0 , which is what we wanted to show. Problem 1.1.4. ( points) Show that the set of odd integers, as a subset of Z , is not an ideal. 4

Solution. We notice that the set of odd integers is not closed under addition, since 1 + 1 = 2 , with 1 odd, but 2 is even (so not odd). Hence, the set of odd integers is not an ideal. Problem 1.1.5. Determine, with proof, all the prime ideals of C [ x ] . You may use, without proof, the Fundamental Theorem of Algebra (namely, that polynomials in C [ x ] can be written as a product of linear factors, and this product is unique up to the order of the linear factors). Solution. We claim that the set of prime ideals in C [ x ] is precisely the set of ideals of the form ⟨ x − a ⟩ , where a ∈ C , and the set { 0 } , with { 0 } the only nonmaximal prime ideal. First, we show that these are all prime. To show that { 0 } is prime, we observe that if f, g are nonzero polynomials, this means that their leading coefficient are both nonzero, so the leading coefficient of f g is the leading coefficient of f times that of g, which is nonzero (and therefore f g ̸ = 0). In other words, if f g = 0 , then one of f, g is zero. Now, we show that ⟨ x − a ⟩ are prime, ideals. Suppose that f g lies in ⟨ x − a ⟩ . Then, we note that the polynomial f g evaluates to 0 at x = a. In other words, f ( a ) g ( a ) = 0 , meaning that one of f ( a ) , g ( a ) is zero. But that, in turn, implies that one of f, g lies in ⟨ x − a ⟩ , which is what we wantedot show. We show that all prime ideals must take one of the above forms. Suppose that I is a prime ideal that contains at least one nonzero polynomial f. By the fundamental theorem of algebra, we may write f ( x ) = ( x − a )( x − a ) · · · ( x − a ) , where n is the degree of f and the a lie in C . However, 1 2 n i by the definition of prime, one of the x − a lies in the ideal I. But then ⟨ x − a ⟩ ⊂ I, since by i i definition of an ideal, x − a ∈ I implies o ( x )( x − a ) ∈ I for all p ( x ) ∈ C [ x ] . However, if I is not i i equal to ⟨ x − a ⟩ , then there is some polynomial g ∈ I where g ( a ) ̸ = 0 . In particular, as g ( x ) − g ( a ) i i i lies in ⟨ x − a ⟩ , it follows that g ( a ) lies in I, or that 1 ∈ I. However, this means that I = C [ x ] , i i which is a contradiction. Therefore, I = ⟨ x − a ⟩ , which is what we wanted to show. i Problem 1.1.6. For each of the functions below, state whether they are injective, surjective, both, or neither.

1. The function f ( x ) = | x | from the set of negative real numbers to the set of positive real numbers. x
2. The function f ( x ) = e from R to R .
3. The function f ( x ) = sin x from [0 , 2 π ] to [ − 1 , 1] . Solution. 1. The function f ( x ) = | x | is both injective and surjective. For any positive real number r, | − r | = r, and − r < 0 is negative. Furthermore, if | x | = | y | , then x = ± y. But x, y must be negative, so x = y. x
4. This is injective, but not surjective. Note that e > 0 for all real x ; in particular, this means x x y that e = − 1 has no solution, so this is not a surjective function. For injectivity: e = e implies that, taking the natural logarithm, x = y. − 1
5. This is surjective, but not injective. For surjectivity, note that for all y ∈ [ − 1 , 1] , sin sin ( y ) = y. For where it fails injectivity, note that sin 0 = sin π = 0 . 1.2 A Family of Rings √ Problem 1.2.1. Show that the set of real numbers a + b 2 , where a, b ∈ Q , forms a field, under √ the normal rules of addition and multiplication in R . This set is sometimes notated as Q ( 2) . 5

Solution. We first verify that this is a ring, and then show that every nonzero element has a multiplicative inverse. As this is a subset of R , conditions 2, 3, and 6 are given to us automatically. √ Condition 4 follows since the identities 0 and 1 lie in Q , and thus Q ( 2) . Condition 5 follows from √ √ √ the fact that, for all a + b 2 ∈ Q ( 2) , ( − a ) + ( − b ) 2 is the additive inverse, and this also lies in √ Q ( 2) . √ √ ′ ′ ′ ′ To show that this is closed: for all elements a + b 2 and a + b 2 , where a, a , b, b ∈ Q , we have √ √ √ √ √ √ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ a + b 2 + a + b 2 = ( a + a ) + ( b + b ) 2 , and ( a + b 2)( a + b 2) = ( aa + 2 bb ) + ( a b + ab ) 2 , √ ′ ′ ′ ′ ′ ′ both of which lie in Q ( 2) as aa + 2 bb , a b + ab , a + a , b + b all are rational numbers (as the rationals are closed under addition and multiplication). √ √ a b 2 Finally, say a + b 2 ̸ = 0 is a nonzero element. Then, notice that − is a multiplicative 2 2 2 2 a − 2 b a − 2 b √ √ √ 2 2 ( a − b 2)( a + b 2) a − 2 b 2 2 inverse if a − 2 b ̸ = 0 , as multiplying this with a + b 2 yields = = 1 . Notice 2 2 2 2 a − 2 b a − 2 b √ a 2 2 2 2 finally that a − 2 b = 0 implies that a = 2 b , so either b = 0 (and so a = 0), or is 2 , which we b √ √ 2 2 know is not possible. Thus, all nonzero elements in Q ( 2) , a + b 2 , are so a − 2 b ̸ = 0 , and thus have multiplicative inverses. √ Therefore, it follows that Q ( 2) is a field, as desired. Problem 1.2.2. Show that a ring R is a field if and only if it has exactly two ideals. Which two ideals are these? Solution. Suppose that R is a field. Suppose that I is an ideal of R. Then, either I = { 0 } , which is − 1 an ideal, or I contains a nonzero element f. However, as the multiplicative inverse of f, f , exists, − 1 we have that for all r ∈ R that rf f = r ∈ I, or that I = R. Thus, R has two ideals. Now, suppose that R has two ideals. Then, in particular as { 0 } and R are both ideals (and they are distinct since R contains a nonzero element), it follows these are all of the ideals. But then for all nonzero f, we have that ⟨ f ⟩ = R. In particular, 1 ∈ ⟨ f ⟩ , so there exists an r ∈ R so rf = 1 , or that r is a multiplicative inverse of f. Therefore, R is a field, which is what we wanted to show. Problem 1.2.3. Show that Z is a PID. To do this, given any ideal I of Z , consider the smallest positive element in I, say i. Show that every element in the ideal has to be divisible by i. Solution. We show that Z is a PID. Let I be an ideal of Z . First, if I = { 0 } , then I is generated by the element 0 . Otherwise, there exists a nonzero element i ∈ I ; either i > 0 , so there is some positive element in I, or i < 0 . But if i < 0 , then ( − 1) · i > 0 , and ( − 1) · i = − i ∈ I. Now, let r be the smallest positive element in I. We show that ∀ d ∈ I, d is divisible by r. This will then show that I = ⟨ r ⟩ . Suppose for the sake of contradiction that an element d ∈ I exists such that d is not divisible ′ ′ by r. Dividing d by r, we can then use the division algorithm to get d = qr + r , where 0 < r < r ′ ( r > 0 by the fact that d is not divisible by r ). However, d, r ∈ I, so ( − q ) · r and thus d − qr both ′ ′ lie in I. But then r = d − qr ∈ I, and 0 < r < r, contradicting the fact that r is the smallest positive element in I. Thus, all the elements in I are divisible by r, and thus I is generated by r, meaning that Z is a PID, as desired. Problem 1.2.4. Show that for any integral domain R, every prime element is irreducible. Solution. Suppose that p is a prime element. Suppose that p = ab, where a, b are elements. Then, ⟨ p ⟩ is a prime ideal, meaning that, as ab ∈ ⟨ p ⟩ , we have that either a or b lies in this ideal; without loss of generality, say this is a. Then, a = pr for some r ∈ R, meaning that brp = p, or that 6

( br − 1) p = 0 . As R is an integral domain and p ̸ = 0 , we thus have that br = 1; in other words, b has multiplicative inverse r, so b is a unit. We also note that p is not a unit, as otherwise ⟨ p ⟩ = R, which is not prime. Therefore, p must be irreducible (it cannot be written as a product of two nonunit elements). √ √ Problem 1.2.5. Show that the set of elements Z [ − 13] , of the form a + b − 13 , for a, b ∈ Z , while an integral domain, is not a UFD, and therefore not a PID. Solution. We first verify that this is a ring; with the operations inherited from C , we just need to show that it contains the multiplicative and additive identities (which is clear, as 0 , 1 ∈ Z ⊂ √ Z [ − 13]), and is closed under addition, multiplication, and additive inverse. √ √ √ √ But given a + b − 13 , c + d − 5 ∈ Z [ − 13] their sum is ( a + c ) + ( b + d ) − 13 , their product √ √ √ is ( ab − 13 bd ) + ( ad + bc ) − 13 , and the additive inverse of a + b − 5 is ( − a ) + ( − b ) − 13 , which √ √ for a, b, c, d ∈ Z lie in Z [ − 13] since Z is a ring. Hence, Z [ − 13] is a ring. √ √ Furthermore, it is an integral domain. Indeed, if ( a + b − 13)( c + d − 13) = 0 , then we have √ √ that ( ac − 13 bd ) + ( ad + bc ) − 13 = 0 , or that 13 bd − ac = ( ad + bc ) − 13 . But the right-hand side √ is not an integer unless ad + bc = 0 , and so ac − 13 bd = 0 too. Now, suppose that a + b − 13 ̸ = 0 , − bc so we have one of a, b is nonzero. If it is a, then notice that ad + bc = 0 implies that d = , and a 2 13 b c 2 2 2 2 2 2 so ac − 13 bd = ac + = 0 , or that a c + 13 b c = 0 , or ( a + 13 b ) c = 0 . If a + 5 b = 0 , then as a squares of integers are positive, we would need a, b = 0 , contradiction. Thus, c = 0 , and therefore 2 − ad − a d d = 0 . Similarly, if b ̸ = 0 , we have that c = , and so ac − 13 bd = − 13 bd = 0 , or that b b 2 2 a d + 13 b d = 0 , where the same argument lets us conclude that c = d = 0 . Hence, R is an integral domain. √ √ To show it is not a UFD, consider the factorizations 14 = 2 · 7 = (1 + − 13)(1 − − 13) . On the √ √ one hand, notice all the elements involved are irreducible. Indeed, if 2 = ( a + b − 13)( c + d − 13) , then ac − 13 bd = 2 and ad + bc = 0 . But then either a or b is nonzero. But notice then that √ √ 2 2 2 ( a − b − 13)( c − d − 13) = 2 as well, meaning that multiplying these implies that ( a + 13 b )( c + 2 2 2 2 2 2 2 13 d ) = 4 . But notice that a + 13 b cannot equal 2 . Hence, either a + 13 b = 1 or c + 13 d = 1 , √ √ meaning that one of a + b − 13 , c + d − 13 is ± 1 , and so 2 is irreducible. By the same logic, we have that 7 is irreducible. √ √ √ √ As for 1 ± − 13 , notice that if (1 + − 13) = ( a + b − 13)( c + d − 13) , then ac − 13 bd = √ √ √ 1 , ad + bc = 1 , and so similarly we find that (1 − − 13) = ( a − b − 13)( c − d − 13) , so multiplying 2 2 2 2 2 2 2 2 these together yields ( a + 13 b )( c + 13 d ) = 14 . But a + 5 b , c + 5 d are positive, and cannot √ √ √ equal 2 or 7 , so one of these is 1 , and so one of a + b − 13 , c + d − 13 is ± 1 , so 1 ± − 13 is irreducible. √ √ However, notice that 1 ± − 13 are not divisible by 2 , since for any a + b − 13 , we have √ √ √ √ 2( a + b − 13) = 2 a +2 b − 13 , where a, b are integers, and so we would need 1 ± − 13 = 2 a +2 b − 13 , √ √ or (2 a − 1) = ( ± 1 − 2 b ) − 13 . But this cannot happen as − 13 is not rational. In particular, we have two factorizations where one of them is not simply a rearrangement of √ the other, or has different unit multiples. Thus, Z [ − 13] is not a UFD, ergo not a PID. 1.3 Product Rings, Quotient Rings and More Examples ′ Problem 1.3.1. Prove that the operations are well-defined. That is, if r + I = r + I and 1 1 ′ r + I = r + I, then 2 2 ′ ′ ( r + I ) + ( r + I ) = ( r + I ) + ( r + I ) 1 2 1 2 7

and ′ ′ ( r + I ) · ( r + I ) = ( r + I ) · ( r + I ) . 1 2 1 2 ′ ′ ′ ′ Solution. Suppose that r + I = r + I and r + I = r + I, where r , r , r , r ∈ R. Then, we 1 2 1 2 1 2 1 2 know that for each r ∈ ( r + r ) + I, by definition r = r + r + i for some i ∈ I. However, 1 2 1 2 ′ ′ ′ ′′ ′ ′′ r ∈ r + I, meaning that r = r + i , and similarly r = r + i , where i , i lie in I. But then 1 1 2 2 1 1 ′ ′ ′ ′′ ′ ′ ′ ′ r = r + r + ( i + i + i ) ∈ r + r + I. Therefore, ( r + I ) + ( r + I ) ⊂ ( r + I ) + ( r + I ) . By 1 2 1 2 1 2 1 2 ′ symmetry, we can run the same argument with r , r swapped, meaning that these two are equal. i i In particular, the value of ( r + I ) + ( r + I ) is independent of the choices of r , r to represent 1 2 1 2 the set r + I, and so is really a function of the set. 1 Similarly, r ∈ ( r + I ) · ( r + I ) = r r + I means that r = r r + i for some i ∈ I. But again 1 2 1 2 1 2 ′ ′ ′ ′ ′ ′′ ′ ′′ ′ ′′ we then have that r = r r + r i + r i + i i + i. Since I is an ideal, i, i , i ∈ I means that 1 2 2 1 ′ ′ ′ ′′ ′ ′′ ′ ′ ′ ′ r i + r i + i i + i ∈ I, and so r ∈ r r + I. Therefore, r r + I ⊂ r r . Again, by symmetry, 1 2 2 1 1 2 1 2 ′ we may swap the roles of the r and r to get that these two sets are equal. Again, it follows that i i ( r + I ) · ( r + I ) , the operation we defined above, is independent of the specific choice of r , r 1 2 1 2 (and only depends on the set). This shows that our operations are well-defined, which is what we wanted to show. Problem 1.3.2. Prove that R/I is a ring, equipped with the operations we defined above. Solution. We run through the conditions again. The fact that R is closed under addition and multiplication is clear, since ( r + I ) + ( r + I ) = ( r + r ) + I and ( r + I ) · ( r + I ) = r r + I are 1 2 1 2 1 2 1 2 both elements in R/I. Associativity, commutativity, and distributivity follow from the conditions for R. Indeed, for associativity we have that for all r + I, r + I, r + I ∈ R/I that 1 2 3 (( r + I ) + ( r + I )) + ( r + I ) = (( r + r ) + I ) + ( r + I ) = (( r + r ) + r ) + I 1 2 3 1 2 3 1 2 3 = ( r + ( r + r )) + I = ( r + I ) + (( r + I ) + ( r + I )) 1 2 3 1 2 3 and (( r + I ) · ( r + I )) · ( r + I ) = (( r r ) + I ) · ( r + I ) = (( r r ) r ) + I 1 2 3 1 2 3 1 2 3 = ( r ( r r )) + I = ( r + I ) · (( r + I ) · ( r + I )) . 1 2 3 1 2 3 For commutativity, we check that ( r + I ) + ( r + I ) = ( r + r ) + I = ( r + r ) + I = ( r + I ) + ( r + I ) 1 2 1 2 2 1 2 1 and ( r + I ) · ( r + I ) = ( r r ) + I = ( r r ) + I = ( r + I ) · ( r + I ) , 1 2 1 2 2 1 2 1 and for distributivity we have ( r + I ) · (( r + I ) + ( r + I )) = ( r + I ) · (( r + r ) + I ) = ( r ( r + r ) + I = ( r r + r r ) + I 1 2 3 1 2 3 1 2 3 1 2 1 3 = ( r r + I ) + ( r r + I ) = ( r + I ) · ( r + I ) + ( r + I ) · ( r + I ) . 1 2 1 3 1 2 1 3 For the identity, we verify that 0 + I is the additive identity and 1 + I is the multiplicative one, since for all r ∈ R, (0 + I ) + ( r + I ) = (0 + r ) + I = r + I and (1 + I ) · ( r + I ) = 1 · r + I = r + I. For the additive inverse, given r + I ∈ R/I, ( − r ) + I ∈ R/I is the inverse, since ( r + I ) + (( − r ) + I ) = ( r + ( − r )) + I = 0 + I, the additive identity. Having verified all of the conditions, it follows that R/I is a ring with the addition and multi- plication operations we defined above. 8

Problem 1.3.3. Let R be a ring, and let I , I be two ideals of R, such that I + I = { i + i | i ∈ 1 2 1 2 1 2 1 I , i ∈ I } = R. 1 2 2

1. Show that I ∩ I is an ideal. 1 2
2. Consider the homomorphism from R/ ( I ∩ I ) to ( R/I ) × ( R/I ) that sends r + I ∩ I to 1 2 1 2 1 2 ( r + I , r + I ) . Show that this map is well-defined and indeed a homomorphism. 1 2
3. Prove that the above map is injective.
4. Prove that the above map is surjective. As a suggestion on where to start, try considering any pair ( r + I , r + I ) , and the fact that 1 ∈ R = I + I . 1 1 2 2 1 2 ′ ′ ′ ′ Solution. 1. First, suppose that i, i ∈ I ∩ I . Then, i, i ∈ I , so i + i ∈ I . Similarly, i + i ∈ I 1 2 1 1 2 ′ ′ since both i, i lie in I . Therefore, i + i ∈ I ∩ I . 2 1 2 Similarly, for all i ∈ I ∩ I and r ∈ R, we have that ri ∈ I and ri ∈ I , and so ri ∈ I ∩ I , 1 2 1 2 1 2 meaning that I ∩ I is an ideal, as desired. 1 2 ′
5. We first argue that this map is well-defined. Indeed, suppose that r + I ∩ I = r + I ∩ I . 1 2 1 2 ′ ′ Then, r ∈ r + I ∩ I . Therefore, in particular, this means that r = r + i, where i ∈ I ∩ I . In 1 2 1 2 ′ ′ ′ particular, this means that r ∈ r + I and r ∈ r + I . Therefore, it follows that r + I ⊂ r + I , 1 2 1 1 ′ ′ ′ ′ ′ since each element of r + I can be written as r + i , where i ∈ I , and so equals r + i + i ∈ r + I . 1 1 1 ′ ′ Similarly, we have that r + I ⊂ r + I . By symmetry, replacing the roles of r and r yields that 2 2 ′ ′ ′ ′ r + I ⊂ r + I and r + I ⊂ r + I , meaning that r + I = r + I and r + I = r + I . Therefore, 1 1 2 2 1 1 2 2 this is a well-defined map R/ ( I ∩ I ) to R/I × R/I , the output value only depending on the set 1 2 1 2 r + I ∩ I and not the choice of representative. 1 2 To verify it is a ring homomorphism, we observe that given r , r ∈ R, if ϕ is this map, we note 1 2 that ϕ ( r + I ∩ I ) + ϕ ( r + I ∩ I ) = ( r + I , r + I ) + ( r + I , r + I ) 1 1 2 2 1 2 1 1 1 2 2 1 2 2 = (( r + r ) + I , ( r + r ) + I ) = ϕ (( r + I ∩ I ) + ( r + I ∩ I )) 1 2 1 1 2 2 1 1 2 2 1 2 and ϕ ( r + I ∩ I ) · ϕ ( r + I ∩ I ) = ( r + I , r + I ) · ( r + I , r + I ) 1 1 2 2 1 2 1 1 1 2 2 1 2 2 = (( r r ) + I , ( r r ) + I ) = ϕ (( r + I ∩ I ) · ( r + I ∩ I )) , 1 2 1 1 2 2 1 1 2 2 1 2 and furthermore that 1 + I ∩ I is sent to (1 + I , 1 + I ) . Noting that 1 + I is the multiplicative 1 2 1 2 1 identity of R/I , 1 + I the multiplicative identity of R/I , we see that (1 + I , 1 + I ) is the 1 2 2 1 2 multiplicative identity of the product ring. Thus, ϕ is a ring homomorphism, which is what we wanted. ′
6. Suppose that ϕ ( r + I ∩ I ) = ϕ ( r + I ∩ I ); by subtracting, this holds if and only if 1 2 1 2 ′ ϕ (( r − r ) + I ∩ I ) is the additive identity in R/I × R/I . Then, it follows that, in particular, 1 2 1 2 ′ ′ ′ ( r − r ) + I = 0 + I and ( r − r ) + I = 0 + I . But this implies that r − r ∈ I , I , and thus that 1 1 2 2 1 2 ′ r − r ∈ I ∩ I . 1 2 ′ But this means that r − r + I ∩ I is just 0 + I ∩ I , using the same argument as before (noting 1 2 1 2 ′ ′ that r − r ∈ I ∩ I and 0 ∈ I ∩ I ). Therefore, r + I ∩ I = r + I ∩ I , and thus ϕ is injective. 1 2 1 2 1 2 1 2
7. To show this is surjective, suppose that we are given an element in ( R/I , R/I ) , ( r + I , r + 1 2 1 1 2 I ) . We wish to show there is some element r ∈ R so that r + I = r + I and r + I = r + I ; 2 1 1 1 2 2 2 then r + I ∩ I will be sent by ϕ to this element. 1 2 9

In other words, we wish to construct an element r ∈ R so that r − r ∈ I , r − r ∈ I , as by the 1 1 2 2 arguments in the previous parts this is enough to show that r + I = r + I and r + I = r + I . To do 1 1 1 2 2 2 this, by assumption we have that 1 ∈ I + I , meaning that there exist elements i ∈ I , i ∈ I such 1 2 1 1 2 2 that 1 = i + i . From here, let r = r i + r i . Notice that r − r = r (1 − i )+ r i = r i + r i ∈ I 1 2 2 1 1 2 1 1 2 2 1 1 1 2 1 1 and r − r = r i + r (1 − i ) = r i + r i ∈ I . Therefore, our element r ∈ R exists, which as 2 1 2 2 1 1 2 2 2 2 we’ve argued previously is enough to show that ϕ is surjective. Problem 1.3.4. Using the previous problem, derive the Chinese Remainder Theorem for integers. Namely, show that, given relatively prime integers m, n, show that given residues r (mod m ) and 1 r (mod n ) , there exists a unique residue r (mod mn ) so r ≡ r (mod m ) and r ≡ r (mod n ) . 2 1 2 Solution. First, we show that if m, n are relatively prime, then m Z + n Z = Z . To show this, recall that Z is a PID. However, if the ideal m Z + n Z equals the ideal ⟨ d ⟩ , then we need d to divide m, n. But then d = 1 , and so therefore m Z + n Z = Z . Furthermore, note that m Z ∩ n Z = mn Z . Indeed, if d lies in both m Z and n Z , then d is divisible by both m, n. But as m, n are relatively prime, it follows that d divides mn, or that d ∈ mn Z . Therefore, m Z ∩ n Z ⊂ mn Z , and as the other inclusion is not hard to see, we find that these two ideals are actually equal. Now, by the previous problem, we know that Z /mn Z , is isomorphic to Z /m Z × Z /n Z , using the map that sends the remainder r (mod mn ) to the pair ( r (mod m ) , r (mod n )) . This map being injective and surjective means that each pair of residues, one (mod m ) and one (mod n ) , has exactly one residue modulo mn that is equivalent to the first modulo m and the second modulo n, which is what we wanted to show. 2 Vector Spaces 2.1 Definitions Problem 2.1.1. Prove the following spaces are vector spaces.

1. The set of polynomials with complex coefficients (with the standard addition and multiplica- tion operations), over the field C .
2. R , (with standard addition and multiplication operations), over the field Q . Solution. 1. Since we have previously shown that C [ x ] is a ring, we have that addition and mul- tiplication are associative, commutative, and distributive if we multiply and add two polynomials. In particular, these will also hold if we restrict our multiplication to only allowing multiplication of elements in C , namely the constant polynomials. This gives us conditions 1, 2, 3, 7. Similarly, we have conditions 4 and 5 from the fact this is a ring. Finally, notice that 1 · p ( x ) = p ( x ) for any polynomial p, since the multiplicative identity in C [ x ] is 1 , which also lies in C .
3. Again, like in the first part, we are given that R is a field that contains Q . Therefore, the fact R is closed under addition and multiplication, and that these operations are associative, commutative, and distributive means that they continue to have these properties if we restrict multiplication so the first element we multiply is a rational. This also gives us conditions 4 and 5, since R is a field, and ergo a ring. Just like in the previous part, we also have that 1 ∈ Q ⊂ R is the multiplicative identity in R too, so condition 6 holds. Hence, R is a vector space over the field Q . 10

Problem 2.1.2. Determine all possible fields k such that Z can be made into a vector space over k, using the standard addition operations. In particular, you’ll need to consider all possible scalar multiplication operations. Solution. Suppose that k is a field such that Z is a vector space over k with the typical addition operation. We will notate the elements of k with the subscript k. First, notice that if 1 + 1 = 0 , k k k then by the distributivity law we have that 0 · 1 = 1 · 1 + 1 · 1 = 2 . But 0 · 1 = (0 · 1) + (0 · 1) k k k k k k implies that 0 · 1 = 0 , contradiction. k Otherwise, if 1 + 1 is not 0 , then by the definition of a field it has a multiplicative inverse, k k k say r . But then observe that r · (1 + 1 ) = 1 implies that r + r = 1 , by the distributivity of k k k k k k k k the field operation. Finally, notice that r · 1 + r · 1 = ( r + r ) · 1 = 1 · 1 = 1 . In other words, we k k k k k have an integer that, added with itself, we get 1 . But no such integer exists. Therefore, there is no field where Z can be made into a vector space over k using the normal addition operation in Z . 2.2 Coordinates and Bases Problem 2.2.1. Find two distinct bases (the plural of basis) for the vector space of polynomials with real coefficients of degree at most 3 , and prove they are bases. Solution. There are many choices of bases that one could use for this vector space. For this solution, 2 3 2 2 3 we will show that { 1 , x, x , x } and { 1 , 1 + x, 1 + x + x , 1 + x + x + x } are both bases. We first show that the first set is linearly independent. To do this, suppose that a , a , a , a are 0 1 2 3 2 3 real, such that a + a x + a x + a x = 0 . Then, we need a , a , a , a to all be zero. Furthermore, 0 1 2 3 0 1 2 3 3 2 for spanning, any polynomial of degree at most 3 can be written as a x + a x + a x + a , which 3 2 1 0 2 3 is definitely a linear combination of 1 , x, x , x . To show the second set is a basis, we first show that this is linearly independent. Suppose there 2 2 3 are real coefficients a , a , a , a such that a + a (1 + x ) + a (1 + x + x ) + a (1 + x + x + x ) = 0 . 0 1 2 3 0 1 2 3 2 3 Then, we have ( a + a + a + a ) + ( a + a + a ) x + ( a + a ) x + a x = 0 . Then, the coefficient 0 1 2 3 1 2 3 2 3 3 3 2 of x is zero, so a = 0 . Meanwhile, the x coefficient requires a + a = 0 , so a = 0 . Repeating 3 2 3 2 this for the x coefficient yields a = 0 , and finally for the constant term we need a = 0 . This shows 1 0 2 2 3 that 1 , 1 + x, 1 + x + x , 1 + x + x + x are linearly independent. 3 2 To show they span, suppose we have a polynomial a x + a x + a x + a . Notice that this 3 2 1 0 3 2 2 equals a ( x + x + x + 1) + ( a − a )( x + x + 1) + ( a − a )( x + 1) + ( a − a ) , meaning that each 3 2 3 1 2 0 1 polynomial with real coefficients is a linear combination of the polynomials in the second set. It 2 2 3 thus follows that 1 , 1 + x, 1 + x + x , 1 + x + x + x forms a basis of the vector space of polynomials of degree at most 3 , which is what we wanted to show. Problem 2.2.2. Suppose that S is a spanning set, and v is a vector that doesn’t lie in S.

1. Show that S ∪ { v } is linearly dependent.

2. Suppose furthermore that v is nonzero. Then, show there exists a vector w ∈ S such that ( S − { w } ) ∪ { v } is a spanning set. Solution. 1. Suppose that S is a spanning set. This means that there exist vectors v , v , . . . , v 1 2 n and a ∈ k such that a v + · · · + a v = v, or that a v + a v + · · · + a v − v = 0 . But − 1 ̸ = 0 i 1 1 n n 1 1 2 2 n n in the field k, meaning that S ∪ { v } is linearly dependent, which is what we wanted to show. 11

3. Suppose that S is a spanning set of a vector space V. Then, v can be written as a linear n P combination of vectors in S, given by a v , where the v lie in S and the a lie in the field k. Since i i i i i =1 ′ v is nonzero, one of the a is nonzero, say a . We claim that S = ( S − { v } ) ∪ { v } is a spanning i 1 1 set of the vector space. m P Indeed, let w ∈ V. Since S is a spanning set, we can write w as the sum b w , where the w i i i i =1 ′ are elements of S. If none of the w are v , then this is also a linear combination of elements in S . i 1 Otherwise, by swapping labelling we can assume w = v and the other vectors are distinct. Then, 1 1 notice that m m n m X X X X 1 a i w = b w = b w + b w = b ( v − v ) + b w . i i 1 1 i i 1 i i i a a 1 1 i =1 i =2 i =2 i =2 ′ In other words, w is a linear combination of elements in S . As this holds for all w ∈ V, it follows ′ that S is a spanning set for V. Problem 2.2.3. Show that if L ̸ ⊆ S, we can replace a vector in S with one in L so that S remains a spanning set, and S ∩ L increases in size by one. Solution. Given S and L, we know that there exists some vector v that lies in L that doesn’t lie in S. Notice that v ̸ = 0 , as otherwise L is not a linearly independent set. Then, by the previous problem, there exists a vector w ∈ S such that ( S − { w } ) ∪ { v } is also a spanning set. Furthermore, by the construction in the previous problem, we can pick a w such that w ̸ ∈ L. Otherwise, per the construction in the previous problem, v is a linear combination of vectors in L ∩ S, contradicting linear independence. Therefore, writing v as a linear combination of vectors in S, there is some vector in this linear combination that lies in S but not L. We can, from the previous problem, remove this vector from S and replace it with v to get another spanning set. In other words, we can replace w with v to keep S a spanning set. By definition, notice that S ∩ L has gained an element, since we removed w from S (which does not change S ∩ L ) and added v to S (which adds an element to S ∩ L ). This is what we wanted to show. Problem 2.2.4. Using the above procedure, show that L must be finite, and that L must have at most as many elements as S. Conclude that the size of every linearly independent set is at most the size of every spanning set. Solution. Suppose that we are given a spanning set S which is finite and L which is linearly independent. If L is not contained in S, by the previous problem, we may repeatedly replace elements in S with elements in L such that | L ∩ S | strictly increases. It follows that after at most | L | steps of repeating this process, we eventually have a spanning set that contains L. Furthermore, by construction, our spanning set is the same size as S, since we remove an element from S and add a different element at each step. Therefore, it follows that | S | ≥ | L | , meaning that L in particular is also a finite subset with at most as many elements of S. Finally, noting that we can apply this procedure to any linearly independent set and any span- ning set. Therefore, this means that for any spanning set and any linearly independent set, the spanning set has at least as many elements as the linearly independent set. Problem 2.2.5. Prove the following. 12

4. Any spanning set with finitely many elements can be reduced to a basis. That is, we may remove elements from our spanning set such that the resulting set is a basis.

5. Any linearly independent set can be extended to a basis. That is, we may add elements to our linearly independent set so that the resulting set is a basis. Solution. 1. Let S = { v , v , . . . , v } be a spanning set with finitely many elements. If S is not 1 2 n linearly independent, then we claim that we can remove a vector from S while still keeping the set n P a spanning set. Indeed, suppose that there exist a ∈ k such that a v = 0 , where not all of the i i i i =1 n P a i a are zero. Without loss of generality, assume that a ̸ = 0 . Then, we have that v = − v . i 1 1 i a 1 i =2 We show that { v , v , . . . , v } is still a spanning set. Indeed, given any vector v ∈ V, our 2 3 n n P vector space, we may write it as a linear combination b v . But then notice that this equals i i i =1 n P − a b i 1 ( + b ) v , from our formula for v above. This proves that { v , v , . . . , v } is a spanning set i i 1 2 3 n a 1 i =2 of V. We can repeat this procedure until eventually we end up with a linearly independent set (as the empty set is by convention a linearly independent set, this procedure must eventually terminate with a linearly independent and spanning set). This set will then be our basis, which is a subset of our spanning set. This proves the first part of the problem.

6. Let L be a linearly independent set. From the previous problem it must be a finite set, say { v , v , . . . , v } . If L is a spanning set, we are done. Otherwise, there exists a vector v ∈ V that 1 2 k cannot be written as a linear combination of vectors in L. Consider the set L ∪ { v } . Notice that this set is also linearly independent (otherwise, a linear combination of elements in L ∪ { v } that equals k k P P − a i zero where not all coefficients are zero, say av + a v = 0 , means either a ̸ = 0 , so v = v , i k k a i =1 i =1 or a = 0 , and this linear combination tells us that the vectors in L are not linearly independent). Thus, given any linearly independent set which is not spanning, we may add a vector to it such that the set remains linearly independent. We may keep repeating this until our set is spanning. This procedure terminates since any linearly independent set has at most as many vectors as a spanning set (and we know one spanning set exists which has finitely many vectors). Therefore, we can extend a linearly independent set into a basis, which is what we wanted to show. Problem 2.2.6. Show that any two bases of our finite dimensional vector space have the same size. This size is known as the dimension of the vector space, denoted as dim V. Solution. By problem 23, every linearly independent set is at most the size of any spanning set. Therefore, in particular, since we know that V has a finite spanning set, every basis (which is a linearly independent set) also is finite length. Furthermore, from the previous problem, by starting with a finite spanning set and removing vectors, we know that every vector space has a basis. Furthermore, if our bases are B and B , then noting that B is linearly independent and B 1 2 1 2 is spanning yields that | B | ≤ | B | . But similarly, B is spanning and B is linearly independent, 1 2 1 2 so | B | ≥ | B | . Combining these equalities yields that | B | = | B | , which is the dimension of V, as 1 2 1 2 desired. Problem 2.2.7. Show that if W is a subspace of V, then the dimension of W is at most that of V. 13

Solution. If W is a subspace of V, we know that a basis of W exists. This set is linearly independent. Therefore, the number of elements in this basis is at most the dimension of V, which is the size of any basis of V (which, in particular, is a spanning set). Therefore, dim V ≥ dim W, which is what we wanted to show. 2.3 Linear Transforms Problem 2.3.1. Suppose that k = Q , and V, W are vector spaces over Q . Show that if T : V → W satisfies T ( v + v ) = T ( v ) + T ( v ) for all v , v ∈ V, then T is actually linear. 1 2 1 2 1 2 Solution. Suppose that f ( v + v ) = f ( v ) + f ( v ) for all v , v in a vector space V over Q . We will 1 2 1 2 1 2 show that f ( qv ) = qf ( v ) for all vectors v ∈ V. We can first argue by induction that f ( mv ) = mf ( v ) for all m ∈ N . Indeed, the base case m = 1 is given by definition, and given that this holds for m ≤ k, then f (( k + 1) v ) = f ( v ) + f ( kv ) = f ( v ) + kf ( v ) = ( k + 1) f ( v ) . Notice that this can be extended to m ∈ Z , by observing that f ( mv ) + f (( − m ) v ) = f ( mv + ( − m ) v ) = f (( m + − m ) v ) = f (0) = 0 , since f (0) + f (0) = f (0) , or f (0) = 0 . Finally, given a rational number q = m/n, notice that nf ( qv ) = f ( mv ) = mf ( v ) , or that f ( qv ) = m/nf ( v ) = qf ( v ) for all v ∈ V. Therefore, it follows that f ( qv ) = qf ( v ) for all q ∈ Q and v ∈ V, or that f is linear, which is what we wanted to show. Problem 2.3.2. Show that ker T is a subspace of V. Solution. In order to show this is a subspace of V, we need to verify that this space contains 0 and V is closed under addition and scalar multiplication. Notice that T (0) + T (0) = T (0 + 0) = T (0) , or that T (0) = 0 , meaning that 0 ∈ ker T. Furthermore, given v , v ∈ V, we have that T ( v + v ) = V 1 2 1 2 T ( v ) + T ( v ) = 0 + 0 = 0 , so hence ker T is closed under addition. Finally, given v ∈ V and 1 2 r ∈ k, we have that T ( rv ) = rT ( v ) = r · 0 = 0 . But this means that ker T is closed under scalar W W multiplication. In other words, we have that ker T is a subspace of V, which is what we wanted to show. Problem 2.3.3. Suppose that V and W are finite dimensional vector spaces with the same dimen- sion d. Prove that V, W are isomorphic ; that is, there exists an isomorphism between them. Solution. Suppose that V, W both are vector spaces of dimension d. Then, it follows that there exist bases v , v , . . . , v of V and w , w , . . . , w of W. Let T : V → W be the map given by 1 2 d 1 2 d n n P P T ( a v ) = a w . i i i i i =1 i =1 First, notice that this map is well-defined. Indeed, since v , v , . . . , v is spanning, we have that 1 2 d n n P P ′ ′ this formula defines the map for all v ∈ V. Furthermore, if a v = a v , where the a , a ∈ k, i i i i i i i =1 i =1 n P ′ ′ then ( a − a ) v = 0 . But since the v are linearly independent, it follows that a = a for each i. i i i i i i i =1 But then this map is well-defined, since each v has a unique representation as a linear combination of the vectors v . i n P We verify first that this is a linear transformation. Indeed, given vectors v = a v and i i i =1 14

n P ′ ′ v = a v , we notice that i i i =1 n n n n X X X X ′ ′ ′ ′ ′ T ( v + v ) = T ( ( a + a ) v ) = ( a + a ) w = a w + a w = T ( v ) + T ( v ) . i i i i i i i i i i i =1 i =1 i =1 i =1 n n P P Similarly, we find that given this vector v, and s ∈ k, we have T ( sv ) = T ( sa v ) = sa w = i i i i i =1 i =1 sT ( v ) . Therefore, T is linear. n n P P Furthermore, we can define the linear map S : W → V by S ( s w ) = s v , which by the i i i i i =1 i =1 same logic as above is well-defined and a linear map. Finally, notice that for all vectors v ∈ V, if n n n n P P P P v = a v , then S ( T ( v )) = S ( a w ) = a v , and similarly given w ∈ W, if w = b w , then i i i i i i i i i =1 i =1 i =1 i =1 n n P P T ( S ( w )) = T ( b v ) = b w . Therefore, S, T are inverses, so V, W are isomorphic, as desired i i i i i =1 i =1 (noting that maps with inverses are bijective). Problem 2.3.4. Prove that an infinite dimensional vector space cannot be isomorphic to a finite dimensional vector space. Solution. Suppose for the sake of contradiction that V, W are isomorphic vector spaces, with V infinite-dimensional and W finite-dimensional, and T : W → V is our isomorphism. Then, as W is finite-dimensional, it has a finite spanning set { w , w , . . . , w } . Now, since T is an isomorphism, it 1 2 n is surjective, meaning that every v ∈ V can be written as v = T ( w ) for some w ∈ W. But from our n n P P spanning set, w = a w for some a ∈ k, meaning that, by linearity, v = T ( w ) = a T ( w ) . i i i i i i =1 i =1 In particular, this means that every element of V is a linear combination of vectors in the set T ( w ) , T ( w ) , . . . , T ( w ) , meaning that V has a finite spanning set. But this contradicts the fact 1 2 n that V is infinite dimensional. Therefore, there cannot be an isomorphism between a finite dimensional vector space and an infinite dimensional vector space, as desired. Problem 2.3.5. To prove the theorem, prove the following:

1. Show that this basis of ker T can be extended to a basis of V.
2. Suppose that this extension adds vectors w , w , . . . , w . Show that T ( w ) , T ( w ) , n +1 n +2 m n +1 n +2 . . . , T ( w ) form a basis for imT, and from here prove the theorem. m Solution. 1. For the first part, we observe that a basis of ker T is linearly independent in V. Therefore, by Problem 2.2.5, we can extend this linearly independent set to a basis of V. Say this gives us the vectors w , w , . . . , w , w , . . . , w . 1 2 n n +1 m
3. We now verify that T ( w ) , . . . , T ( w ) forms a basis for imT. First, we check that this is n +1 m spanning. To see this, suppose that w ∈ imT, so then w = T ( v ) for some v ∈ V. Since w , w , . . . , w 1 2 m m m P P is a basis of V, we can write v = a w for some a ∈ k. Therefore, w = T ( v ) = a T ( w ) . Since i i i i i i =1 i =1 m P w , w , . . . , w ∈ ker T, this equals a T ( w ) . This shows that T ( w ) , for i = n + 1 , n + 2 , . . . , m, 1 2 n i i i i = n +1 span imT. 15

m m P P To show that these are linearly independent, suppose that a T ( w ) , we have that T ( a w ) = i i i i i = n +1 i = n +1 m m n P P P 0 . Therefore, a w ∈ ker T, so hence a w = ( − a ) w for some a , a , . . . , a ∈ k, since i i i i i i 1 2 n i = n +1 i = n +1 i =1 m P w , w , . . . , w is a basis for ker T. But this means that a w = 0 , or that all of the a are zero. 1 2 n i i i i =1 In particular, this means that T ( w ) , T ( w ) , . . . , T ( w ) is linearly independent, and therefore n +1 n +2 m they form a basis for imT. In particular, dim imT = m − n = dim V − dim ker T, which is enough to prove the theorem. Problem 2.3.6. Show that two finite dimensional vector spaces are isomorphic if and only if they have the same dimension. Solution. We have already shown that two finite dimensional vector spaces that are the same dimension are isomorphic to each other. Now, suppose that V, W are isomorphic vector spaces; consider linear transformations T : V → W that is an isomorphism. Then, using the above result, we note that dim ker T = 0 , since ker T only consists of the 0 vector by T being injective (the empty set being a basis for ker T ). Furthermore, T is surjective, meaning that imT = W. But then dim V = dim ker T + dim imT = 0 + dim W = dim W, meaning that V, W are the same dimension, which is what we wanted to show. 2.4 Matrices and Row Reduction Problem 2.4.1. Show that this above map is well-defined and is an isomorphism between V and n k . Solution. We first check that this map is well-defined. However, this follows from the fact that w , w , . . . , w is a basis for V, meaning that the coefficients a , a , . . . , a are uniquely defined by 1 2 n 1 2 n v (as the difference between two such representations of v is a linear combination of the w that i yields 0 , which by linear independence must be zero). ′ To show that this linear, suppose this map is T. We observe that, given vectors v, v ∈ V,   ′ a + a 1 1 ′   a + a 2 2   n n P P ′   ′ ′ ′ a + a 3 3 if v = a w and v = a w , then our map sends v + v to the column vector =   i i i i   . i =1 i =1 .   . ′ a + a n n       ′ a a aa 1 1 1 ′       a a aa 2 2 2       ′       ′ a a aa 3 3 3

• , which is equal to T ( v )+ T ( v ) . In addition, given a ∈ k, we have T ( av ) = =             . . . . . .       . . . ′ a a aa n n n   a 1   a 2     a 3 a = aT ( v ) . Hence, this map is linear.     . .   . a n 16

    a 0 1     a 0 2     n P     a 0 3 Injectivity is clear: ker T consists of the vectors that send a v to = , or that     i i     . . i =1 . .     . . a 0 n   a 1   a 2   n P   a 3 v = 0 + 0 + · · · + 0 . Surjectivity is also clear, since = T ( a w ) , and thus we have shown   i i   . i =1 .   . a n that T is an isomorphism, which is what we wanted. Problem 2.4.2. Show that if we multiply the matrix of T with the coordinate representation of v ∈ V, we get the coordinate representation of T ( v ) . In this sense, our notion of matrix multiplication is consistent with the way our linear transformation acts on vectors. n n n m P P P P Solution. Suppose that we are given a vector v = a v . Then, T ( v ) = a T ( v ) = a a w , i i i i i j,i j i =1 i =1 i =1 j =1   n P a a i 1 ,i   i =1   n P   a a   i 2 ,i   i =1   n P   which has coordinate representation . Meanwhile, if we consider the matrix multipli- a a  i 3 ,i    i =1   .   . .    n  P a a i m,i i =1 cation of the coordinates of v, we have   n P a a i 1 ,i   i =1     n   P a   1 a a · · · a a a   11 12 1 n i 2 ,i   a   2 i =1     a a · · · a   21 22 2 n n P     a   3 = ,     . . . a a i 3 ,i   . . .     . . . .   i =1 .   .   . a a · · · a   m 1 m 2 mn . . a   n   n P a a i m,i i =1 which is the same as the coordinate representation of T ( v ) . Problem 2.4.3. Show that there exists bases for V, W such that the only nonzero entries of T are along the diagonal; that is, only the ( i, i )th entries are nonzero for i = 1 , 2 , . . . , r for some nonnegative integer r. What is the value of r ? Solution. Consider the subspace ker T ⊂ V ; this vector space has a basis v , v , v , . . . , v . Extend 1 2 3 k this to a basis of V by v , v , . . . , v , v , v , . . . , v . Relabel this basis, furthermore, such that 1 2 k k +1 k +2 n 17

v , v , . . . , v are the basis vectors of ker T. Now, consider the vectors w = T ( v ) , w = n − k +1 n − k +2 n 1 1 2 T ( v ) , . . . , w = T ( v ) . By Problem 31, these vectors form a basis for imT, and therefore are 2 n − k n − k linearly independent in W. Hence, we may extend this to a basis w , w , . . . , w . 1 2 m Consider the matrix for T with respect to these bases. Then, observe that T ( v ) = w for i i 1 ≤ i ≤ n − k, and T ( v ) = 0 otherwise, by construction. Therefore, the matrix of T looks like i   1 0 0 · · · 0   0 1 0 · · · 0     0 0 1 · · · 0 ,     . . . . . . . . . .   . . . . . 0 0 0 · · · 0 which is what we wanted to show. We observe that r, the value above, is equal to n − k = dim V − dim ker T = dim imT, which is the rank of T. Problem 2.4.4. Show that if we apply one of our row reduction operations to a matrix for T, we get another matrix for T, using a different basis for W (but the same basis for V ). How do you relate the old basis to the new basis? Solution. Suppose that we are given a matrix for T, with entries a , with respect to the bases i,j m P v , v , . . . , v for V and w , w , . . . , w for W. By definition, for each i, we have T ( v ) = a w . 1 2 n 1 2 m i ji j j =1 We consider each of the choices of row operation.

1. Consider scaling up the r th row of the matrix by c ̸ = 0 . Then, notice that if the entries of ′ this new matrix are a , notice that i,j m r − 1 m X X X w r ′ ′ ′ T ( v ) = a w = a w + a + a w . i ji j j j ji ri ji c j =1 j =1 j = r +1 Notice that this holds for each i, so it suffices to check that w , w , . . . , w , w /c, w , . . . , w 1 2 r − 1 r r +1 m is a basis for W. This follows as this is still a spanning set (we can write any vector as a linear combination of w , w , . . . , w , which gives us a linear combination of our new basis, scaling 1 2 m up the coefficient of the r th vector by c ̸ = 0), and is still linearly independent (if a linear com- bination of these vectors is 0 , then this is a linear combination of our original basis, with the coefficient of the r th vector scaled down by 1 /c ; these must be zero, so the original coefficients were zero too).

2. Consider swapping the r th row with the s th row, r ̸ = s. Then, if our new matrix has entries ′ ′ ′ ′ a , then a = a if i ̸ = r, s, a = a , and a = a . We can easily check that i,j s,j r,j i,j i,j r,j s,j m X X ′ ′ ′ T ( v ) = a w = a w + a w + a w . i ji j j s r ji ri si j =1 1 ≤ j ≤ m j ̸ = r,s This corresponds, then, to the basis with w , w swapped positions (which does not affect r s spanning or linear independence). 18

3. Consider adding c times the r th row to the s th row, where r ̸ = s. Then, if our new matrix ′ ′ ′ has entries a , then a = a if i ̸ = s and a = a + ca . We again see that i,j s,j r,j i,j i,j s,j m X X X ′ ′ ′ ′ ′ T ( v ) = a w = a w + ( a − ca ) w = a w + a ( w − cw ) . i ji j j s j r s ji si ri ji ri j =1 1 ≤ j ≤ m 1 ≤ j ≤ m j ̸ = s j ̸ = r This corresponds to the basis w , w , . . . , w − cw , w , . . . , w . 1 2 r s r +1 m We need to check that this is a basis. For spanning, given a vector w ∈ W, we may write it as m P P a w , which is also equal to ( a + ca ) w + a ( w − cw ) + a w . Hence, every vector i i s r s r r s i i i =1 1 ≤ i ≤ m i ̸ = r,s in W is a linear combination of vectors in our new set, so our set is actually spanning. For linear independence: X X a ( w − cw ) + a w = ( a − ca ) w + a w = 0 r r s i i s r s i i 1 ≤ i ≤ m 1 ≤ i ≤ m i ̸ = r i ̸ = s implies that a = 0 for i ̸ = s, and a − ca = 0 . But a = 0 implies that a = 0 , which means i s r r s our vectors are linearly independent. Therefore, our set is actually a basis. Therefore, each row reduction step turns the matrix of T into a different matrix of T with respect to a different basis for W, which is what we wanted to show. We can relate the old bases to the new bases in each type of operation through what we computed above.

4. For the first, if we scale the r th row by c, this corresponds to scaling the r th basis vector by 1 /c.

5. For the second, swapping rows r, s corresponds to swapping the r th and s th basis vectors.

6. For the third, adding c times row r to row s corresponds to adding − c of the s th basis vector to the r th basis vector. Problem 2.4.5. Reduce the following matrices to reduced row echelon form. 1 2 3

6 5 4   4 2 − 1 − 3   2. 1 0 − 5 2 0 1 0 2 1 2 3 Solution. 1. We start with the matrix . Adding − 6 times the first row to the second 6 5 4 1 2 3 row yields the matrix . Dividing the second row by − 7 then yields the matrix 0 − 7 − 14 1 2 3 1 0 − 1 . Finally, subtracting two times the second row from the first row yields , 0 1 2 0 1 2 which is our desired reduced row echelon form. 19

  4 2 − 1 − 3   2. We start with the matrix 1 0 − 5 2 . Swap the first and second rows to get the ma- 0 1 0 2     1 0 − 5 2 1 0 − 5 2     4 2 − 1 − 3 0 2 19 − 11 trix . Subtract four times the first row from the second to get . 0 1 0 2 0 1 0 2   1 0 − 5 2   Swap the second and third row to get 0 1 0 2 . Subtract two times the second row from 0 2 19 − 11     1 0 − 5 2 1 0 − 5 2     the third row to get 0 1 0 2 . Divide the third row by 19 to get 0 1 0 2 . 15 0 0 19 − 15 0 0 1 − 19   − 37 1 0 0 19   Finally, add 5 times the third row to the first row to get 0 1 0 2 . This is our desired 15 0 0 1 − 19 reduced row echelon form. Problem 2.4.6. Show that for any i, using the row operations on the matrix for T, if column i had at least one nonzero entry initially, then there is a sequence of row operations such that the resulting matrix only has one nonzero entry in column i, and it is a 1 . Solution. Suppose that the matrix for T has a nonzero entry in column i at row j. Say that the entries of T are a in row k and column l, and suppose T has m columns and n rows. Then, for kl − a ki each k ̸ = j, if we add times the j th row to the k th row, notice that the entry in row k, column a ji − a 1 ki i is a + a = 0 . Finally, if we scale the j th row by , the j th row has a 1 in column i. ki ji a a ji ji In particular, using these row operations, we can change the matrix of T such that the i th column only has one nonzero entry, namely 1 (in the j th row), which is what we wanted. Problem 2.4.7. Using the above subprocedure, show that any matrix can be reduced to reduced row echelon form. Solution. We inductively show that, for a matrix T with m rows and n columns, for a given positive integer i, by performing row operations, we can reduce our matrix to a form such that

1. Among the first i rows, for each row with a nonzero entry, their leftmost nonzero entry is a 1 , which are pivots.
2. These i pivots are the only nonzero entry in their column.
3. The pivot of the k th row is left of the pivot of the j th row if k < j.
4. If the pivot of the last nonzero row among the first i rows is in column k, then the leftmost nonzero entry of any other row is right of column k.
5. Any rows with all zeroes at at the bottom of the matrix. Our base case is i = 1 . If there is no row with nonzero entries, then the matrix is the zero matrix, and there is nothing we need to do. Otherwise, we first swap rows such that all of the rows that are entirely zero are at the bottom; in particular, by assumption, the first row is nonzero. Consider the 20

first column k with a nonzero entry ( k being the smallest index); suppose that row l has a nonzero entry in column k. We can then swap this with row 1 , so row 1 has a nonzero entry in column k. Using the subprocedure from the previous problem, we can make it such that row 1 has a 1 in column k, and all the other rows have a zero in column k. Furthermore, in row 1 , there are only zeros to the left of this 1 , and by construction there are no nonzero entries to the left of column k. Swapping the rows around to get all of the zero rows at the bottom gives us a matrix satisfying the base case. Suppose we have shown this for i − 1 , and i ≤ m. If all of the rows outside of these rows are zero, then this clearly satisfies the conditions for i. Otherwise, we know that row i is not all zeros by construction, and furthermore rows 1 , 2 , . . . , i − 1 all have pivots (and are nonzero). Among the nonzero rows that are below the ( i − 1)st row, consider the leftmost nonzero entries of each row. Let row l be the row with the leftmost such entry, and say it is in column k. Swap row l with row i. Next, perform the subprocedure such that row i has a 1 in column k, and and no other row has a nonzero entry in column k. Finally, again swap rows such that all rows with all zeroes are at the bottom of the matrix. By assumption of which case we are in, rows 1 to i − 1 had pivots, and these pivots are not changed by the subprocedure, since in the columns of those pivots row i has a zero, by our inductive hypothesis. Row i, then, also has a pivot by our procedure, and furthermore we have made it such that the pivot is the only nonzero entry in the column. For the other i − 1 pivots, we have not changed this, since in the columns of those pivots, row i had a zero, and so the column does not change. ′ For the third condition, suppose that the pivot of row i − 1 is in column k . Then, by the ′ inductive hypothesis fourth condition, k > k , meaning that the pivot of row i is right of every pivot in rows 1 , 2 , . . . , i − 1 . For the fourth condition, by assumption, in all the other rows they only have zeros in columns left of column k, and from our subprocedure they have only zeros in column k. Finally, the fifth condition holds by our swapping at the end (which does not affect rows 1 to i, and therefore still preserves the first four conditions). This finishes the inductive step, and thus we have shown that the condition above holds for each i ≤ m. In particular, if i = m, we obtain the reduced row echelon form. Problem 2.4.8. Show that the number of pivots of T is equal to the rank of T, and the number of columns without pivots is equal to the nullity of T, without using the rank-nullity theorem. (One can prove the rank-nullity theorem by analyzing the reduced row echelon form of a matrix). Solution. First, notice that the rank of T : V → W is the dimension of the image, and furthermore the rank does not change under row operations, since these row operations simply correspond to changing bases (and not the underlying vectors underneath). So it suffices to compute the rank and nullity corresponding to the reduced row echelon form for the matrix. Suppose that T has k pivots, and these are in columns i , i , . . . , i . Suppose that this matrix 1 2 k corresponds to bases { v , v , . . . , v } for V and { w , w , . . . , w } for W. Then, notice that the image 1 2 n 1 2 n contains w for j = 1 , 2 , . . . , k, since by definition v gets sent to w . Furthermore, notice that since j i j j T has k pivots, and each nonzero row has a pivot, rows k + 1 , k + 2 , . . . , m are all zeros, meaning that the image only contains vectors that are linear combinations of w , w , . . . , w . In particular, 1 2 k the image has dimension k ( w , w , . . . , w all lie in the image, and they linearly independent and 1 2 k span the image). n P We now consider the kernel. Suppose that v = x v gets sent to zero. Then, by considering i i i =1 21

the matrix multiplication, we note that if the matrix for T has entries a , then the j th coordinate ij n P of T v is a x . Notice for j > k that this is automatically zero. Meanwhile, for j ≤ k, this ji i i =1 n n P P equation is of the form x + a x = 0 , or that x = − a x . Let S = { i , i , . . . , i } . i ji i i ji i 1 2 k j j i = i +1 i = i +1 j j n P In particular, this means that v = x v is therefore equal to i i i =1 k n X X X v = − a x v + x v . ji i i i i j j =1 i = i +1 1 ≤ i ≤ n j i ̸ ∈ S ! k P P Notice that a = 0 for l ̸ = j, meaning that we can rewrite this as x v − x a v ) . ji i i i ji i l j 1 ≤ i ≤ n j =1 i ̸ ∈ S In other words, every element in the kernel has to be a linear combination of the n − k vectors k P ′ v = v − a v , where i ̸ ∈ S. Furthermore, we can manually check here that these vectors all i ji i i j j =1 k P lie in the kernel: the j th coordinate of T ( v − a v ) is equal to − a + a = 0 if j < k, and 0 i ji i ji ji j j =1 otherwise. P ′ Finally, these vectors are linearly independent, since if a v = 0 , then notice that, expanding i i i ̸ ∈ S ′ ′ this in terms of the v , the only v with a nonzero v term, for j ̸ ∈ S, is v , and the coefficient is j j i j 1 , meaning that we need a = 0 for each j ̸ ∈ S. Thus, these vectors are linearly independent, and j therefore they form a basis for the kernel. In particular, the nullity of T is n − k, which is also the number of columns without a pivot. 3 Modules Problem 3.0.1. Show that for any ring R and ideal I of R, I is an R − module under the addition and multiplication operations of the ring R. Solution. We check the properties of a module. We note for an ideal I that property 1 follows from the definition of an ideal, and properties 2, 3, 6, 7 follow from the properties for a ring R. For property 4 , we notice that in a ring R, 0 · r = 0 , so in particular 0 ∈ I (by multiplying an element of I by 0). Property 5 follows from the fact that, if ( − 1) is the additive inverse of 1 , then ( − 1) · r is the additive inverse of r, since r + ( − 1) · r = 1 · r + ( − 1) · r = (1 + ( − 1)) · r = 0 · r = 0 . As all of the properties have been checked, it follows that I is a module over R. n Problem 3.0.2. Show that any finitely generated free module is isomorphic to R for some n ∈ N . Solution. Suppose that M is a finitely generated free module over a ring R. We know that, as it is free, it has a free basis, and furthermore that this free basis is finite from finite generation (pick a finite set of generators, and write them as linear combinations of the free basis: only finitely many elements in the basis are used, so every element can be written as a linear combination of 22

elements among these finitely many. In particular, there can be no other basis elements by linear independence). n Now, suppose this free basis is m , m , . . . , m . Consider the map ϕ : M → R defined by 1 2 n n P n sending r m to ( r , r , . . . , r ) ∈ R . First, this is well-defined, since from the definition of free i i 1 2 n i =1 basis, every element has such a form, and furthermore this form is unique by linear independence (the difference of two possible forms is a linear combination of zero, so all of the coefficients have to be zero by linear independence). We can easily verify that this map satisfies the properties for a module homomorphism, since n n n n n X X X X X ′ ′ ′ ′ ′ ′ ϕ ( r m + r m ) = ϕ ( ( r + r ) m ) = ( r + r , r + r , . . . , r + r ) = ϕ ( r m )+ ϕ ( r m ) i i i i i 1 2 n i i i i i 1 2 n i i =1 i =1 i =1 i =1 i =1 and for r ∈ R, we have n n n X X X ϕ ( r · r m ) = ϕ ( rr m ) = ( rr , rr , . . . , rr ) = rϕ ( r m ) . i i i i 1 2 n i i i =1 i =1 i =1 n We can check that this is surjective, since any element ( r , r , . . . , r ) ∈ R arises from the 1 2 n n P n element r m . For injectivity, if an element maps to (0 , 0 , . . . , 0) ∈ R , then notice that it maps i i i =1 n P from 0 m = 0 . Therefore, this map ϕ is a homomorphism which is injective and surjective, and i i =1 therefore an isomorphism. Problem 3.0.3. Given a submodule N of an R − module M, consider the map κ : M → M/N M,N that sends m to m + N. Show that this map is a surjective homomorphism. What is the kernel of κ ? M,N ′ Solution. We first check that this is a homomorphism of modules. Suppose that m, m ∈ M. Then, ′ ′ ′ ′ ϕ ( m + m ) = ( m + m ) + N = { m + m + n | n ∈ N } . But by definition, ( m + m ) + N = ( m + N ) + ′ ′ ( m + N ) = ϕ ( m ) + ϕ ( m ) . Furthermore, if r ∈ R, then ϕ ( rm ) = rm + N = r ( m + N ) = rϕ ( m ) , so this is a homomorphism. To check that it is surjective, we know that every element in M/N is of the form m + N for some m ∈ M ; but then this means that ϕ ( m ) = m + N, so this is surjective. For the kernel, we claim that the kernel is N. Indeed, if m + N = N, then in particular we require m + 0 ∈ N. But then m ∈ N. This in turn implies that for all n ∈ N, we have m + n ∈ N, so m + N ⊂ N. Furthermore, for all n ∈ N, n − m ∈ N, so m + ( n − m ) ∈ m + N, and thus N ⊂ m + N, or that N = m + N, as desired. Problem 3.0.4. Given a homomorphism between R − modules M, N : ¯

1. Show that there exists a homomorphism ϕ : M/ ker ϕ → N such that ¯ ϕ ( κ ( m )) = ϕ ( m ) M, ker ϕ for all m ∈ M.
2. Show that M/ ker ϕ is isomorphic to im ϕ. 23

¯ Solution. 1. Consider the map ϕ defined by sending m + ker ϕ to ϕ ( m ) . This satisfies the desired property that ¯ ϕ ( κ ( m )) = ϕ ( m ) , M, ker ϕ ¯ ¯ since ϕ ( κ ( m )) = ϕ ( m + ker ϕ ) = ϕ ( m ) . We need to check that this is a well-defined homo- M, ker ϕ morphism. ′ Suppose that m + ker ϕ = m + ker ϕ. Then, in particular, as 0 ∈ ker ϕ, we have that m ∈ ′ ′ ′ m + ker ϕ, so there exists some k ∈ ker ϕ so that m = m + k. But then ϕ ( m ) = ϕ ( m + k ) = ′ ′ ′ ¯ ¯ ϕ ( m ) + ϕ ( k ) = ϕ ( m ) , and so ϕ ( m + ker ϕ ) = ϕm + ker ϕ ) , so this is well-defined. To check that this is a homomorphism, we verify that ′ ′ ′ ¯ ¯ ϕ (( m + ker ϕ ) + ( m + ker ϕ )) = ϕ (( m + m ) + ker ϕ ) = ϕ ( m + m ) ′ ′ ¯ ¯ = ϕ ( m ) + ϕ ( m ) = ϕ ( m + ker ϕ ) + ϕ ( m + ker ϕ ) , and ¯ ¯ ¯ ϕ ( r ( m + ker ϕ )) = ϕ ( rm + ker ϕ ) = ϕ ( rm ) = rϕ ( m ) = r ϕ ( m + ker ϕ ) . This shows that we have the desired homomorphism. ¯ 2. To show that the modules are isomorphic, we claim that ϕ is our desired isomorphism. We note that our above homomorphism is a well-defined homomorphism from M/ ker ϕ to im ϕ. We need to check that it is injective and surjective. For surjectivity, by definition, for all n ∈ im ϕ, n = ϕ ( m ) for some m ∈ M. But then we have ¯ that ϕ ( m + ker ϕ ) = ϕ ( n ) . We just need to show that this map is injective. ¯ Suppose that m + ker ϕ gets sent by ϕ to zero. Then, by definition, ϕ ( m ) = 0 , meaning that m ∈ ker ϕ. But then m + ker ϕ = ker ϕ, which is enough to prove injectivity. 4 The PID Structure Theorem 4.1 Noetherian Rings and Modules Problem 4.1.1. Prove the following.

1. Show that every ideal can be generated by a finite set of elements in a Noetherian ring. ∞ S
2. For any chain I ⊂ I ⊂ I ⊂ . . . of ideals, show that I is an ideal. 1 2 3 i i =1
3. Suppose that ring R is such that every ideal can be generated by a finite set of elements. Prove that R is Noetherian. As a hint, consider the previous part, and consider a finite set that generates the union of ideals in the chain. Where do each of the elements in this finite set live?
4. Conclude that every PID is Noetherian. Solution. 1. Suppose for the sake of contradiction that some ideal I cannot be generated by a finite set of elements. We show that R is not Noetherian. To do this, we define the ideals I inductively, as follows. First, let i be an element in I, and j 0 let I = ⟨ i ⟩ . Now, given the elements i , i , . . . , i , and ideals I = ⟨ i , i , . . . , i ⟩ for j = 0 , 1 , . . . , n, 0 0 0 1 n j 0 1 j 24

we know that I ̸ = I since I cannot be generated by a finite set of elements. Thus, there exists an n element i ∈ I − I . From here, let I = ⟨ i , i , . . . , i ⟩ . n +1 n n +1 0 1 n +1 Notice that this inductive construction yields a chain of ideals I ⊂ I ⊂ I ⊂ . . . . However, 0 1 2 notice that by construction, I = ⟨ i , i , . . . , i ⟩ is not equal to I , since I contains i , but j 0 1 j j +1 j +1 j +1 I does not (by definition). This is a contradiction of the fact that R is Noetherian. j Therefore, it follows that every ideal I can be generated by a finite set of elements, which is what we wanted to show. ∞ S 2. Given a chain of ideals I ⊂ I ⊂ . . . , we show that I is an ideal. First, suppose that 1 2 i i =1 r , r lie in this set. It follows that there exist i , i ∈ { 1 , 2 , . . . } such that r ∈ I for j = 1 , 2 . But 1 2 1 2 j i j ∞ S then if i is the maximum of i , i , from our chain we have that r , r ∈ I , so r + r ∈ I ⊂ I . 1 2 1 2 i 1 2 i i i =1 ∞ S Furthermore, for all r ∈ I and s ∈ R, there exists an i ∈ { 1 , 2 , . . . } such that r ∈ I . Then, i i i =1 ∞ S sr ∈ I ⊂ I , and we are done. i i i =1 3. Suppose that every ideal can be generated by a finite set of elements. Then, consider any ascending chain of ideals in R, say I ⊂ I ⊂ I ⊂ . . . . Let I be their union; from the previous 1 2 3 part, we know this is an ideal, so it can be generated by a finite set of elements { r , r , . . . , r } . By 1 2 k definition, each r lies in a union of the I , so there exists some i for each j so that r ∈ I . Let i j i j j i j ′ be the maximum of the i values, so { r , r , . . . , r } ⊂ I . Then, notice that for all i ≥ i, we have j 1 2 k i ′ that I ⊂ I ⊂ I. But I = ⟨ r , r , . . . , r ⟩ ⊂ I , since for all s , s , . . . , r ∈ R, by I being an ideal, i i 1 2 k i 1 2 k i k P ′ s r ∈ I . Therefore, I ⊂ I ⊂ I ⊂ I , meaning that all of these subsets are equalities. j j i i i i j =1 ′ ′ In particular, I = I for all i ≥ i. As this holds for all ascending chains of ideals, it follows i i that R is a Noetherian ring. 4. By definition, every ideal in a PID can be generated by a single element, and so thus it can be generated by a finite number of elements. But by the previous part, it must be Noetherian, which is what we wanted to show. Problem 4.1.2. Prove the following statements.

1. Show that if M is a Noetherian module, then every submodule of M is finitely generated. (Hint: can you think of what a submodule generated by elements would be?)
2. Suppose that every submodule of M is finitely generated. Prove that M is Noetherian. Solution. 1. Suppose that N is a submodule of M, and suppose for the sake of contradiction that N was not finitely generated. Then, we can construct a sequence of elements n , n , . . . that lie 1 2 in N such that for each i, the module generated by n , n , . . . , n does not contain n . Let N 1 2 k k +1 k be the submodule of M consisting of all linear combination of elements { n , n , . . . , n } . Then, by 1 2 k construction, N ⊂ N for each k ∈ N , but n ̸ ∈ N , meaning that N ̸ = N . k k +1 k +1 k k k +1 We therefore have an increasing chain of submodules in M, given by N ⊂ N ⊂ . . . , which does 1 2 not stabilize by construction. This is a contradiction. Hence, N must be finitely generated, which is what we wanted to show.
3. Suppose that M is a module where every submodule of M is Noetherian, and suppose N ⊂ N ⊂ . . . is an increasing chain of submodules of M. Let N be the union of these modules. 1 2 Notice that it is also a submodule of M ; indeed, if n , n ∈ N, there is some i , i so n ∈ N 1 2 1 2 j i j 25

for j = 1 , 2 . But then letting i be the maximum of the i , we have that n , n lie in N , and so j 1 2 i n + n , rn ∈ N ⊂ N for all r ∈ R. 1 2 1 i Since this is a submodule of M, it is finitely generated, say by n , n , . . . , n . Furthermore, each 1 2 k of these generators has to lie in some module in the increasing chain. Therefore, there is some i such that n , n , . . . , n ∈ N . However, this means that every linear combination of the n lie in 1 2 k i j N too. But these linear combinations are precisely N, by definition, meaning that N ⊂ N . In i i particular, for l ≥ i, we have N ⊂ N ⊂ N ⊂ N , or that N = N for l ≥ i, which is what we i l i l i wanted to show. Problem 4.1.3. Given an R − module M and a submodule N of M, show that if M is Noetherian, then N, M/N are both Noetherian. (Hint: consider the map κ , and use the previous problem). M,N Solution. Suppose that M is Noetherian. By the previous problem, this means that every submodule of M is finitely generated. In particular, this means that every submodule of N is also finitely ′ generated, meaning that N is Noetherian. Furthermore, suppose that L is a submodule of M/N. − 1 ′ ′ Consider the set κ ( L ) , the set of elements which get sent to L under the κ map. Then, M,N M,N ′ observe that, since κ is a homomorphism, and furthermore L is a submodule of M/N, that this M,N − 1 ′ ′ is also a submodule: for instance, l , l ∈ κ ( L ) means that κ ( l ) , κ ( l ) ∈ L , or that 1 2 M,N 1 M,N 2 M,N − 1 ′ ′ κ ( l ) + κ ( l ) = κ ( l + l ) ∈ L , or that l + l ∈ κ ( L ) , and similarly with scalar M,N 1 M,N 2 M,N 1 2 1 2 M,N multiplication. − 1 ′ Now, notice that κ ( L ) is a submodule of M, so is finitely generated by m , m , . . . , m . 1 2 k M,N Consider the elements κ ( m ) , κ ( m ) , . . . , κ ( m ); we claim that these are generators of M,N 1 M,N 2 M,N k ′ ′ ′ L . For each element l ∈ L , since κ is surjective, there is some element l ∈ M such that M,N k P − 1 ′ ′ κ ( l ) = l , and furthermore l lies in κ ( L ) . Therefore, it is a linear combination r m for M,N i i M,N i =1 i = 1 , 2 , . . . , k. k P ′ ′ But then we have that l = r κ ( m ) . This proves that L is finitely generated. As this i M,N i i =1 holds for all submodules, we have that M/N is Noetherian. Problem 4.1.4. Prove the following.

1. Given a module M and a submodule N of M suppose that M ⊂ M are submodules such 1 2 that M ∩ N = M ∩ N and κ ( M ) = κ ( M ) . Show that M = M . 1 2 M,N 1 M,N 2 1 2
2. Using the above result, show that if N and M/N are Noetherian, then M is also Noetherian. Solution. 1. Suppose we are given two submodules of M, say M , M , such that M ⊂ M . If 1 2 1 2 M ∩ N = M ∩ N and κ ( M ) = κ ( M ) , we claim that M = M . 1 2 M,N 1 M,N 2 1 2 To prove this, suppose for the sake of contradiction that this was not the case, so there is ′ some m ∈ M so m ̸ ∈ M . Now, κ ( m ) ∈ κ ( M ) , so there is some m ∈ M such that 2 1 M,N M,N 1 1 ′ ′ ′ κ ( m ) = κ ( m ) . But this means that κ ( m − m ) = 0 , or that m − m ∈ N, since N is M,N M,N M,N the kernel of κ . M,N ′ ′ However, m ∈ M , m ∈ M means that m − m ∈ M ∩ N = M ∩ N, and therefore m = 2 2 2 1 ′ ′ m − m + m ∈ M , contradiction. Therefore, we have that M = M . 1 1 2
3. Suppose that N, M/N are Noetherian modules. Consider any chain M ⊂ M ⊂ . . . of 1 2 submodules of M. Consider the chains M ∩ N ⊂ M ∩ N ⊂ . . . and κ ( M ) ⊂ κ ( M ) ⊂ . . . . 1 2 M,N 1 M,N 2 ′ ′ ′ Note that for a submodule M of M that M ∩ N and κ ( M ) are submodules. For instance, M,N 26

′ ′ ′ m , m ∈ M ∩ N means that m , m ∈ M and N, and so therefore m + m ∈ M and N, so 1 2 1 2 1 2 ′ m + m ∈ M ∩ N. A similar argument holds for the other three properties we would need to check 1 2 to get the two submodules. By N, M/N Noetherian, it follows that there is an i such that j ≥ i implies that M ∩ N = 1 1 j M ∩ N, and an i so j ≥ i implies that κ ( M ) = κ ( M ) . Let i be the maximum of i , i , i 2 2 M,N j M,N i 1 2 1 2 and j ≥ i. Then, notice that M ⊂ M , and M ∩ N = M ∩ N = M ∩ N, and κ ( M ) = i j i i j M,N j 1 κ ( M ) = κ ( M ) , so hence by our above claim we have that M = M . This holds for all M,N i M,N i j i 2 chains of submodules of M, meaning that M is Noetherian, which is what we wanted to show. Problem 4.1.5. Let R be a Noetherian ring, and let M be a module over R.

1. Show that if M is Noetherian, then M is finitely generated.

2. Show that R is an Noetherian R − module (hint: what are submodules of R ?) n m n − m m

3. Show that R /R is isomorphic to R , for positive integers n ≥ m, where we embed R n into R as the elements where the last m − n coordinates are zero. n

4. Using the previous part, show that R is a Noetherian R − module for every positive integer n.

5. Show therefore that if M is finitely generated, then M is a Noetherian R − module. Solution. 1. We know that M is Noetherian if and only if all of the submodules are finitely generated. But then M in particular is also finitely generated.

6. It is enough to show that all submodules M of R are finitely generated over R. However, notice that M is an ideal, since M is closed under addition and multiplication by elements of R. Therefore, since R is Noetherian, every ideal is finitely generated, so in particular M is finitely generated as an ideal. Say its generators are m , m , . . . , m . Notice, however, that every element 1 2 k m ∈ M can be written as a linear combination of the elements m , m , . . . , m , which in particular 1 2 k means that these k elements generate M as a module, so M is finitely generated as an R − module. Thus, we have that R is a Noetherian R − module, which is what we wanted to show. n m

7. Let the free basis for R be e , e , . . . , e , and R have free basis generated by the first m 1 2 n n − m elements. Say that R has a free basis generated by v , v , . . . , v . Consider the linear map 1 2 n − m n n − m P P n n − m ϕ : R → R by ϕ ( a e ) = a v . Notice that this is a well-defined homomorphism, and i i m + i i i =1 i =1 furthermore the kernel consists precisely of the elements where a , a , . . . , a are zero, which is m +1 m +2 n m n − m just R . Furthermore, this is surjective, since any element of R is generated by v , v , . . . , v . 1 2 n − m n m n − m Therefore, R /R is isomorphic to the image of ϕ, which is R . This is what we wanted to show. n

8. We prove that R is a Noetherian R − module by induction on n. The base case, n = 1 , is given by induction. k +1 k Now, suppose that this has been shown for n ≤ k. Then, consider R ; we know that R (the subspace, say, where the last coordinate is zero) is Noetherian by our inductive hypothesis. k +1 k Meanwhile, by the previous part, we have that R /R ≃ R is also Noetherian. Therefore, by the k +1 previous problem, it follows that R is Noetherian. This finishes the inductive step, and therefore proves the claim. 27

9. Suppose that M is finitely generated, generated by m , m , . . . , m . Then, consider the map 1 2 n n n P P n ϕ from R to M by a e to a m . This can be quickly checked, in the same manner as the i i i i i =1 i =1 previous problems, to be a surjective homomorphism. n n Therefore, it follows that R / ker ϕ is isomorphic to M. However, notice that R is a Noetherian n module by the previous part, and ker ϕ is a submodule, meaning that R / ker ϕ is a Noetherian R − module. But then it follows that M is also a Noetherian R − module (using this isomorphism, if − 1 n N is a submodule of M, then ϕ ( N ) is a submodule of R / ker ϕ and is finitely generated, so N is finitely generated too by the images under ϕ of these finite generators). This is what we wanted to show. 4.2 Smith Normal Form Problem 4.2.1. Suppose that we multiply A on the right by an m × m invertible matrix S to get ′ ′ the matrix A . Show that N ( A ) = N ( A ) . (Hint: show that an element on the left-hand side lies on the right-hand side. Use invertibility). ′ ′ Solution. Suppose that A = AS, where S is an invertible m × m matrix. We show that N ( A ) ⊂ ′ − 1 N ( A ) . This is enough, since applying this argument with the equality A = A S will give us the ′ other inclusion, which will finish the proof of the above statement. Suppose the ( i, j )th entry of A ′ is a , the ( i, j )th entry of A is a , and the ( i, j )th entry is s . i,j i,j i,j ′ Suppose we are given some vector v ∈ N ( A ) . Then, we know that v can be written as m n P P ′ b a e , where the b lie in R. However, from the definition of matrix multiplication, we j i j i,j j =1 i =1 m P ′ have that a = a s . Substituting this into the above expression for v yields the following i,k k,j i,j k =1 expression: m n m X X X b a s e . j i,k k,j i j =1 i =1 k =1 But this in turn is equal to m m n X X X b s a e , j k,j i,k i k =1 j =1 i =1 n P which lies in the submodule generated by a e for k = 1 , 2 , . . . , m. Therefore, v ∈ N ( A ) , and i,k i i =1 we are done. Problem 4.2.2. Suppose that we multiply A on the left by an n × n invertible matrix S to get ′ n n ′ the matrix A . Show that R /N ( A ) and R /N ( A ) are isomorphic. (Hint: what is an isomorphism between the two modules?) ′ ′ Solution. Suppose the ( i, j )th entry of A is a , the ( i, j )th entry of A is a , and the ( i, j )th entry i,j i,j   v 1   n v 2 P   is s . We identify the element v = v e with column vector , which by the same logic as   . i,j i i .   i =1 . v n in the case of vector spaces is a module isomorphism. 28

n n ′ Consider the module homomorphism from R onto R /N ( A ) given by first sending the element   v 1   v 2   v = to Sv, before applying the quotient map κ n ′ . Note that this map is surjective.   . R ,N ( A ) .   . v n n ′ n n ′ To see this, for each w ∈ R /N ( A ) , since κ is surjective, there is some w ∈ R so w = R ,N ( A ) − 1 n ′ κ ( w ) . From here, note that S is invertible, and so S w is well-defined, and satisfies that R ,N ( A ) − 1 n ′ n ′ κ ( S ( S w )) = κ ( w ) = w. R ,N ( A ) R ,N ( A ) n ′ From here, we consider the kernel of this map. Note that κ ( Sv ) = 0 holds if and only R ,N ( A ) ′ if Sv ∈ N ( A ) , from the computation of the kernel of the κ map in Problem 3.0.3. However, by m n P P ′ ′ definition, N ( A ) consists of the vectors of the form b a e ; in other words, the vectors j i i,j j =1 i =1   b 1   b 2   ′ ′ of the form A b for some vector b = . However, Sv = A b for some b holds if and only if,   . .   . b m − 1 ′ multiplying by the inverse of S, v = S A b = Ab for some vector b, which in turn holds if and only if v ∈ N ( A ) . Therefore, the kernel of this combined map is N ( A ) , and as it is surjective, it follows that this n n ′ map is an isomorphism from R /N ( A ) to R /N ( A ) , which is what we wanted to show. Problem 4.2.3. As a first step, we want to reduce a column down to having a single nonzero entry in it, using row operations. r 1

1. Suppose we have a matrix , where r , r ̸ = 0 . Show there exists a 2 × 2 invertible matrix 1 2 r 2 r r 1 S such that S = for some element r ∈ R. How is r related to r , r , . . . , r ? 1 2 n r 0 2   r 1   r 2  
2. Suppose now we have a matrix , where not all the r are zero. Show that there exists   . i .   . r n     r r 1     r 0 2     an n × n invertible matrix S such that S = , for some r ∈ R. How is r related to     . . . .     . . r 0 n r , r , . . . , r ? 1 2 n
3. Given an n × m matrix A, for n, m ≥ 0 , show that there exists an n × n invertible matrix S and an m × m invertible matrix T so that SAT has no nonzero entries in the first row or first column, except for the (1 , 1) entry. (Hint: suppose that the (1 , 1) entry doesn’t divide every entry in the first row or first column. Apply part b). Repeat, and utilize the fact that R is a PID, ergo Noetherian.) 29

Solution. 1. Since R is a PID, the ideal ⟨ r , r ⟩ is equal to the ideal ⟨ r ⟩ . Then, it follows that 1 2 s s 1 2 there exist elements s , s such that s r + s r = r. We claim that the matrix is 1 2 1 1 2 2 r /r − r /r 2 1 an invertible matrix in R. To see this, first note that, since ⟨ r , r ⟩ = ⟨ r ⟩ , it follows that r , r are 1 2 1 2 divisible by r, so this matrix has entries in R. r /r s s s r 1 2 1 2 1 Furthermore, note that this matrix has inverse . Finally, notice that = r /r − s r /r − r /r r 2 1 2 1 2 r , which is what we wanted to show. 0 2. We proceed by induction on n, showing that r is such that ⟨ r ⟩ = ⟨ r , r , . . . , r ⟩ . 1 2 n The base case is n = 2 , where we have shown that this holds by the previous part. Suppose that   r 1   r 2   we have shown this now for n ≤ k − 1 , and consider the vector . If r is zero, then the   . n .   . r n inductive hypothesis lets us conclude that there exists some invertible n − 1 × n − 1 matrix S such     r r 1     r 0 2     that S = , and     . . . .     . . r 0 n − 1 r = ⟨ r , r , . . . , r ⟩ = ⟨ r , r , . . . , r , r ⟩ . 1 2 n − 1 1 2 n − 1 n If the entries of S are s , whose inverse T has entries t then the matrix ij ij   s s · · · s 0 11 12 1( n − 1)   s s · · · s 0 21 22 2( n − 1)     . . . ′ . . . . . S = ,   . . . . 0     s s · · · s 0 ( n − 1)1 ( n − 1)2 ( n − 1)( n − 1) 0 0 · · · 0 1 S 0 which we can denote as , is also invertible, with inverse 0 1   t t · · · t 0 11 12 1( n − 1)   t t · · · t 0 21 22 2( n − 1)   T 0   . . . . . . . .

  . . . . 0 0 1     t t · · · t 0 ( n − 1)1 ( n − 1)2 ( n − 1)( n − 1) 0 0 · · · 0 1     r r 1     r 0 2         . . ′ . . and S = .     . .         r 0 n − 1 r 0 n 30

Otherwise, note that there exists an invertible 2 × 2 matrix S, with entries s , such that ij r r n − 1 S = , where ⟨ r ⟩ = ⟨ r , r ⟩ . Furthermore, considering the n × n matrix n − 1 n r 0 n   1 0 · · · 0 0 0   0 1 · · · 0 0 0     . . . . . . . .   . . . . 0 ,     0 0 · · · 1 0 0     0 · · · 0 0 s s 11 12 0 0 · · · 0 s s 21 22     r r 1 1     r r 2 2         r r 3 3     note this sends to , where by the inductive hypothesis and our argument above     . . . .     . .         r r n − 1 r 0 n   ′ r   0     ′ 0 we can apply another invertible n × n matrix such that we get the vector , where ⟨ r ⟩ =     . .   . 0 ⟨ r , r , . . . , r , r ⟩ , and ⟨ r ⟩ = ⟨ r , r ⟩ . Note that ⟨ r , r , . . . , r ⟩ ⊂ ⟨ r , r , . . . , r , r ⟩ (since 1 2 n − 2 n − 1 n 1 2 n 1 2 n − 2 ′ ′ r , r lie in the latter), which in turn lies in ⟨ r ⟩ , and furthermore ⟨ r ⟩ = ⟨ r , r , . . . , r , r ⟩ ⊂ n − 1 n − 2 1 2 n − 2 ⟨ r , r , . . . , r , r , r ⟩ (since r lies in the latter), showing that these two ideals are equal. 1 2 n − 2 n − 1 n − 2 This finishes the inductive step and hence proves the claim. 3. Suppose we are given an n × m matrix A. Suppose that either the first column or first row are not entirely zero (if they are entirely zero, we are done). Without loss of generality, suppose that the first column is not entirely zero. By part 2, there exists an invertible matrix S such that SA only has one nonzero entry in the first column, and it is in the (1 , 1) entry. Say this (1 , 1) entry is a . 1 Suppose that the first row has more than one nonzero entry, and that some nonzero entry is not divisible by a . Then, by the same argument as in parts 1 and 2, there exists some m × m matrix 1 T such that ( SA ) T has no nonzero entry in the first row, other than the (1 , 1) entry. Notice that from part 2 that the new (1 , 1) entry a divides a , since ⟨ a ⟩ contains a . Furthermore, since some 2 1 2 1 entry in row 1 is not divisible by a , we have that ⟨ a ⟩ is strictly larger than ⟨ a ⟩ . 1 2 1 If the first column has a nonzero entry not divisible by a , we can repeat, finding an invertible 2 ′ ′ matrix S such that S SAT has no nonzero entries in the first column other than the (1 , 1) entry, which is a , which divides a . We then repeat this, alternating between rows and columns. 3 2 Suppose this procedure does not terminate. We then get a strictly increasing sequence of ideals, which is a contradiction of the fact that R is a PID, ergo a Noetherian ring. Thus, at some point, we arrive at a point where every entry in the first row and column is divisible by the (1 , 1) entry. The invertible row operations of adding some multiple of the first row/column to each other row/column, respectively, then give us our desired form for the matrix. Problem 4.2.4. Show that, given an n × m matrix A, there exists an n × n invertible matrix S 31

and an m × m invertible matrix T such that the nonzero entries of SAT lie on the diagonal (so a ̸ = 0 implies that i = j ). i,j Solution. We induct on the minimum of m, n. The base case, when min { m, n } = 1 , is given to us by Problem 53. Suppose we have shown this for all matrices A that are m × n where min { m, n } ≤ k. Suppose that min { m, n } = k + 1 . Then, by the previous problem, there exist invertible matrices S, T such that SAT has no nonzero entries in the first row or first column, other than the (1 , 1) entry. In particular, we know that SAT has the following form:   ′ a 0 0 . . . 0 1 , 1 ′ ′ ′   0 a a . . . a 2 , 2 2 , 3 2 ,m   ′ ′ ′   0 a a . . . a 3 , 2 3 , 3 3 ,m .     . . . . . . . . . .   . . . . . ′ ′ ′ 0 a a . . . a n, 2 n, 3 n,m ′ ′ ′ Now, we know that there exist matrices S , T , by the inductive hypothesis, such that if A is the matrix   ′ ′ ′ a a . . . a 2 , 2 2 , 3 2 ,m ′ ′ ′   a a . . . a 3 , 2 3 , 3 3 ,m   .   . . . . . . . .   . . . . ′ ′ ′ a a . . . a n, 2 n, 3 n,m 1 0 1 0 ′′ ′′ ′′ ′′ So then the matrices S = and T = are such that S SAT T has its nonzero ′ ′ 0 S 0 T ′′ ′′ entries only along the diagonal, and we know that S S and T T are invertible matrices. This finishes the inductive step and hence proves the claim. Problem 4.2.5. Show that we can further reduce the matrix so that the nonzero entries are a , a , . . . , a for some positive integer 1 ≤ k ≤ m, and so that a divides a for i = 1 , 1 2 , 2 k,k i,i i − 1 ,i − 1 2 , 3 , . . . , k. This is known as Smith normal form. Solution. By the previous problem, along with swapping rows and columns appropriately, we can reduce our matrix to the form such that the only nonzero entries are on the diagonal, and these are a , a , . . . , a . 1 , 1 2 , 2 k,k Given i and j, suppose that ⟨ a , a ⟩ = ⟨ d ⟩ , and say s , s are such that s a + s a = d. i,i j,j 1 2 1 i,i 2 j,j Then, consider the following operations.

1. Swap rows i and j.
2. Add s times row j to row i. 1
3. Add s times column j to column i. 2
4. Subtract a /d times row i from row j. i,i
5. Subtract a /d times column i from column j. j,j 32

Notice that this only affects the ( i, j )th, ( j, i )th, ( i, i )th, and ( j, j )th entries, since all the other entries in either row i or column j are zero and remain zero at each step of the process (as either the swapping nor the addition operations change this fact, since by assumption the only nonzero entries at the beginning are along the diagonal). We can then just analyze what this does to these four entries, giving us the following table. Now, run the following procedure: apply this ( i, i )th entry ( i, j )th entry ( j, i )th entry ( j, j )th entry After Step 1 0 a a 0 j,j i,i After Step 2 s a a a 0 1 i,i j,j i,i After Step 3 d a a 0 j,j i,i After Step 4 d a 0 − a /d j,j i,i After Step 5 d 0 0 − a /d i,i above subprocedure first with i = k, and j = k − 1 , k − 2 , . . . , 1 . Notice that after each one of these steps, we make the ( k, k )th entry a divisor of the ( j, j )th entry and the previous ( k, k )th entry. But by induction, we can see that this new entry will be divisible by the ( l, l )th entry for l = j + 1 , j + 2 , . . . k − 1 . Hence, after running all of these, we see that the ( k, k )th entry divides the ′ ( j, j )th entry for j < k. Say this entry is a . k,k Run this procedure now with i = k − 1 , and j = k − 2 , k − 3 , . . . 1 . Notice that at each step that the new ( k − 1 , k − 1)st entry of the matrix will be divisible by the ( k, k )th entry, since from our above procedure this entry lies in the ideal generated by the old diagonal entries (which, in ′ particular, by our above observations, lies in ⟨ a ⟩ ), and furthermore by the same argument as the k,k above the ( k − 1 , k − 1)st entry, after running the procedure on k − 2 , k − 3 , . . . , j, divides the new ( l, l )th entry for l = j, j + 1 , . . . , k − 2 . So after running all of these, if we end up with the entry ′ ′ ′ a in the ( k − 1 , k − 1) entry, then a divides a , and this entry divides all of the k − 1 ,k − 1 k,k k − 1 ,k − 1 other entries. Repeating this for i = k − 2 , k − 3 , . . . , 2 eventually yields our desired form for the matrix. 4.3 Proof of the Theorem Problem 4.3.1. Show that there exists a surjective map ϕ from a free module F of finite rank to M. Solution. Since M is finitely generated, there exists a finite set of generators m , m , . . . , m . Then, 1 2 k k P k consider the map ϕ : R → M by sending ( r , r , . . . , r ) to r m . Note that this map can be 1 2 k i i i =1 checked to be linear. Furthermore, since m , m , . . . , m are a generating set for M, each element of M can be written 1 2 k k P k as a m for some a ∈ R. But then ( a , a , . . . , a ) ∈ R , under ϕ, gets sent to m ∈ M. i i i 1 2 k i =1 Problem 4.3.2. Show that ker ϕ is finitely generated. k Solution. Since R is a PID, it is Noetherian by Problem 4.1.1. But then R is a finitely generated module over a Noetherian ring, and therefore is a Noetherian module by Problem 4.1.5. Therefore, the submodule ker ϕ is Noetherian by Problem 4.1.2. 33

Problem 4.3.3. Suppose that the only nonzero entries of A are along the diagonal (that is, a ̸ = 0 i,j implies that i = j ). Show that M is then isomorphic to a module of the form k M r R ⊕ R/ ⟨ d ⟩ , i i =1 and describe how you obtain the values d and r. i n Solution. Suppose that e , e , . . . , e are the standard basis for R ; that is e is the tuple with the 1 2 n i only nonzero entry being a 1 in the i th coordinate. Then, since A only has nonzero entries along the diagonal, it follows that the kernel of ϕ is generated by a e , a e , . . . , a e . Let d = a . 1 , 1 1 2 , 2 2 m,m m i i,i L m n n − m Consider the map ψ : R → ( R/ ⟨ d ⟩ ) ⊕ R by sending the tuple ( r , r , . . . , r ) to i 1 2 n i =1 ( r , r , . . . , r , r , r , . . . , r ) , where r is the image of r under the quotient map R → R/ ⟨ d ⟩ . 1 2 m m +1 m +2 n i i i One can quickly verify that this is a surjective homomorphism: indeed, given ( r , r , . . . , r ) and 1 2 n ′ ′ ′ n ( r , r , . . . , r ) ∈ R , we have 1 2 n ′ ′ ′ ′ ′ ′ ′ ′ ψ (( r , r , . . . , r ) + ( r , r , . . . , r )) = ( r + r , r + r , . . . , r + r , r + r , . . . , r + r ) , 1 2 n 1 2 m m +1 n 1 2 n 1 2 m m +1 n which is equal to ′ ′ ′ ′ ′ ′ ′ ′ ( r , r , . . . , r , r , . . . , r )+( r , r , . . . , r , r , . . . , r ) = ψ (( r , r , . . . , r ))+ ψ (( r , r , . . . , r )) , 1 2 m m +1 n 1 2 n m m +1 n 1 2 n 1 2 and similarly for any r ∈ R, we have ψ ( r ( r , r , . . . , r )) = ( rr , rr , . . . , rr , rr , . . . , rr ) = rψ (( r , r , . . . , r )) . 1 2 n 1 2 m m +1 n 1 2 n L m n − m For surjectivity, given ( r , r , . . . , r , r , r , . . . , r ) ∈ ( R/ ⟨ d ⟩ ) ⊕ R , there exist r 1 2 m m +1 m +2 n i i i =1 for i = 1 , 2 , . . . , m so the image of r in R/ ⟨ d ⟩ is r , so then ( r , r , . . . , r ) maps to our above tuple. i i i 1 2 n Notice that the kernel of this homomorphism is precisely the set of tuples ( r , r , . . . , r ) where 1 2 n r ∈ ⟨ d ⟩ for i = 1 , 2 , . . . , m, and are 0 for the others. However, such tuples are precisely those i i m P of the form a d e , which is precisely the kernel of ϕ, as noted above. Therefore, we have the i i i i =1 isomorphisms ! m M n − m n n R/ ⟨ d ⟩ ⊕ R ≃ R / ker ψ = R / ker ϕ ≃ M. i i =1 Finally, noting that R/ ⟨ 0 ⟩ ≃ R (since the identity map on R has kernel 0 and is surjective) and that L k r ′ the map permuting the tuples is an isomorphism, it follows that M ≃ R ⊕ R/ ⟨ d ⟩ , where i i =1 ′ k is the number of nonzero d , the d are precisely the nonzero diagonal entries in A (with some i i ordering), and r = n − k. Problem 4.3.4. Prove Theorem 4.0.1, and show that a choice of d can be made such that the d i i are all powers of prime elements. Solution. Suppose that M is a finitely generated R -module. We know there exists a module ho- n momorphism ϕ : R → M which is surjective. Consider ker ϕ, which is finitely generated by some w , w , . . . , w . Using the above construction, we know that ker ϕ is equal to N ( A ) for some n × m 1 2 m matrix A, and thus R/N ( A ) ≃ M. 34

However, by Problem 4.2.5, there exist invertible matrices S, T such that SAT is a matrix n whose nonzero entries lie on the diagonal, and by the previous problem we know that R /N ( SAT ) takes the form given in Theorem 4.0.1. However, by Problems 4.2.1 and 4.2.2, we know that L k r M ≃ R/N ( A ) ≃ R/N ( SA ) ≃ R/N ( SAT ) ≃ M ≃ R ⊕ R/ ⟨ d ⟩ . This proves the theorem. i i =1 To show that all the d can be made into powers of prime elements, recall from Theorem 1.2.7 that i e e e 1 2 l PIDs are UFDs, so we have unique factorization of d into prime powers, say by d = p p . . . p , i i 1 2 l where the p are prime elements that are pairwise not multiples of each other by units. Now, we i e e e j e j i i wish to apply Problem 1.3.3. We consider ⟨ p ⟩ + ⟨ p ⟩ = ⟨ p , p ⟩ . Say this is ⟨ d ⟩ , so d divides i j i j e e j i both p and p . However, by uniqueness of factorization, this requires that d be a unit, since the i j first divisibility condition requires that the only primes in d ’s factorization are unit multiples of p , i and the second requires that the only primes in d ’s factorization are unit multiples of p . j e e e e j e j e j i i i Thus, ⟨ p ⟩ + ⟨ p ⟩ = ⟨ p , p ⟩ = R. Furthermore, note that ⟨ p ⟩∩⟨ p ⟩ = ⟨ p p ⟩ . The right-hand i j i j i j i j e e j i side lies in the left-hand side, since any multiple of p p is a multiple of each of the prime powers. i j e e j i As for the other direction, since we are working in a PID (ergo, a UFD), x being divisible by p , p i j e e j i means that the unique factorization of x contains p and p in this factorization. But then x is i j L e l e e j j i divisible by p p . Thus, by Problem 1.3.3, we know that R/ ⟨ d ⟩ ≃ R/ ⟨ p ⟩ . Applying this i i j i =1 j for each d (and noting that if d is a unit, R/ ⟨ d ⟩ is equal to R/ ⟨ 1 ⟩ , with 1 a power of a prime) i i i thus gives us a form where each diagonal entry is a power of a prime. 5 Applications and Asides 5.1 A Counterexample √ Problem 5.1.1. Find a Z [ − 5] − module that is not isomorphic to a module of the form k M r R ⊕ R/ ⟨ d ⟩ , i i =1 √ where R = Z [ − 5] . √ Solution. We claim that I = ⟨ 2 , 1 + − 5 ⟩ is not isomorphic to any module of the above form. L k r To see this, suppose that there existed such an isomorphism ϕ : R ⊕ R/ ⟨ d ⟩ → I to some i i =1 module of the above form. First, suppose that k ≥ 1 , and one of the d is not a unit. Let d be i one such element. Then, we know that R/ ⟨ d ⟩ consists of elements such that, when multiplied by d, they become zero. Say m is one such nonzero element. Then, dm = 0 , so ϕ ( dm ) = dϕ ( m ) = 0 . √ Thus, ϕ ( m ) is nonzero and vanishes upon multiplication by d. But Z [ − 5] is a domain, so this is impossible. Hence, the only d are units. Suppose that r ≥ 2 . Then, there exist two linearly independent i L k r elements s , s in R ⊕ R/ ⟨ d ⟩ (namely, taking the tuple with a 1 only in the first coordinate, 1 2 i i =1 and the tuple with only a 1 in the second coordinate). Note, however, that ϕ ( s ) , ϕ ( s ) must 1 2 be also linearly independent, as r ϕ ( s ) + r ϕ ( s ) = 0 implies that ϕ ( r s + r s ) = 0 , or that 1 1 2 2 1 1 2 2 r s + r s = 0 , or that r , r are zero. But ϕ ( s ) ϕ ( s ) − ϕ ( s ) ϕ ( s ) = 0 , and ϕ ( s ) , ϕ ( s ) are 1 1 2 2 1 2 2 1 1 2 1 2 nonzero, so this is impossible. k L Thus, we would need I to be isomorphic to a module of the form R ⊕ R/ ⟨ u ⟩ , where the u i i i =1 35

are units. But note that this is isomorphic to R, since R/ ⟨ u ⟩ are all isomorphic to 0 , and we have i k L the isomorphism from R ⊕ R/ ⟨ u ⟩ to R sending ( r, 0 , 0 , . . . , 0) to r ∈ R. i i =1 This would thus require that I ≃ R. But then I is generated by ϕ (1) . But this is impossible: ϕ (1) √ √ √ would divide both 2 and 1 + − 5 , meaning that if ϕ (1) = a + b − 5 , then there exists c + d − 5 ∈ √ √ √ √ √ Z [ − 5] such that ( a + b − 5)( c + d − 5) = 2 . But then note that ( a + b − 5)( c + d − 5)( a − √ √ √ √ √ 2 2 2 2 b − 5)( c − d − 5) = ( a +5 b )( c +5 d ) = 4 , as ( a − b − 5)( c − d − 5) = ac − 5 bd − ( ad + bc ) − 5 = 2 . But this is only possible when a = 1 , c = 2 , or a = 2 , c = 1 (with the rest 0). And as 2 does not √ divide 1 + − 5 , it follows that a = 1 , so ϕ (1) = 1 . But 1 ̸ ∈ I, as one can quickly check. Thus, I cannot be isomorphic to any module of the above form, which is what we wanted to show. 5.2 Abelian Groups Problem 5.2.1. Consider the group Z / 8 Z . How many elements are there of each order? What if you replace 8 with any positive integer n ? Solution. For Z / 8 Z , we can check each element’s order: we have the elements represented by 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 . We note that any odd integer will have order 8 : indeed, if x is odd, then for nx ≡ 0 (mod 8) , or 8 to divide nx, we need n to be divisible by 8 , and furthermore this is sufficent. Thus, there are 4 elements of order 8 . Similarly, if an element x is divisible by 2 but not 4 , then nx ≡ 0 (mod 8) implies that 8 | nx, or that 4 | n, so two elements have order 4 . Finally, 0 has order 1 and 4 has order 2 , so we have 1 element of order 1 , 1 of order 2 , 2 of order 4 , and 4 of order 8 . In general, suppose we have Z /n Z . Consider the order of an element x ∈ Z /n Z . We have that n n divides dx if and only if divides d. Furthermore, the order is equal to d precisely if gcd( n,x ) n = d. Thus, for any d not dividing n, there are no elements of order d. Meanwhile, for gcd( n,x ) d | n, note that we are looking at the set of elements x ∈ { 1 , 2 , . . . , n } so gcd( n, x ) = n/d, or that gcd( d, dx/n ) = 1 , and x is divisible by n/d. So this set is in bijection with the integers in { 1 , 2 , . . . , d } that are relatively prime to d. But this is just φ ( d ) , where φ is the Euler totient function. Therefore, there are φ ( d ) elements of order d in Z /n Z . Problem 5.2.2. Show that Z /n Z is cyclic for every positive integer n. Solution. We show that Z /n Z is generated by the element 1 . Indeed, notice that any element m ∈ Z /n Z , by definition, is equal to the residue of m modulo n. We can, by adding more n s to m, assume that m > 0 . However, notice that m is equal to 1 + 1 + · · · + 1 , where we have m 1s. Therefore, m is equal to the sum of m 1s. But this can be done for each m ∈ Z /n Z , meaning that 1 generates Z /n Z , which is what we wanted to show. Problem 5.2.3. Show that Z [ x ] , the set of polynomials with coefficients in Z , is not a finitely generated abelian group under addition. (Hint: suppose you had a finite subset of Z [ x ] . What elements can be written as a sum of these elements?) Solution. We suppose for the sake of contradiction that Z [ x ] was a finitely generated abelian group under addition. Then, we have some set { f , f , . . . , f } of generators for Z [ x ] as an abelian group. 1 2 k But note that the sum of any of these polynomials is going to have degree at most the maximum of the degrees of the f . Indeed, given any polynomials f, g, if both of their degrees are at most n, i then f + g also has degree at most n, and similarly for f − g. 36

N +1 Let N be the maximum of the degrees of the f , and consider x . For Z [ x ] to be generated i N +1 by f , f , . . . , f , we need for x = g + g + . . . + g , where each g is either one of the f or the 1 2 k 1 2 m i i additive inverse of an f . But the right-hand side is a polynomial of degree at most N, which is a i contradiction. Thus, Z [ x ] cannot be a finitely generated abelian group, which is what we wanted to show. Problem 5.2.4. Show that every abelian group is a Z − module, where one of the operations is + . What is the scalar multiplication? Solution. Let G be an abelian group. We claim that this is a Z − module with scalar multiplication given by n · g = g + g + · · · + g, with n g s, if n > 0 , and n · g = − g + ( − g ) + · · · + ( − g ) , with − g the additive inverse of g and there being − n ( − g )s. Finally, we let 0 · g = 0 . We check the properties of being a Z − module. Properties 1, 3, 4, 5 follow from the fact that G is an abelian group, and the associativity of + also follows. For property 6 , this follows by definition of our module structure, since 1 · g = g. For the associativity of · , we first note that ( − n ) · g = − 1 · ( n · g ) = n · ( − 1 · g ) if n > 0 . Indeed, note that ( − n ) · g is equal to − g + ( − g ) + · · · + ( − g ) , where there are n − g s. Meanwhile, the right-hand side is equal to the additive inverse of n · g = g + g + · · · + g. However, ( n · g ) + ( − n · g ) = g + g + · · · + g + ( − g ) + ( − g ) + · · · + ( − g ) , where there are n g s and n ( − g )s. Each of these cancel out, and so ( n · g ) = ( − 1) · ( n · g ) . Finally, by definition, ( − n ) · g is equal to n · ( − 1 · g ) , which is the sum of n − 1 · g = ( − g )s. From here, note that for n = 0 that both sides are equal to 0 , and for n < 0 , we have that ( − 1) · (( − 1) · (( − n ) · g )) is equal to ( − n ) · g (since the two ( − 1)s corresponding to taking additive inverse and then applying additive inverse again, which cancel each other out). Thus, by the n > 0 case, this is also equal to ( − 1) · ( n · g ) , which is what we wanted. Again, note that ( − n ) · g is the sum of − n g s, which is also what n · ( − 1 · g ) is, as the additive inverse of the additive inverse of g is g. From here, given m, n ∈ Z , let s , s be the sign of m, n, respectively. Then, note that m · m n ( n · g ) = s · ( | m | · ( s · ( | n | · g ))) . But by the above, this is equal to s · ( s · ( | m | · ( | n | · g ))) . m n m n Furthermore, | m | · ( | n | · g ) is just the sum of | mn | g s (by having | m | sums of | n | g s), so this equals s · ( s · ( | mn | · g )) = s s | mn | · g = mn · g. This proves associativity, and hence property 2. m n m n For property 7, we note that ( − 1) · ( g + g ) is the additive inverse of g + g . But this is then equal 1 2 1 2 to ( − g ) + ( − g ) , since if the additive inverse is e, then e = e + g + g + ( − g ) + ( − g ) = − g + − g . 1 2 1 2 1 2 1 2 From here, we note that if s is the sign of n, then n · ( g + g ) = s · ( | n | · ( g + g )) = s · ( | n | · n 1 2 n 1 2 n g + | n | · g ) = n · g + n · g . 1 2 1 2 Furthermore, given m, n, we note that if both m, n are positive, then ( m + n ) · g = m · g + n · g, and the above argument also covers the case if m, n are both negative (by factoring out the − 1 first). If m + n > 0 but one of them is nonpositive, suppose without loss of generality that m > 0 , n ≤ 0 . Then, ( m + n ) · g is equal to the sum of m + n g s. But this is equal to m g s plus | n | ( − g )s, or m − | n | g s. The above observation, giving the distributivity of ( − 1) , gives us the case for when m + n < 0 as well, which proves property 7 and thus shows that G can be given a Z − module structure with this notion of scalar multiplication. Problem 5.2.5. Suppose that G is a finitely generated abelian group. Show that G is isomorphic (as groups) as n M r Z ⊕ Z /d Z , i i =1 37

for some positive integers d , d , . . . , d and nonnegative integers r, n. 1 2 r Solution. Given such a finitely generated abelian group G generated by { g , g , . . . , g } , recall from 1 2 k the previous problem that G can then be given the structure of a Z -module. Since Z is a PID, and G is a finitely generated Z -module as well (noting that the generators g , g , . . . , g also generate 1 2 k G as a Z -module). Therefore, by the PID structure theorem, it follows that G is isomorphic, as Z -modules, to n M r Z ⊕ Z /d Z , i i =1 for some positive integers d , d , . . . , d and nonnegative integers r, n. Let ϕ be this isomorphism. 1 2 r But this isomorphism, in particular, satisfies ϕ ( g + g ) = ϕ ( g ) + ϕ ( g ) , since ϕ is a module 1 2 1 2 homomorphism. Therefore, ϕ is also a group homomorphism, and as it is bijective, it follows that ϕ is an isomorphism of abelian groups. This proves the theorem. 5.3 Jordan Canonical Form n P i Problem 5.3.1. Show that V is a C [ x ] − module, where for a polynomial p ( x ) = a x we define i i =0 n P i p ( x ) · v = a T v for each v ∈ V. i i =0 Solution. We check through the properties of a module. Again, we know that, since V is a vector space, properties 3, 4, 5 hold. Property 1 follows since T, by assumption, sends V to V, and so n n P P i i p ( x ) · v, for any p ∈ C [ x ] , is equal to a T v ∈ V. For property 2, suppose that p ( x ) = a x i i i =0 i =0 m P i and q ( x ) = b x . Then, i i =0 n m n X X X i j i q ( x ) · ( p ( x ) · v ) = q ( x ) · ( a T v ) = b T ( a T v ) . i j i i =0 j =0 i =0 m n P P i + j However, by linearity, this is equal to a b T v. However, note that this is equal to q ( x ) p ( x ) · i j j =0 i =0 v, meaning that property 2 follows. 0 0 For property 6, note that by definition that 1 · v = T v = v, since T is the identity. We finally check property 7: one direction of distributivity follows from the fact that T is linear. n m P P i i For the other direction, suppose we are given polynomials p ( x ) = a x and q ( x ) = b x . i i i =0 i =0 We can suppose that m = n. Then, note that n n n X X X i i i p ( x ) · v + q ( x ) · v = a T v + b T v = ( a + b ) T v. i i i i i =0 i =0 i =0 However, note that this equals ( p ( x ) + q ( x )) · v, giving us property 7. Therefore, V forms a C [ x ]- module with the given scalar multiplication, as desired. 38

Problem 5.3.2. Show that, as C [ x ] − modules and as vector spaces, V is isomorphic to n M r i C [ x ] / ( x − λ ) , i i =1 for some complex numbers λ , λ , . . . , λ and positive integers r , r , . . . , r . Again, you will need 1 2 n 1 2 n the Fundamental Theorem of Algebra (see Problem 1.1.5). Solution. First, by the PID Structure theorem, it follows that as C [ x ] modules that V is isomorphic to n M r r i C [ x ] ⊕ C [ x ] / ( p ( x )) , i =1 where p ( x ) are polynomials in C [ x ] . Furthermore, we know that by Problem 4.3.4 that such a choice can be made where the p ( x ) are prime elements. But the only such prime elements in C [ x ] , by Problem 1.1.5, are of the form x − λ. So we thus have that V is isomorphic to n M r r i C [ x ] ⊕ C [ x ] / ( x − λ ) i i =1 as C [ x ]-modules via the homomorphism ϕ , and in particular as vector spaces (since to be a vector space homomorphism, one must only check that ϕ ( ax + by ) = aϕ ( x ) + bϕ ( y ) for x, y ∈ V and a, b ∈ C , rather than C [ x ]). L n r r i Now, suppose that r ≥ 1 . Then, we know that V is isomorphic to C [ x ] ⊕ C [ x ] / ( x − λ ) i i =1 as vector spaces, and by assumption V is finite dimensional, say dimension k. Then, the right-hand 2 k +1 side must be as well. But if r ≥ 1 , then in particular we have that 1 , x, x , . . . , x (or rather, the tuples with these in the first coordinate and 0 in all others) are linearly independent over C , so the dimension of the right-hand side is more than k, contradiction. Hence, r = 0 , and so we require L n r i that V ≃ C [ x ] / ( x − λ ) , as desired. i i =1 Problem 5.3.3. Prove the following.

1. Show that for each λ there exists a set of vectors v , v , . . . , v ∈ V such that T v = λ v , i 1 2 r 1 i 1 i and for j = 2 , 3 , . . . , r , we have that T v = λ v + v , and that v , v , . . . , v are linearly i j i j j − 1 1 2 r i independent.
2. Show furthermore that these sets can be chosen such that, if we combine all of these sets together, the resulting set of vectors is also linearly independent.
3. Show that this set of vectors must therefore be a basis for V. r i Solution. 1. Consider the element 1 ∈ C [ x ] / ( x − λ ) ; for the sake of readability for this part we i drop the bars (and understand all the polynomials as residues). We furthermore treat each of these L n r i elements as the tuples in C [ x ] / ( x − λ ) where all other coordinates are zero. Notice that i i =1 r − 1 i r − 1 i 1 , ( x − λ ) , . . . , ( x − λ are linearly independent, since a + a ( x − λ ) + . . . + a ( x − λ ) = 0 i 0 1 i r − 1 i i i r − 1 i implies, by translating the polynomialm that a + a x + . . . + a x = 0 , or that all of the a are 0 1 r − 1 i i r − j r − 1 − 1 − 1 − 1 − 1 i i zero. Consider now the vector ϕ (1) , ϕ ( x − λ ) , . . . , ϕ ( x − λ ) . Let v = ϕ ( x − λ ) , for i j i i r − 1 i j = 1 , 2 , . . . , r . Then, note that ϕ (( T − λ ) v ) = ϕ (( x − λ ) · v ) = ( x − λ )( x − λ ) = 0 (working i i 1 i 1 i i 39

r i in C [ x ] / ( x − λ ) ). In other words, by ϕ being an isomorphism, we have that ( T − λ ) v = 0 , or i i 1 T v = λ v . Furthermore, we have that 1 i 1 r − j i ϕ (( T − λ ) v ) = ϕ (( x − λ ) · v ) = ( x − λ )( x − λ ) = ϕ ( v ) , i j i j i j j − 1 j or that T v = λ v + v . Finally, notice that the v are linearly independent, since the ( x − λ ) j i j j − 1 j i are too, proving this first part. 2. Let X be the collection of vectors that we chose corresponding to coordinate i in the direct i n L S n r i sum C [ x ] / ( x − λ ) . Then, notice that for any linear combination of vectors in X to be i i i =1 i =1 zero, the linear combination must be zero in each coordinate. But in coordinate i, the only vectors with nonzero coordinate are those in X , and these are presumed to be linearly independent. So i the coefficients on the vectors in X are zero, and this holds for each i. Thus, our choices can be i made such that the set of vectors is linearly independent. L n 3. To show that this is a basis for V, we argue that the corresponding elements in C [ x ] / ( x − i =1 r i λ ) are a basis (which is enough, since ϕ is a vector space isomorphism and thus preserves linear i combinations: so every vector v ∈ V being a linear combination of vectors v holds if and only each i vector in ϕ ( v ) is a linear combination of vectors ϕ ( v )). i L n r i Suppose we have a vector ( p , p , . . . , p ) ∈ C [ x ] / ( x − λ ) . Then, note that each p is 1 2 n i i i =1 r i equivalent modulo ( x − λ ) to some vector that is of degree at most r − 1 , by the normal polynomial i i division algorithm. So we may suppose that each p is degree at most r − 1 . Then, by repeatedly i i dividing quotients by x − λ , we find that we may write i 2 r − 1 r − 2 i i p ( x ) = q ( x )( x − λ )+ a = q ( x )( x − λ ) + a ( x − λ )+ a = . . . = a ( x − λ ) + a ( x − λ ) + · · · + a . i 1 i 0 2 i 1 i 0 r − 1 i r − 2 i 0 i i This gives us that ( p , p , . . . , p ) can be written as the linear combination 1 2 n a (1 , 0 , 0 , . . . , 0) + a ( x − λ , 0 , 0 , . . . , 0) + · · · + a (0 , 1 , 0 . . . , 0) 10 11 1 20 r − 1 n

• · · · + a (0 , 1 , 0 , . . . , 0) + · · · + a (0 , 0 , . . . , ( x − λ ) ) . n 0 n n ( r − 1) n n S But these are just the vectors in X . Hence, it follows that this set is linearly independent and i i =1 spanning, and therefore is a basis. Thus, it follows that the corresponding vectors in V (obtained n S − 1 by mapping each vector in X to V via ϕ ) form a basis for V, which is what we wanted to i i =1 show. Problem 5.3.4. Show that for any linear transformation T on a C − vector space V, there exists a basis v , v , . . . , v such that, with respect to this basis, T has block matrix form 1 2 n   J 0 · · · 0 1   0 J · · · 0 2   ,   . . . . . . . .   . . . . 0 0 · · · J k 40

where each of the J has the following form for some λ ∈ C : i i   λ 1 0 · · · 0 i   0 λ 1 · · · 0 i     0 0 λ · · · 0 i ,     . . . . . . . . . .   . . . . . 0 0 0 0 λ i with λ along the main diagonal and 1s along the diagonal immediately above it. This is known as i the Jordan canonical form for a linear transformation/matrix. Solution. Given a linear transformation T on a C -vector space, we know that V, as a C [ x ]-module, n L r i is isomorphic to C [ x ] / ( x − λ ) , for some λ , and from the previous problems we can find i i i =1 a basis v , v , . . . , v , v , . . . , v , . . . , v , . . . , v satisfying the properties above. Recall 1 , 1 1 , 2 1 ,r 2 , 1 2 ,r n, 1 n,r 1 2 n that, by construction, for each i, we have that T v = λ v and for j = 2 , 3 , . . . , r that T v = i, 1 i i, 1 i i,j λ v + v . In other words, the matrix of T with respect to this basis has the above block form, i i,j i,j − 1 where the block corresponding to v , v , . . . , v is given by i, 1 i, 2 i,r i   λ 1 0 · · · 0 i   0 λ 1 · · · 0 i     0 0 λ · · · 0 i .     . . . . . . . . . .   . . . . . 0 0 0 · · · λ i This is what we wanted to show. 6 Acknowledgements + Resources Thank you to Aleksa Milojevic, Nancy Xu, and Oliver Thakar for their feedback on drafts of the power round. For more information about the material in the power round, see Sheldon Axler’s Linear Algebra Done Right (Chapters 1-3) and Michael Artin’s Algebra (Chapters 11, 14). 41