PUMaC 2023 · 加试 · 第 53 题

PUMaC 2022* Power Round: The PID Structure Theorem Frank Lu Spring 2023 Rules and Reminders

1. Your solutions should be turned in by 12PM Thursday, March 30th, EDT . You will submit the solutions through Gradescope. The instructions describing how to log into Gradescope will be sent to the coaches. The deadline for submission is clearly visible on the Gradescope site once you enroll in the course. Please make sure you submit your work in time. No late submissions will be accepted. Please do not submit your work using email or in any other way. If you have questions about Gradescope, please post them on Piazza. A You may either typeset the solutions in L TEX or write them by hand. We strongly encourage you to typeset the solutions. This way, the proofs end up being more clear and the chances are you will not lose points there. Moreover, you might want to use A some of the L TEX resources listed in point 2. In case your solutions are handwritten, the cover sheet (the last page of this document) should be the first page of your submission. In case you typeset your solutions, please take a look at the Solutions Template we posted and make sure to make the cover sheet the first page of your submission. Each page should have on it the team number (not team name) and problem number . This number can be found by logging in to the coach portal and selecting the corresponding team. Solutions to problems may span multiple pages. Please put them in order when submitting your solutions. A

2. You are encouraged, but not required, to use L TEX to write your solutions. If you submit your power round electronically, you may submit several times, but only your final submission will be graded (moreover, you may not submit any work after the deadline). The last version of the power round solutions that we receive from your team will be graded. Moreover, you must submit a PDF . No other file type A will be graded. For those new and interested in L TEX, check out Overleaf as well as its online guides. If you do not know the specific command for a math symbol, check out Detexify or TeX.StackExchange.

3. Do not include identifying information aside from your team number in your solutions.

4. Please collate the solutions in order in your submission. Each problem should start on a new page (there is a point deduction for not following this formatting).

5. On any problem, you may use without proof any result that is stated earlier in the test, as well as any problem from earlier in the test, even if it is a problem that your team has not solved. These are the only results you may use. In particular, to solve a problem, you may not cite the subsequent ones. You may not cite parts of your proof of other problems: if you wish to use a lemma in multiple problems, please reproduce it in each one.

6. When a problem asks you to “find”, “find with proof,” “show,” “prove,” “demon- strate,” or “ascertain” a result, a formal proof is expected, in which you justify each step you take, either by using a method from earlier or by proving that everything you do is correct. When a problem instead uses the word “explain,” an informal expla- nation suffices. When a problem instead uses the word “sketch” or “draw” a clearly marked diagram is expected.

7. All problems are numbered as “Problem x.y.z” where x.y is the subsection number and z is the the number of the problem within the subsection. Each problem’s point distribution can be found in the cover sheet.

8. You may NOT use any references, such as books or electronic resources, unless otherwise specified. You may NOT use computer programs, calcu- lators, or any other computational aids.

9. Teams whose members use English as a foreign language may use dictionaries for reference.

10. Communication with humans outside your team of 8 students about the content of these problems is prohibited.

11. There are two places where you may ask questions about the test. The first is Piazza. Please ask your coach for instructions to access our Piazza forum. On Piazza, you may ask any question so long as it does not give away any part of your solution to any problem . If you ask a question on Piazza, all other teams will be able to see it. If such a question reveals all or part of your solution to a power round question, your team’s power round score will be penalized severely. For any questions you have that might reveal part of your solution, or if you are not sure if your question is appropriate for Piazza, please email us at pumac@math.princeton.edu. We will email coaches with important clarifications that are posted on Piazza.

Introduction and Advice In this power round, we state and prove the PID Structure Theorem , before de- scribing a few applications of this theorem. This theorem states that certain examples of a structure called a module satisfy nice properties. In order to state and prove the theorem, we first need to introduce a few more structures from abstract algebra. We first study rings, which are sets with addition and multiplication operations. This structure includes some familiar sets, such as the set of integers and the set of rational numbers. As we introduce new structures, we will slowly see, under certain conditions, that these structures satisfy nice properties. The material in this power round belongs to the field of abstract algebra, which studies sets equipped with operations that obey certain properties. A large part of the difficulty of this subject arises from the abstraction and the amount of generality present (in contrast with the computation-heavy and concrete world of high school algebra and geometry). Try to keep in mind the examples introduced throughout the power round, and checking the definitions and propositions against these examples. This will be useful in understanding what each of these otherwise abstract statements are saying. Here is some further advice with regard to the Power Round: • Read the text of every problem! Many important ideas are included in problems and may be referenced later on. In addition, some of the theorems you are asked to prove are useful or even necessary for later problems. • Make sure you understand the definitions . A lot of the definitions are not easy to grasp; don’t worry if it takes you a while to fully understand them. If you don’t, then you will not be able to do the problems. Feel free to ask clarifying questions about the definitions on Piazza (or email us). • Don’t make stuff up : on problems that ask for proofs, you will receive more points if you demonstrate legitimate and correct intuition than if you fabricate something that looks rigorous just for the sake of having “rigor.” • Check Piazza often! Clarifications will be posted there, and if you have a question it is possible that it has already been asked and answered in a Piazza thread (and if not, you can ask it, assuming it does not reveal any part of your solution to a question). If in doubt about whether a question is appropriate for Piazza, please email us at pumac@math.princeton.edu. • Don’t cheat : as stated in Rules and Reminders, you may NOT use any references such as books or electronic resources. If you do cheat, you will be disqualified and banned from PUMaC, your school may be disqualified, and relevant external institu- tions may be notified of any misconduct. Good luck, and have fun! – Frank Lu We would like to acknowledge and thank many individuals and organizations for their support; without their help, this Power Round (and the entire competition) could not exist. Please refer to the solutions of the power round for full acknowledgments and references.

Contents 1 Rings and Fields 6 1.1 Rings and Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 A Family of Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Product Rings, Quotient Rings and More Examples . . . . . . . . . . . . . 13 2 Vector Spaces 15 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Coordinates and Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Linear Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Matrices and Row Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Modules 24 4 The PID Structure Theorem 27 4.1 Noetherian Rings and Modules . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Smith Normal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 Proof of the PID Structure Theorem . . . . . . . . . . . . . . . . . . . . . . 32 5 Applications and Asides 32 5.1 A Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 Jordan Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Notation • ∀ : for all. Ex.: ∀ x ∈ { 1 , 2 , 3 } means “for all x in the set { 1 , 2 , 3 } ” • A ⊂ B : proper subset. Ex.: { 1 , 2 } ⊂ { 1 , 2 , 3 } , but { 1 , 2 }̸ ⊂ { 1 , 2 } • A ⊆ B : subset, possibly improper. ex.: { 1 } , { 1 , 2 } ⊆ { 1 , 2 } • f : x 7 → y : f maps x to y . Ex.: if f ( n ) = n − 3 then f : 20 7 → 17 and f : n 7 → n − 3 are both true. • f ( C ): for a function f : A → B and subset C ⊆ A, the set of elements of the form f ( c ) , for c ∈ C. • { x ∈ S : C ( x ) } : the set of all x in the set S satisfying the condition C ( x ). Ex.: √ { n ∈ N : n ∈ N } is the set of perfect squares. • N : the natural numbers, { 1 , 2 , 3 , . . . } . • [ n ] = { 1 , 2 , 3 , ..., n } . • Z : the integers. • Q : the rational numbers. • R : the real numbers. • C : the complex numbers. • | S | : the cardinality of set S .

1 Rings and Fields In this section, our goal is to introduce some structures which generalize some of the key features that we like from some familiar objects. The main example to motivate our dis- cussion is the set of integers Z . In particular, we can add and subtract integers, as well as multiply them together. It is these operations and certain nice properties that they satisfy which we would like to capture. 1.1 Rings and Ideals We begin with the concept of a ring, which generalizes the concept of the integers Z with its addition and multiplication operations. Definition 1.1.1. A ring is a set R equipped with two operations, + and · , satisfying the following conditions:

1. R is closed under + and · : that is, ∀ r , r ∈ R, r + r , r · r ∈ R. 1 2 1 2 1 2
2. The operations + , · are associative: ∀ r , r , r ∈ R, we have that ( r + r ) + r = 1 2 3 1 2 3 r + ( r + r ) , r · ( r · r ) = ( r · r ) · r . 1 2 3 1 2 3 1 2 3
3. The operations + , · are commutative: ∀ r , r ∈ R, r + r = r + r and r · r = r · r . 1 2 1 2 2 1 1 2 2 1
4. The operations + , · have identity elements: specifically, we have elements 0 , 1 ∈ R such that 0 + r = r = 1 · r = ∀ r ∈ R. We refer to 0 as the additive identity of R and 1 as the multiplicative identity of R. ′ ′
5. For each element r ∈ R, there is an element r ∈ R such that r +( r ) = 0 . This element ′ ′ r is the additive inverse of r ; we will sometimes write r as − r.
6. We have the following distributive law: ∀ r , r , r ∈ R, we have r · ( r + r ) = 1 2 3 1 2 3 r · r + r · r . 1 2 1 3 A subring of a ring R is a subset S of R that is a ring, using the same operations + , · as R. Remark. Sometimes we will have more than one ring that we will be concerned with. In that case, for the sake of clarity, we will use + and · to represent the addition and R R multiplication operations for the ring R. In cases where which ring we are working with is clear, for the sake of notational simplicity, we will write r · r as just r r . 1 2 1 2 Similarly, we will write 0 , 1 to denote the additive and multiplicative identities of our ring, with subscripts to indicate which ring we are referring to when it isn’t clear from context. Example. We check that Z is a ring, using the standard addition and multiplication rules. Note that the sum of two integers and the multiplication of two integers is also an integer. Furthermore, we know that addition and multiplication are associative and commutative. The additive identity is 0 and the multiplicative identity is 1 . We observe as well that the additive inverse of an integer is its negative. Finally, we know that addition and multiplication satisfy the distributive law.

Remark. With the above example, we can see how some of the key features of the addition and multiplication operations in Z are captured in the above definition of a ring. It will be useful throughout this section to think about Z when presented with a new example; we will sometimes also explicitly relate the examples to the ring Z throughout the power round. In addition to the above example, Q , R , and C are all rings; you may assume that these are rings without proof, with the standard addition and multiplication rules. When we write one of the above symbols and refer to the corresponding ring, unless otherwise stated, the addition and multiplication rules we are using are the standard addition and multiplication rules. We present an example of a ring that is not one of the above rings. √ √ Example. We will show that Z [ 2] , the set of real numbers of the form a + b 2 , where a, b ∈ Z , is a ring, under the normal addition and multiplication rules. We know from the properties of addition and multiplication of real numbers that properties 2, 3, and 6 hold. We just need to verify properties 1, 4, 5. √ To show property 1, if we are given two elements r , r ∈ Z [ 2] , we know by definition 1 2 √ √ that there exist integers a , b and a , b such that r = a + b 2 and r = a + b 2 . 1 1 2 2 1 1 1 2 2 2 √ √ Then, we find that r + r = ( a + a ) + ( b + b ) 2 ∈ Z [ 2] . Furthermore, r r = 1 2 1 2 1 2 1 2 √ √ √ √ ( a + b 2)( a + b 2) = ( a a + 2 b b ) + ( a b + a b ) 2 , which again lies in Z [ 2] . This 1 1 2 2 1 2 1 2 1 2 2 1 shows the first property holds. For property 4, note that the identity elements for addition and multiplication over R , √ √ which are 0 and 1 , respectively, lie in Z [ 2] , and so Z [ 2] also contains identity elements for addition and multiplication. √ Finally, for property 5, given any element r ∈ Z [ 2] , we know that it takes the form √ √ √ ′ a + b 2 for some integers a, b. But then the value r = ( − a ) + ( − b ) 2 also lies in Z [ 2] , √ ′ and the sum r + r yields 0 . We have thus shown that Z [ 2] is a ring. 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 coeffi- cients, 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 ]). We also have the following example of a ring. Keep this example in mind as you go through the rest of this section. Problem 1.1.2. 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.

Using the above definition of a ring, we can already prove some basic properties. For instance, we have the following elementary proposition. Proposition 1.1.2. Let R be a ring, with additive identity 0 and multiplicative identity 1 .

1. There exists exactly one element e ∈ R so e + r = r ∀ r ∈ R, namely e = 0 , and there is exactly one element i ∈ R so ir = r ∀ r ∈ R, namely i = 1 . In other words, the additive and multiplicative identity elements are unique.
2. For all r ∈ R, 0 r = 0 . ′ Proof. To prove the first property, suppose there were two elements e, e such that e + r = ′ ′ ′ r = e + r for all r ∈ R. Then, observe that e + e = e , using the left equation, but ′ ′ ′ e + e = e + e = e, using the right equation. Therefore, e = e , and there is only one additive identity. ′ ′ Similarly, suppose there were two elements i, i so that ir = r = i r for all r ∈ R. Then, ′ ′ ′ ′ we know that ii = i , from the left equation, but ii = i i = i from the right equation, so ′ again i = i , and there is only one multiplicative identity. To prove the second property, we observe that for each r ∈ R, 0 r + 0 r = (0 + 0) r = 0 r. Therefore, adding to both sides of the equation the additive inverse of 0 r yields us that 0 r = 0 , which is what we wanted to show. 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? One of the first things we wish to generalize is the notion of divisibility in Z . In particular, we can consider in Z subsets that are given as multiples of a given integer. We will begin with something which captures some of the most basic properties about these sets; a more precisely analogous concept will be introduced later. Definition 1.1.3. An ideal of a ring R is a nonempty subset I ⊆ R such that the following properties hold: ′ ′
3. I is closed under addition. That is, for i, i ∈ I, we have i + i ∈ I.
4. For every i ∈ I and r ∈ R, we have that ri ∈ I. A proper ideal of a ring R is an ideal I that is not equal to R itself. Example. We show that the set of even integers is an ideal in the ring Z . To see this, recall that the set of even integers are all the integers that can be written as 2 n, for some integer ′ n ∈ Z . Property 1 follows since for any r, r even integers, we know that there exist integers ′ ′ ′ ′ ′ n, n so r = 2 n, r = 2 n , and so r + r = 2( n + n ) , which is again even. For the second property, given an even integer i, we can write it as i = 2 n for some integer n. But then for any integer r, we have that ri = r 2 n = 2( nr ) , which is again an even integer.

Problem 1.1.4. Show that the set of odd integers, as a subset of Z , is not an ideal. (Hint: which property does this set not satisfy?) Sometimes, we want to specify an ideal of R without having to explicitly list all of the elements. In particular, we only need to specify a subset of the elements of the ideal, knowing that our ideal satisfies the properties in the definition. For instance, note that any ideal that contains 2 also must contain the even integers. Indeed, note that if 2 lies in an ideal I, then so does every even integer, since each even integer is equal to 2 times some other integer. As the even integers are an ideal, it thus makes sense to describe the ideal of even integers as the smallest ideal that contains 2 : that is, every other ideal containing 2 contains the even integers, and the even integers are precisely the set of integers which are a multiple of 2 . These notions, of each even integer being a multiple of 2 , and of the even integers being the smallest such ideal containing 2 , motivates the notion of generators of an ideal. Definition 1.1.4. We say that an ideal I is generated by a subset of elements S ⊂ I if n P every element i ∈ I can be written in the form i = r s , for some positive integer n, and j j j =1 elements s , s , . . . , s ∈ S and r , r , . . . , r ∈ R. 1 2 n 1 2 n Similarly, given a ring R and elements s , s , . . . , s , we let ⟨ s , s , . . . , s ⟩ be the set of 1 2 n 1 2 n n P elements of the form i = r s for elements r , r , . . . , r ∈ R. We can also substitute a j j 1 2 n j =1 n P set, letting ⟨ S ⟩ be the set of elements in R of the form i = r s for some positive integer j j j =1 n, and elements s , s , . . . , s ∈ S, r , r , . . . , r ∈ R. 1 2 n 1 2 n With the notation above, the set of even integers, 2 Z , can also be written as ⟨ 2 ⟩ . Note that the set of even integers is an ideal. This happens more generally, as follows. Proposition 1.1.5. Given a subset S ⊂ R, the set ⟨ S ⟩ is an ideal. ′ Proof. For the first condition, suppose that we have two elements in ⟨ S ⟩ , say i and i . ′ ′ ′ Then, there are positive integers n, m and elements s , s , . . . , s , s , s , . . . , s ∈ S and 1 2 n 1 2 m n m P P ′ ′ ′ ′ ′ ′ r , r , . . . , r , r , r , . . . , r ∈ S such that i = r s and i = r s . Then, their sum 1 2 n j j m 1 2 j j j =1 j =1 n m P P ′ ′ ′ is equal to i + i = r s + r s , which is of the given form. Notice that we can j j j j j =1 j =1 ′ further simplify this expression if we know that some of the s and s are equal, using the j j distributive property. n P For the second condition, given an element i in ⟨ S ⟩ , we can write it as r s for some j j j =1 positive integer n, s , s , . . . , s ∈ S and r , r , . . . , r ∈ R. But then, for each element 1 2 n 1 2 n n P r ∈ R, observe that ri = rr s , which is also in ⟨ S ⟩ . This finishes the proof of the j j j =1 proposition. Definition 1.1.6. We call the set ⟨ S ⟩ the ideal generated by S.

We now wish to generalize the notion of a prime from Z . Rather than thinking about elements as being primes, we want to think about ideals. The main behavior we want to capture is the fact that, given a prime number p, if ab lies in p Z , then either a or b lies in it. Contrast this with 6 Z , for instance: 2 · 3 lies in 6 Z , but 2 , 3 do not lie in 6 Z . Definition 1.1.7. An ideal I of a ring R is said to be prime if it is a proper ideal, and furthermore, for all a, b ∈ R, ab ∈ I implies that either a ∈ I or b ∈ I. For instance, the ideal ⟨ 2 ⟩ ⊂ Z is a prime ideal, since ab ∈ ⟨ 2 ⟩ if and only if ab is an even integer; but notice that one of a, b must be even as well. Problem 1.1.5. Determine, with proof, all the prime ideals of C [ x ] . You may use, without proof, the following theorem: any nonconstant polynomial 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. This theorem is also known as the Fundamental Theorem of Algebra. We finish by considering functions between rings. To do this, we have the following definition relating functionss between sets. ′ ′ Definition 1.1.8. Given a function f : S → S , where S, S are sets, we say that f is injective if f ( s ) = f ( t ) implies that s = t for any s, t ∈ S. ′ ′ ′ We say that f is surjective if for all s ∈ S , there exists an s ∈ S so f ( s ) = s , and bijective if it is both injective and surjective. 3 For instance, treating all the following as functions from R to R , the function f ( x ) = x x is injective and surjective, the function g ( x ) = 2 is injective but not surjective, and the 3 function f ( x ) = x − x is surjective but not injective. Note that the specification of the set ′ x S is important: the function g ( x ) = 2 is surjective when viewed as a function from R to { x ∈ R | x > 0 } . 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] . ′ ′ Definition 1.1.9. Given a function f : S → S , an inverse of f is a function g : S → S ′ ′ ′ ′ such that f ( g ( s )) = s for all s ∈ S , and g ( f ( s )) = s for all s ∈ S. We have the following proposition, which you may assume to be true without proof. Proposition 1.1.10. A function has an inverse if and only if it is injective and surjective. If a function has an inverse, this inverse is unique. We can now introduce our notion of maps (which is another word for “function”) between rings.

Definition 1.1.11. A ring homomorphism between rings R and S is a map ϕ : R → S such that the following holds: ′ ′ ′ ′ ′

1. For all r, r ∈ R, we have ϕ ( r + r ) = ϕ ( r ) + ϕ ( r ) and ϕ ( r · r ) = ϕ ( r ) · ϕ ( r ) . R S R S
2. ϕ (1 ) = 1 . R S If this map is bijective, we say that it is a ring isomorphism, and then we say that R, S are isomorphic. The notion of two rings being isomorphic essentially means that two rings are the “same;” that is, you can go from one to the other simply by relabelling the elements. As a simple example, the function Z → Q sending n ∈ Z to itself, is a ring homomor- √ phism. This is injective but not surjective. We also have a ring isomorphism ϕ from Z [ 2] √ √ to itself that sends a + b 2 to a − b 2 . One can check that the properties of a ring homo- √ √ morphism hold for this function: for instance, we notice that ϕ ( a + b 2) + ϕ ( c + d 2) = √ √ ( a + c ) − ( b + d ) 2 = ϕ (( a + c ) + ( b + d ) 2) . 1.2 A Family of Rings We are now interested in a variety of different types of rings. Definition 1.2.1. A field is a ring R such that every nonzero element r ∈ R has a multiplicative inverse; that is, for each nonzero r ∈ R, there is an element s ∈ R such that rs = 1 . For instance, Q , R , C are all fields; you may assume this fact without proof. √ 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 . 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? (Hint: think about the second question first. Consider the field of rational numbers Q . What are its ideals?). Of course, not all rings are fields, such as Z . However, Z still has some properties that distinguish it from other rings. In particular, it is the following type of ring. Definition 1.2.2. A integral domain is a ring R such that for any a, b ∈ R, ab = 0 if and only if one of a, b is zero. Another example of such a ring is C [ x ] . One can check that the product of two polyno- mials is zero if and only if one of the polynomials is zero. However, not all rings are integral domains. For instance, consider Z / 4 Z , where addition and multiplication are done modulo 4 . One can verify that this is a ring. Then, notice that 2 · 2 = 0 , but 2 ̸ = 0 , so this ring is not an integral domain. We are also interested in rings with particular finiteness properties, with regards to ideals. This motivates the definitions below.

Definition 1.2.3. A principal ideal domain , or a PID, is an integral domain such that every ideal can be generated by one element. Problem 1.2.3. Show that Z is a PID. As a hint, 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. Remark. In particular, notice that this shows that the only ideals of Z are the zero ideal (the ideal consisting only of the element 0) and n Z , the set of elements divisible by a positive integer n. As another example, it turns out that for any field k, we have that k [ x ] , the set of polynomials with coefficients in k, is a PID. Here, we take our addition operation and multiplication operations to be the typical addition and multiplication of two polynomials: n n n X X X i i i a x + b x = ( a + b ) x , i i i i i =1 i =1 i =1 and n n 2 n n X X X X i i i a x · b x = ( a b ) x , i i k j − k i =1 i =1 j =1 k =1 where a = b = 0 for i not equal to 1 , 2 , . . . , n. You may use the following theorem without i i proof. Theorem 1.2.4. Given a field k, the ring k [ x ] is a PID. Besides ideals being prime, in Z we also have the notion of prime elements. There are two properties of primes which seem familiar, but are slightly different. First, note that a prime number cannot be decomposed into a product of two other numbers, where neither is 1 , − 1 . The second is that if p divides a product of positive integers, then p divides one of the positive integers. In Z , an element satisfies one property if and only if it satisfies the other. In general, however, we cannot assume this. As such, we have the following definition. Definition 1.2.5. Given a ring R, a unit is an element u ∈ R with a multiplicative inverse. An element r ∈ R is irreducible if it cannot be written as the product of two elements in the ring, neither of which are units, and furthermore is not a unit itself. An element r ∈ R is prime if it is nonzero and the ideal generated by r is prime. Example. For instance, the prime numbers in Z are prime in the sense of the above definition. To prove this, given a prime number p, suppose that we have integers a, b ∈ Z such that ab ∈ ⟨ p ⟩ . In other words, p divides ab. But we know by the Fundamental Theorem of Arithmetic that this means that p appears in the prime factorization of ab, and thus of either a or b. The more traditional definition of a prime in Z , that a prime is divisible by only 1 or itself, shows that all the prime numbers are irreducible as well. However, we note that 4 is not prime: for instance, 2 · 2 lies in ⟨ 4 ⟩ , but 2 does not. Finally, we observe the only units in Z are 1 , − 1 .

Problem 1.2.4. Show that for any integral domain R, every prime element is irre- ducible. Recall that we can uniquely factor integers into primes, up to ordering of the primes. However, not all rings have this property. This suggests the following category of ring which we’d like to consider. Definition 1.2.6. A unique factorization domain , or UFD, is an integral domain where every nonzero element can be uniquely written as a product of irreducible elements and a unit, up to the order of irreducible elements and unit multiples. For instance, Z is a UFD; this is the condition that lets us perform prime factorization, and this factorization is unique up to ordering of the primes and choice of signs on the primes. In fact, we can say something more general. We present the following theorem, which you may use throughout this power round without proof. Theorem 1.2.7. Every PID is a UFD, and in every UFD, every irreducible element is also prime. However, we have the following non-example of a UFD. √ √ 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. 1.3 Product Rings, Quotient Rings and More Examples In this subsection, we introduce two important constructions with regards to rings, before proceeding with some explicit examples of rings. Definition 1.3.1. Given two rings R and S, their product R × S is the set of pairs ( r, s ) , where r ∈ R, s ∈ S. We can then define the addition and multiplication operations by ′ ′ ′ ′ ′ ′ ′ ′ ( r, s ) + ( r , s ) = ( r + r , s + s ) and ( r, s ) · ( r , s ) = ( r · r , s · s ) . Recall here that R S R S

• , · are the addition and multiplication operations on R, and + , · are the addition and R R S S multiplication operations on S. Example. For instance, consider the product of the rings Z / 2 Z and Z / 3 Z . The addition and multiplication tables for this ring are given below:
• (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (0, 0) (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (0, 1) (0, 1) (0, 2) (0, 0) (1, 1) (1, 2) (1, 0) (0, 2) (0, 2) (0, 0) (0, 1) (1, 2) (1, 0) (1, 1) (1, 0) (1, 0) (1, 1) (1, 2) (0, 0) (0, 1) (0, 2) (1, 1) (1, 1) (1, 2) (1, 0) (0, 1) (0, 2) (0, 0) (1, 2) (1, 2) (1, 0) (1, 1) (0, 2) (0, 0) (0, 1)

· (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 0) (0, 1) (0, 0) (0, 1) (0, 2) (0, 0) (0, 1) (0, 2) (0, 2) (0, 0) (0, 2) (0, 1) (0, 0) (0, 2) (0, 1) (1, 0) (0, 0) (0, 0) (0, 0) (1, 0) (1, 0) (1, 0) (1, 1) (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (1, 2) (0, 0) (0, 2) (0, 1) (1, 0) (1, 2) (1, 1) One can show that this is a ring; for the purposes of this power round, you may assume this to be true. Definition 1.3.2. Given a ring R, let r ∈ R and I be an ideal of R. Let r + I be the set of elements of the form r + i, for i ∈ I, and let R/I be the set { r + I | r ∈ R } . Then, on this set, define the sum as ( r + I ) + ( r + I ) = ( r + r ) + I and the product as 1 2 1 2 ( r + I ) · ( r + I ) = r r + I. 1 2 1 2 Example. For instance, consider the ring Z . Note that 3 Z is an ideal. Then, 0 + 3 Z = { 0 , 3 , − 3 , 6 , − 6 , . . . } , and similarly 1 + 3 Z = { 1 , 4 , − 2 , 7 , − 5 , . . . } and 2 + 3 Z = { 2 , 5 , − 1 , 8 , − 4 , . . . } . First, we need to verify that these operations are well-defined: that is, if we pick a ′ ′ different choice of r such that r + I = r + I, then the result of the operation should still be the same. In particular, notice that for any i ∈ I, r + I = ( r + i ) + I. ′ Problem 1.3.1. Prove that the operations are well-defined. That is, if r + I = r + I 1 1 ′ and r + I = r + I, then 2 2 ′ ′ ( r + I ) + ( r + I ) = ( r + I ) + ( r + I ) 1 2 1 2 and ′ ′ ( r + I ) · ( r + I ) = ( r + I ) · ( r + I ) . 1 2 1 2 Remark. Note that it is important that we check that this operation is well-defined. Some- times we want to define an operation that has certain nice properties. However, it is not always clear that such an operation exists. In particular, we should expect to get the same result if we apply the same input, regardless of how we describe that input. As a non-example, note that the “numerator” of a rational number is not well-defined. The number 0 . 5 could have numerator 1 (from the fraction 1 / 2), or numerator 8 (from 8 / 16). This is a problem, since then this function is not actually a function of the number itself, but rather how we write it. Similarly, we need to check in the above problem that our operations are actually operations that depend only on the sets r + I, not on which r we used to represent it. Now, we claim that this is a ring.

Problem 1.3.2. Prove that R/I is a ring, equipped with the operations we defined above. We call this ring a quotient ring of R. For instance, the set of residues (mod m ) , for any positive integer m, is a quotient ring, given by Z / ⟨ m ⟩ . One can show that Z /m Z can be thought of as the quotient of Z by the ideal m Z = ⟨ m ⟩ , explaining the notation. You may use this fact without proof throughout the rest of the power round. We now aim to prove the following theorem. Problem 1.3.3. Let R be a ring, and let I , I be two ideals of R, such that I + I = 1 2 1 2 { i + i | i ∈ I , i ∈ I } = R. 1 2 1 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 1 2 1 2 r + I ∩ I to ( r + I , r + I ) . Show that this map is well-defined and indeed a 1 2 1 2 homomorphism.

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 This is known as the Chinese Remainder Theorem for rings. This is related to the case of Chinese Remainder Theorem for the integers. 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 r (mod n ) , there exists a unique residue r (mod mn ) so 1 2 r ≡ r (mod m ) and r ≡ r (mod n ) . 1 2 2 Vector Spaces We now foray into a brief introduction into the subject of linear algebra, and the study of vector spaces. As we shall see, these structures are comparatively easy to classify. 2.1 Definitions We begin by introducing our object of study. Definition 2.1.1. Given a field k, a vector space V over the field k is a set of elements, which we call vectors, equipped with two operations, addition + : V × V → V and scalar multiplication · : k × V → V, satisfying the following properties:

5. V is closed under + and · : that is, ∀ v , v ∈ V, v + v ∈ V, and for all s ∈ k, v ∈ V, 1 2 1 2 we have s · v ∈ V.

6. The operations + , · are associative: ∀ v , v , v ∈ V, we have that ( v + v ) + v = 1 2 3 1 2 3 v + ( v + v ) , and for s , s ∈ k and v ∈ V, we have s · ( s · v ) = ( s · s ) · v. 1 2 3 1 2 1 2 1 2 k

7. The operation + is commutative.

8. The operation + has an identity element, which we denote as 0 .

9. Each element v ∈ V has an additive inverse.

10. For all v ∈ V, 1 · v = v. k

11. We have the following distributive laws: ∀ s ∈ k and v , v ∈ V, we have s · ( v + v ) = 1 2 1 2 s · v + s · v , and for all s , s ∈ k and v ∈ V, we have ( s + s ) · v = s · v + s · v. 1 2 1 2 1 2 1 2 Again, we sometimes omit the multiplication dot, and add subscripts to the operations as needed; the same convention will apply to other structures as well (when we introduce modules in the next section). We also say that V in this case is an k − vector space. A subspace of V is a subset U that is also a vector space under the same operations as that of V. Example. Consider the set of ( x , x , . . . , x ) of real numbers. We equip it with coordinate- 1 2 n wise addition and scalar multiplication, by ( x , x , . . . , x ) + ( y , y , . . . , y ) = ( x + y , x + 1 2 n 1 2 n 1 1 2 y , . . . , x + y ) and r · ( x , x , . . . , x ) = ( rx , rx , . . . , rx ) . We show that this forms a 2 n n 1 2 n 1 2 n vector space over R . We first observe that for tuples ( x , x , . . . , x ) and ( y , y , . . . , y ) , we 1 2 n 1 2 n have that their sum is ( x + y , x + y , . . . , x + y ) is also a tuple of real numbers (as the real 1 1 2 2 n n numbers are closed under addition). Similarly, given r ∈ R and a tuple ( x , x , . . . , x ) , we 1 2 n have that r · ( x , x , . . . , x ) = ( rx , rx , . . . , rx ) is a tuple of real numbers (real numbers 1 2 n 1 2 n are closed under addition). The commutativity, associativity, and distributivity properties are given from those of addition and multiplication over R . Indeed, from the fact that these operations are defined on each coordinate, properties 2, 3, 7 hold if they hold for each coordinate, which is the case because these properties hold for R . To show identity element, we note that (0 , 0 , . . . , 0) is the identity element (since adding this to any tuple doesn’t change any of the coordinates), and we observe that negating each of the entries of any tuple yields its additive inverse. Finally, property 6 follows since 1 · ( x , x , . . . , x ) = (1 · x , 1 · x , . . . , 1 · x ) = ( x , x , . . . , x ) . This gives us that this is a 1 2 n 1 2 n 1 2 n vector space. n n n We denote the vector space above as R . By the same reasoning, we have that Q , C n (defined analogously) are vector spaces (and more generally k for any field k ) for n ∈ N . Here are some other examples of vector spaces. Problem 2.1.1. Prove the following spaces are vector spaces.

12. The set of polynomials with complex coefficients (with the standard addition and multiplication operations), over the field C .

13. R , (with standard addition and multiplication operations), over the field Q . Here’s an interesting non-example.

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. 2.2 Coordinates and Bases Throughout this section, we will fix a vector space V over a field k. Definition 2.2.1. A linear combination of v , v , . . . , v ∈ V is an expression of the form 1 2 n n P s v , where s ∈ k. By convention we say that we can take n = 0; in this case this is an i i i i =1 empty sum, which we set to equal zero. A spanning set is a set S such that every element can be written as a linear combination of some finite subset of S. We say that a module is finite dimensional if it has a finite spanning set, and infinite dimensional otherwise. A set of elements of M is linearly independent if, for every finite subset of M, the only linear combination of these elements that equals zero is the linear combination where all of the coefficients s are 0 . Notice that if M is finite then it suffices to check the above i condition at the set M. By convention we say that the empty set is a linearly independent set. A set of elements of V is said to be a basis if it is linearly independent and a spanning set. Example. For instance, in the space of polynomials of degree at most 2 with coefficients 2 in C , the polynomials 1 , x, x are a basis. Indeed, they are linearly independent, since if 2 a + bx + cx = 0 as polynomials, where a, b, c ∈ C , then a = b = c = 0 . Furthermore, every 2 polynomial of degree at most 2 , by definition, can be written in the form a + bx + cx , and 2 so these elements 1 , x, x are a basis. 2 2 As another example, note that 1 + x, x , 2 x + x + 1 is not a basis, since they are linearly 2 2 dependent. Indeed, 2 x + x + 1 + ( − 2) x + ( − 1)( x + 1) = 0 . 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. Our main goal for this subsection is to prove that every finite dimensional vector space indeed has a basis, and in fact the length of this basis is the same, for a given vector space V. From here on out, assume that we are working within a given finite dimensional vector space V. We begin by trying to compare the lengths of spanning sets and linearly independent sets. To do this, consider the following properties of spanning sets.

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. From here, we consider the following procedure. Start with a linearly independent set L and a spanning set S ; by assumption, we know that we can pick a spanning set S that is finite. We now consider replacing vectors in S with those that are in L. 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. 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. Using this size comparison, we are now ready to construct a basis for our vector space, and show they have the same size. The first result allows us to state that every vector space has a basis. Problem 2.2.5. Prove the following.
3. 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.
4. 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. We are now ready to state the main result. 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. n For instance, one can check that R , as a vector space over R , has dimension n (you may assume this throughout the rest of the power round). Similarly, the space of polynomials, with coefficients in C , with degree at most 2 , is a vector space with dimension 3 , as we saw 2 previously with this space having basis 1 , x, x . Problem 2.2.7. Show that if W is a subspace of V, then the dimension of W is at most that of V.

2.3 Linear Transforms Now that we’ve discussed vector spaces, we can consider maps between vector spaces. Just like with rings, we consider a special type of map between vector spaces that are linear. Definition 2.3.1. A linear transformation between two vector spaces V, W over a com- mon field k is a map T : V → W satisfying the following conditions:

1. For all vectors v , v ∈ V, we have T ( v + v ) = T ( v ) + T ( v ) . 1 2 1 2 1 2
2. For all s ∈ k and v ∈ V, we have T ( sv ) = sT ( v ) . Such a linear transformation is an isomorphism if it is both injective and surjective. As a first example, the maps of the form f ( x ) = kx, for k ∈ R , are all linear transfor- mations from R to R . Notice, however, that f ( x ) = x + 1 is not a linear transformation, since f (1) + f (1) = 2 + 2 = 4 , but f (1 + 1) = f (2) = 3 . Notice that the second condition is sometimes unnecessary. 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 1 2 1 2 1 2 linear. Now, given a linear transformation T : V → W, we consider the following two sets associated with this linear transformation: the kernel and the image. Definition 2.3.2. The kernel of a linear transformation, ker T, is the set of elements v ∈ V such that T ( v ) = 0 . The image, im T, is the set of elements w ∈ W such that there exists W a v ∈ V so T ( v ) = w. Example. Consider the map that sends a polynomial of degree at most 2 , with coefficients in C , to its value at 0 (lying in C ); we can easily check that this is a linear transformation. The kernel of this map is then just the set of polynomials that vanish at 0 , namely those of 2 the form ax + bx , for a, b ∈ C , and the image is C . Proposition 2.3.3. A linear transformation T is injective if and only if ker T = { 0 } . V Proof. First, we note that T being injective means that ker T only has one element. Fur- thermore, by linearity, T (0 ) + T (0 ) = T (0 ) , meaning that T (0 ) = 0 , meaning that V V V V W ker T = { 0 } . For the other direction, if ker T = { 0 } , suppose that T ( v ) = T ( v ) . By lin- V v 1 2 earity, we have that T ( v ) − T ( v ) = T ( v ) + ( − 1) T ( v ) = T ( v ) + T ( − v ) = T ( v − v ) = 0 . 1 2 1 2 1 2 1 2 But this means that v − v ∈ ker T, or that v − v = 0 , meaning that v = v . This means 1 2 1 2 T 1 2 that T is injective, which is what we wanted to show. Problem 2.3.2. Show that ker T is a subspace of V. We now have the following result, which essentially states that finite-dimensional vector spaces are essentially determined by their dimension. Indeed, just like with rings, we can think of isomorphisms as simply being “relabellings” of the elements in our original space.

Problem 2.3.3. Suppose that V and W are finite dimensional vector spaces with the same dimension d. Prove that V, W are isomorphic ; that is, there exists an isomor- phism between them. To show that this characterizes the space, we should also verify that two spaces that are different dimensions cannot be isomorphic. First, we verify the following. Problem 2.3.4. Prove that an infinite dimensional vector space cannot be isomorphic to a finite dimensional vector space. For a given linear transformation T, we can relate the dimension of its image and kernel in the following way. The following theorem is also known as the rank-nullity theorem. Theorem 2.3.4. Suppose that T is a linear transformation from V to W, where V is a finite dimensional vector space. Then, dim ker T + dim im T = dim V. Often, dim ker T is referred to as the nullity of T, and dim im T the rank. To do this, first consider a basis for ker T. Say these vectors are w , w , . . . , w . 1 2 n 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 n +1 n +2 m T ( w ) , T ( w ) , . . . , T ( w ) n +1 n +2 m form a basis for im T, and from here prove the theorem. Using the theorem, we also say the following. Problem 2.3.6. Show that two finite dimensional vector spaces are isomorphic if and only if they have the same dimension. This says essentially that, for a given field k, the finite dimensional vector spaces over that field are characterized exactly by the dimension of the space, up to isomorphism. 2.4 Matrices and Row Reduction Sometimes it is useful to be able to talk explicitly about the vectors in a vector space V. This can be done by fixing a basis of our vector space V, and then describing each vector as being a linear combination of these basis vectors. In particular, given our basis w , w , . . . , w , 1 2 n   a 1   a 2   n P   n a 3 we represent v = a w as the column vector ∈ k .   i i   . i =1 .   . a n

Problem 2.4.1. Show that this above map is well-defined and is an isomorphism n between V and k . If we now specify bases ( v , v , . . . , v ) for V and ( w , w , . . . , w ) for W, we can now describe 1 2 n 1 2 m m P every linear transformation T : V → W as a matrix . Specifically, if T ( v ) = a w , we j i,j i i =1 can represent T as the following m × n array of numbers:   a a · · · a 11 12 1 n   a a · · · a 21 22 2 n   .   . . . . . .   . . . a a · · · a m 1 m 2 mn We say that a is the ( i, j )th entry of this matrix. ij We can then view the operation of the linear transformation entirely using the coordi- nates described by these bases, using the following multiplication rule:   n P   a x 1 i i   x   1 i =1 a a · · · a   11 12 1 n n   P x   2     a x a a · · · a   2 i i 21 22 2 n     x   3 i =1 = .     . . .   . . .     . . . . .   . .   . .   a a · · · a   n m 1 m 2 mn P x n a x mi i i =1 For instance, given the vector space of polynomials of degree at most 2 , we can see that 2 this has a basis 1 , 1 + x, 1 + x + x . Consider the map that sends each polynomial to the p (0) vector . Then, the matrix that we get for this linear transformation is p (1) 1 1 1 . 1 2 3 1 2 For instance, we note that T (1 + x + x ) = , giving us the third column. 3 We wish to relate the two operations of matrix multiplication and of applying our linear transformation in general. Problem 2.4.2. Show that if we multiply the matrix of T with the coordinate rep- resentation 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. Often, we want to represent T using a choice of bases that are as simple as possible. If we are allowed to change the bases of both V and W, this can take a particularly simple form.

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 ? Although this is a nice result, often we run into situations where we cannot freely choose bases in the way the above result requires. First, if T is a map from a vector space to itself, we often only want to use one basis for both the input and output. This gives us significantly less flexibility; see section 5 for more details. In other situations, we have a nice basis for V which we would like to preserve. As such, we are only allowed to choose a basis for W. In this latter situation, we can achieve a comparatively simple form using a method called row reduction. The main algorithm for row reduction utilizes three operations, acting on rows of our matrix.

1. We can take a row and multiply every entry in the row by some nonzero scalar c ∈ k.
2. We can swap two rows (that is, if we are swapping rows i, j, then the old ( i, k )th entry is the new ( j, k )th entry for k = 1 , 2 , . . . , n, and vice versa).
3. We can add a multiple of one row to another row.   2 6 3   For instance, we can apply some row operations to the matrix 1 0 4 . If we 0 − 1 1   2 6 3   subtract half the first row from the second, we get the matrix 0 − 3 2 . 5 . If we then 0 − 1 1   1 3 1 . 5   divide the first row by 2 , we get the matrix 0 − 3 2 . 5 . 0 − 1 1 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? From here, we claim that we can reach the following form, known as reduced row echelon form. This form satisfies the following properties.
4. Every row with at least one nonzero entry has their leftmost nonzero entry as a 1 . These 1s are known as pivots.
5. Each pivot is the only nonzero entry in its column.
6. The pivot of the i th row is left of the pivot of the j th row if i < j.
7. The rows with all zeros are on the bottom of the matrix.

For instance, with the same matrix as the above, we can continue our procedure: swapping   1 3 1 . 5   rows two and three yields 0 − 1 1 , then subtracting three times the second row 0 − 3 2 . 5   1 3 1 . 5   from the third yields 0 − 1 1 . Adding three times the second row to the first 0 0 − 0 . 5   1 0 4 . 5   yields 0 − 1 1 . Adding two times the third row to the second, and nine times the 0 0 − 0 . 5   1 0 0   third row to the first, yields 0 − 1 0 . Multiplying the third row by − 2 and the 0 0 − 0 . 5   1 0 0   first by − 1 yields the final matrix 0 1 0 , which is in reduced row echelon form. 0 0 1 Problem 2.4.5. Reduce the following matrices to reduced row echelon form. 1 2 3 1. 6 5 4   4 2 − 1 − 3   2. 1 0 − 5 2 0 1 0 2 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 . Problem 2.4.7. Using the above procedure, show that any matrix can be reduced to reduced row echelon form. With the reduced row echelon form, we can more easily read off useful information about our linear transformation T. 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). With the above method, we can everywhere replace the word “row” with “column” to get column reduction. This corresponds to changing the basis for the input space, which you may assume without proof.

3 Modules We can generalize the definition of a vector space above to that of a module, as below. Definition 3.0.1. Given a ring R, a module M is a set of elements equipped with two operations, addition + : M × M → M and scalar multiplication · : R × M → M, satisfying the following properties:

1. M is closed under addition and scalar multiplication: that is, ∀ m , m ∈ M, m + m ∈ 1 2 1 2 M, and for all r ∈ R, m ∈ M, we have r · m ∈ M.
2. The operations + , · are associative: ∀ m , m , m ∈ M, we have that ( m + m )+ m = 1 2 3 1 2 3 m + ( m + m ) , and for r , r ∈ R and m ∈ M, we have r · ( r · m ) = ( r · r ) · m. 1 2 3 1 2 1 2 1 R 2
3. The operation + is commutative.
4. The operation + has an identity element, which we denote as 0 .
5. Each element m ∈ M has an additive inverse.
6. For all m ∈ M, 1 · m = m. R
7. We have the following distributive laws: ∀ r ∈ R and m , m ∈ M, we have r · ( m + 1 2 1 1 m ) = r · m + r · m , and for all r , r ∈ R and m ∈ M, we have ( r + r ) · m = 2 1 1 1 2 1 2 1 2 r · m + r · m. 1 2 We also say that M in this case is an R − module. A submodule of M is a subset N that is also a module under the same operations as that of M. Notice in particular that a vector space over a field is also module over that field, and any ring is a module over itself. Here is another example. Example. The set of even integers is a module over Z , using the standard addition on even integers and scalar multiplication being just multiplication in Z . Properties 2, 3, 7 follow simply because we know that Z is a ring, and property 1 follows since we’ve previously argued that the sum of even integers is even, and the product of an even integer with another integer is even. For property 4, we note that the identity for addition, 0 , lies in Z , and property 5 follows since we know that for each even integer, its negation is also even. Finally, for property 6, by the standard multiplication rule in Z , multiplying any even integer by 1 yields the even integer again. This example can be generalized. 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. Definition 3.0.2. Given an R − module M, a linear combination of m , m , . . . , m ∈ M 1 2 n n P is an expression of the form r m , where r ∈ R. i i i i =1

A generating set of a module M is a set S such that every element can be written as a linear combination of some finite subset of S. We say that a module is finitely generated if it has a finite generating set. A set of elements of M is linearly independent if the only linear combination of these elements that equals zero is the linear combination where all of the coefficients r are 0 . i A set of elements of M is said to be a free basis of M if it is linearly independent and a generating set. In this case, if such a free basis exists, we say that M is a free module . Its rank is then the length of this free basis. These definitions should be reminiscent of definitions of linear independence and span from our discussions of linear algebra. We need to explicitly point out when our modules are free for the following reason. √ √ Example. Consider the ideal I = ⟨ 2 , 1 + − 5 ⟩ inside the ring R = Z [ − 5] , the set of √ integers of the form a + b − 5 for some integers a, b. Notice that this ideal is an R − module by Problem 3.0.1. We show that this is not a free module. To see this, suppose for the sake of contradiction that { r , r , . . . , r } was a free basis for 1 2 k I. If k ≥ 2 , then note that by linear independence that none of the elements can be zero. But then ( − r ) r + r r = 0 , meaning that this set is not linearly independent, contradiction. 2 1 1 2 Therefore, I would have to have a free basis with one element, say r . But then there 1 √ exist elements s , s ∈ R such that s r = 2 and s r = 1 + − 5 . But suppose that 1 2 1 1 2 1 √ √ √ s = a + a − 5 and r = b + b − 5 , then s r = ( a b − 5 a b ) + ( a b + a b ) − 5 . 1 1 2 1 1 2 1 1 1 1 2 2 1 2 2 1 For this to equal 2 , we need a b = − a b . Note however that multiplying this by ( a − 1 2 2 1 1 √ √ √ a − 5)( b − b − 5) , which equals ( a b − 5 a b ) − ( a b + a b ) − 5 = 2 , yields that 2 1 2 1 1 2 2 1 2 2 1 2 2 2 2 ( a + 5 a )( b + 5 b ) = 4 . For this to hold, as the a are integers, we need one pair of ( a , a ) i 1 2 1 2 1 2 to be ( ± 1 , 0) and the other to be ( ± 2 , 0) . However, note that r cannot be ± 2 , since that 1 √ √ 1+ − 5 implies that s = ± ∈ / Z [ − 5] , contradiction. 2 2 √ √ But if r = ± 1 , this means that 1 ∈ ⟨ 2 , 1 + − 5 ⟩ , meaning that there exist a + b − 5 1 √ √ √ √ √ and c + d − 5 in Z [ − 5] so 2( a + b − 5) + (1 + − 5)( c + d − 5) = 1 , or that (2 a + c − 5 d ) + √ (2 b + c + d ) − 5 = 1 . But c − 5 d would have to be odd and c + d even, which is impossible. Hence, no r can exist, and therefore I must not be a free module, which is what we 1 wanted to show. Observe that if we are given a free module, the following property from linear algebra does carry over to the module case. You may assume that this proposition holds without proof. Proposition 3.0.3. Suppose that F is a free module over a nonzero ring R that is finitely generated. Then, any two free bases of F have the same length. Similarly to the vector space case, we can also consider maps between modules, in the following way. Definition 3.0.4. A module homomorphism between R − modules M and N is a map ϕ : ′ ′ ′ M → N such that for all m, m ∈ M and r ∈ R, we have that ϕ ( m + m ) = ϕ ( m )+ ϕ ( m ) , M N and ϕ ( r · m ) = r · ϕ ( m ) . M N

Definition 3.0.5. A module homomorphism is said to be an isomorphism if it is injective and surjective. Two modules are then isomorphic if there exists an isomorphism between them. We also have the kernel and the image, defined similarly to the vector space case. Definition 3.0.6. Let ker ϕ = { m ∈ M | ϕ ( m ) = 0 } , and im ϕ = { ϕ ( m ) | m ∈ M } . Just like before, we will omit which objects are being mapped if it is clear from context what objects we are mapping. Similarly to the vector space case, we can verify that the ker- nel and image of a module homomorphism are both modules; you may use this throughout the rest of the power round without proof. n Problem 3.0.2. Show that any finitely generated free module is isomorphic to R for some n ∈ N . We finally have the notion of a quotient module and the direct sum of modules. Definition 3.0.7. Given R − modules M , M , . . . , M , the module M ⊕ M ⊕ . . . ⊕ M , 1 2 1 2 k k L k sometimes written as M , is the set of elements { ( m , m , . . . , m ) | m ∈ M for i = i 1 2 i i k i =1 1 , 2 , . . . , k } , equipped with addition and scalar multiplication coordinate-wise. That is, ′ ′ ′ ′ ′ ′ ( m , m , . . . , m ) + ( m , m , . . . , m ) = ( m + m , m + + m , . . . , m + m ) 1 2 k 1 M 2 M k M 1 2 k 1 1 2 2 k k and r · ( m , m , . . . , m ) = ( r · m , r · m , . . . , r · m ) . 1 2 k M 1 M 2 M k 1 2 k n For instance, to get the module R , the set of tuples of length n (whose entries are n elements of R ), we can do R = R ⊕ R ⊕ . . . ⊕ R ; the addition and scalar multiplication n operations of R are precisely those that are obtained by using this direct sum procedure. Definition 3.0.8. Given two R − modules M, N, define for m ∈ M the set m + N as { m + n | n ∈ N } . Then, M/N is the module defined to be the set of elements { m + N | m ∈ M } , equipped with addition ( m + N )+( m + N ) = ( m + m )+ N and r · ( m + N ) = ( r · m )+ N, 1 2 1 2 1 1 for all m , m ∈ M and r ∈ R. 1 2 One can verify that the two above definitions are well-defined and actually give modules. For the purposes of this power round, however, you may assume these to be true. We now begin to discuss some important properties of homomorphisms. Problem 3.0.3. Given a submodule N of an R − module M, consider the map κ : M,N M → M/N that sends m to m + N. Show that this map is a surjective homomorphism. What is the kernel of κ ? M,N

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. Remember to check that the homomorphism that you construct is actually well-defined!
2. Show that M/ ker ϕ is isomorphic to im ϕ. 4 The PID Structure Theorem Although we’ve seen that modules in general can be quite complex, lacking the simplicity of vector spaces (in the sense that they aren’t generally classified by a single number), modules over PIDs are the next best case. Having built up the necessary ring and module theory over the previous sections, we are now ready to state and prove the main theorem of this power round! Theorem 4.0.1. Let R be a PID, and M be a finitely generated R − module. Then, there are positive integers k, r and nonzero elements d , d , . . . , d of R such that M is isomorphic 1 2 k to k M r R ⊕ R/ ⟨ d ⟩ . i i =1 Before we proceed onto the proof, we first need to understand some more important properties of PIDs and modules of PIDs. These properties arise in a more general class of rings, which are called Noetherian rings. The notion of being Noetherian will also be extended to modules. One of the main benefits of having this concept of Noetherian modules is that it de- scribes a certain “finiteness” condition that the module satisfies. Such a finiteness condition will allow us to conclude that certain algorithm stops, or that certain constructions (in par- ticular, having a finite set of generators) are possible, which we will find useful in the proof of the PID Structure Theorem. As such, before proceeding to the proof of the theorem, we begin by discussing Noetherian modules in general. 4.1 Noetherian Rings and Modules We first begin by introducing the notion of a Noetherian ring. Definition 4.1.1. A Noetherian ring is a ring R satisfying the following property: suppose we have a chain of ideals I ⊆ I ⊆ I ⊆ . . . . Then, there exists some n such that I = I 1 2 3 m n for all m ≥ n. We first consider some examples of a Noetherian ring.

Example. For instance, Z is a Noetherian ring. Indeed, given any ideals I ⊆ I ⊆ I . . . , 1 2 3 notice that, by Problem 1.2.3, each ideal is of the form ⟨ i ⟩ for some i. Say that I = ⟨ i ⟩ . j j Then, observe that for I ⊆ I , we need i ∈ I , or that i is divisible by i . j j +1 j j +1 j j +1 We finally observe that if no such m exists, then we can pick a subset of the ideals I , I , . . . that forms a strictly increasing chain, namely where I ⊊ I ⊊ I ⊊ . . . . To do j j j j j 1 2 1 2 3 this, one can proceed inductively: pick one ideal to start with, I . Then, by assumption, j 1 not all the ideals are equal to I ; let one such ideal be I . We can repeat this logic for I j j j 1 2 2 to get some I , and so on. j 3 But then we have an infinite sequence of integers i , i , i , . . . , where i /i is an j j j j j 1 2 3 k k +1 integer. Furthermore, since our ideal inclusions are proper, this integer cannot be 1 or − 1 , as otherwise the ideals would be equal (since − 1 ∈ Z , and an integer is a multiple of x if and only if it is a multiple of − x ). In particular, we have that | i | > | i | for each k. j j k k +1 But then | i | , | i | , | i | , . . . is an infinite sequence of decreasing positive integers, which is j j j 1 2 3 impossible. Therefore, Z is a Noetherian ring. We also have the following equivalent way of defining a Noetherian ring, as follows, which is more reminiscent of the definition of a PID. 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. As a hint, suppose that an ideal existed that was not generated by finitely many elements. Can you find an increasing chain of ideals? ∞ 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. While being a PID is a stronger condition than being Noetherian, throughout the proof of the PID Structure theorem we will find thinking about the Noetherian property to be useful. We also have the notion of Noetherian modules, which are defined with a similar char- acteristic property to that of rings. Definition 4.1.2. An R − module M is Noetherian if the following holds: for every se- quence of submodules M , M , . . . of M so M ⊆ M ⊆ . . . , there is some n ∈ N such that 1 2 1 2 M = M for all m ≥ n. m n Just like with the case of Noetherian rings, there is another, perhaps more natural way, of determining whether a module is Noetherian:

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: suppose some submodule N was not finitely generated. Then, if you pick any finite subset of N, the module that subset generates will not equal N. Keep adding elements to this finite subset; what happens?)
2. Suppose that every submodule of M is finitely generated. Prove that M is Noethe- rian. The condition of being Noetherian means we don’t have to be worried about whether submodules of our finitely generated module are also finitely generated; the condition of a module being Noetherian allows us to conclude that the submodules are Noetherian, and in particular finitely generated. We can also relate modules being Noetherian to other modules being Noetherian. 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 M,N use the previous problem). Problem 4.1.4. Prove the following.
3. Given a module M and a submodule N of M suppose that M ⊆ M are sub- 1 2 modules such that M ∩ N = M ∩ N and κ ( M ) = κ ( M ) . Show that 1 2 M,N 1 M,N 2 M = M . 1 2
4. Using the above result, show that if N and M/N are Noetherian, then M is also Noetherian. This above problems really mean that the property of being Noetherian carries over to a lot of other different modules (which in turn means we know a lot of modules are finitely generated as a result). The classification of when a module is Noetherian is particularly simple when we also have that it is a module over a Noetherian ring R.

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
3. Let N be the submodule of R consisting of tuples whose last n − m entries are n n − m all zero. Show that R /N is isomorphic to R , for positive integers n ≥ m. m Note that N is isomorphic to R ; for the purposes of this power round you do not need to prove this. n
4. Using the previous part, show that R is a Noetherian R − module for every pos- itive integer n.
5. Show therefore that if M is finitely generated, then M is a Noetherian R − module. 4.2 Smith Normal Form In this part, we apply some of the operations of row reduction and column reduction to a matrix A whose entries are in a PID R (where instead of multiplication by scalars in a field, we have multiplication by elements in R ). Throughout this subsection and the next subsection, we let R be a fixed PID. Instead of row and column operations, we have multiplication on the left and right by certain matrices, illustrated as follows. Definition 4.2.1. An n × n matrix S, whose entries are in R, is invertible if there exists an n × n matrix T such that ST = T S = I, where I is the matrix given by having 1 along the diagonal and zero elsewhere. For instance, each of the row operations from linear algebra can be viewed as multiplying 4 6 2 our matrix on the left. If we start with the matrix , we can add twice the second 1 3 5 1 2 row to the first by multiplying the matrix on the left by . By the same reasoning, 0 1 we can think of column operations as multiplying by an invertible square matrix on the right. Observe also that the product of two invertible matrices (that are the same square ′ dimension) is an invertible matrix; indeed, if S, S are invertible matrices with inverses ′ ′ ′ ′ ′ ′ ′ ′ ′ T, T , then SS ( T T ) = SIT = ST = I, and ( T T ) SS = T IS = T S = I. Now, suppose we are given an n × m matrix A (where n, m ≥ 1) whose ( i, j )th entry n P n is a . Then, in R , consider the submodule N ( A ) generated by the m elements a e , i,j i,j i i =1 n n where e , e , . . . , e is some fixed free basis of R . We are interested in R /N ( A ) . We assume 1 2 n that A ̸ = 0 first. We first show that multiplying by these invertible matrices correspond to simply per- forming changes of basis, meaning that we should have modules that are isomorphic. In particular, we have the following statements.

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). Problem 4.2.2. Suppose that we multiply A on the left by an n × n invertible matrix ′ n n ′ S to get the matrix A . Show that R /N ( A ) and R /N ( A ) are isomorphic. (Hint: what is an isomorphism between the two modules?) We also observe here that this is false if we do not scale by a unit. For instance, letting our ring R = Z and A = (1) , notice that R/N ( A ) is simply Z / Z = { 0 } , the trivial module. ′ ′ However, scaling by 2 yields A = (2) , and so R/N ( A ) = Z / 2 Z , which is not isomorphic to the trivial module. From here, we are interested in how simple a form for the matrix we are able to obtain using row and column operations. 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 1 2 r 2 r r 1 invertible matrix S such that S = for some element r ∈ R. How is r r 0 2 related to r , r ? 1 2   r 1   r 2  
2. Suppose now we have a matrix , where not all the r are zero. Show that   . i .   . r n     r r 1     r 0 2     there exists an n × n invertible matrix S such that S = , for some     . . . .     . . r 0 n r ∈ R. How is r related to 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 the previous part. Repeat, and use the fact that R is a PID, ergo Noetherian.) Using this above procedure, we are able to bring our matrix A into a diagonal form. Problem 4.2.4. Show that using row and column operations, one can reduce the matrix such that all nonzero entries lie on the diagonal (so a ̸ = 0 implies that i = j ). i,j

This is already a rather nice simplification. However, it turns out we are able to do more. There are two ways that we can further simplify our diagonal form for the matrix. 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 1 , 1 2 , 2 k,k i,i divides a for i = 2 , 3 , . . . , k. This is known as Smith normal form. i − 1 ,i − 1 So if we allow both row and column operations, we can drastically simplify A, and further- n more we get the same quotient ring for R /N ( A ) , up to isomorphism. 4.3 Proof of the PID Structure Theorem We can now use this idea of Smith normal form to prove the PID Structure theorem. Throughout this section, let M be a finitely generated R -module. Problem 4.3.1. Show that there exists a surjective map ϕ from a free module F of finite rank to M. Now, fix one such ϕ : F → M. Problem 4.3.2. Show that ker ϕ is finitely generated. Since ker ϕ is finitely generated, there is a finite set of generators w , w , . . . , w . Further- 1 2 m more, F is a free module of finite rank, so there is some free basis e , e , . . . , e . By the 1 2 n n P definition of free basis, we can write w = a e for j = 1 , 2 , . . . , m. j ij i i =1 This then suggests that we construct the matrix n × m matrix A, whose ( i, j )th entry is a . i,j Problem 4.3.3. Suppose that the only nonzero entries of A are along the diagonal (that is, a ̸ = 0 implies that i = j ). Show that M is then isomorphic to a module of i,j the form k M r R ⊕ R/ ⟨ d ⟩ , i i =1 and describe how you obtain the values d and r. i However, using the results of the previous section, we are now ready to prove the theorem. Problem 4.3.4. Prove Theorem 4.0.1, and show that a choice of d can be made such i that the d are all powers of prime elements. i 5 Applications and Asides In this section, we establish two corollaries of the PID Structure theorem, which are also interesting results in their own right. Before we do this, however, we first turn to an example where the theorem fails if our ring is not a PID.

5.1 A Counterexample This theorem that we have just proven only applies to modules of PIDs, as we see from the following. √ 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] . 5.2 Abelian Groups As a corollary, we can apply the theorem to what are known as abelian groups. We define these structures as follows. Definition 5.2.1. A abelian group is a set G equipped with an operation, + , satisfying the following conditions:

1. G is closed under + .
2. The operation + is associative and commutative: that is, for all g , g , g ∈ G, ( g + 1 2 3 1 g ) + g = g + ( g + g ) , and g + g = g + g . 2 3 1 2 3 1 2 2 1
3. The operation + has an identity element 0 .
4. Every element of G has an inverse with respect to + . Written out, for each g ∈ G, there exists an element h ∈ G such that g + h = 0 . A subgroup of a group G is a subset H of G that is a group under the same operation of H. Note that, by definition, every ring is also an abelian group, by discarding the · operation. Example. For instance, note that Z /n Z is an abelian group for any positive integer n, using the remark above, as well as Z / 2 Z × Z / 3 Z , under the addition operation. Note that Z is also an abelian group, with the set of even integers forming a subgroup. We also have the following useful notions. Definition 5.2.2. The order of an element g ∈ G is the smallest positive integer n so that g + g + . . . + g = 0 , if it exists. If it doesn’t, we say that g has infinite order. | {z } n times The order of a group G is the number of elements in the group. 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 ?

Many of the definitions and constructions that we introduced for rings and modules also carry over to abelian groups as well, such as the notion of group homomorphisms and group isomorphisms. For instance, we have that Z is an abelian group under addition, and for each positive integer n that Z /n Z is also an abelian group under addition. We observe that every element in Z /n Z has order that divides n, since if we add any element to itself n times, we get 0 . As a mild abuse of notation, in this section we will write Z , Z /n Z to mean the abelian groups with the normal addition operation, rather than considering the entire ring structure. Definition 5.2.3. A subset S of abelian group G is a set of generators for G if every element of G can be written as a finite sum of elements in S. G is finitely generated if S can be made finite. An abelian group G is cyclic if it can be generated by one element. Definition 5.2.4. Given abelian groups G , G , . . . , G , we define the abelian group 1 2 n n M G ⊕ G ⊕ . . . ⊕ G = G 1 2 n i i =1 is defined as the set of tuples { ( g , g , . . . , g ) | g ∈ G for i = 1 , 2 , . . . , n } , which we also 1 2 n i i denote as G × G × . . . × G , with addition defined as 1 2 n ′ ′ ′ ′ ′ ′ ( g , g , . . . , g ) + ( g , g , . . . , g ) = ( g + g , g + g , . . . , g + g ) . 1 2 n 1 G 2 G n G n 1 2 n 1 1 2 2 n Problem 5.2.2. Show that Z /n Z is cyclic for every positive integer n. 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?) Similarly to rings and modules, we have the notion of homomorphisms and isomorphisms of abelian groups, as follows. Definition 5.2.5. A group homomorphism is a map ϕ : G → G between groups G 1 2 1 and G such that for all g, h ∈ G, we have that ϕ ( g ) + ϕ ( h ) = ϕ ( g + h ) , where the first 2 addition is in group G and the second addition is in the group G . 2 1 An isomorphism is a bijective homomorphism. Example. As a simple example, we show that two cyclic groups that have the same finite order are isomorphic. To do this, suppose that our cyclic groups are G and G . Suppose that g is a generator 1 2 1 of G and g a generator of G . Let ϕ : G → G be the map that sends the sum of g with 1 2 2 1 2 1 itself n times to the sum of g with itself n times (for instance, ϕ ( g + g ) = g + g ). 2 1 1 2 2 Since g generates G , this specifies where ϕ sends every element of G . Furthermore, if 1 1 1 G , G both have order m, notice that g , g have order m as well. Indeed, if we consider 1 2 1 2

the sequence g , g + g , g + g + g , . . . , we will get a sequence where every element of G 1 1 1 1 1 1 1 appears, and that is periodic with period the order of g . But it will also need to be periodic 1 with the order of G , meaning that g has order m. The same logic applies for g . 1 1 2 In particular, this means that if the sum of g with itself k times equals the sum of g 1 1 with itself l times, then l − k is divisible by m. But then the sum of g with itself k times 2 equals the sum of g with itself l times (so are equal). This means that ϕ is well-defined. 2 Finally, if h is the sum of g with itself x times, then ϕ ( h + h ) equals the sum of g x 1 x y 2 with itself x + y times. But ϕ ( h ) equals the sum of g with itself x times, and ϕ ( h ) equals x 2 y the sum of g with itself y times, so ϕ ( h )+ ϕ ( h ) = ϕ ( h + h ) , and ϕ is our homomorphism. 2 x y x y We can also see that this map is bijective, since it an inverse, which we can construct using the same procedure as above but with G , G swapped. Thus, G , G are isomorphic. 1 2 1 2 In order to apply the PID Structure Theorem, we need to find an appropriate module structure. Problem 5.2.4. Show that every abelian group is a Z − module, where one of the operations is + . What is the scalar multiplication? Having given abelian groups a Z − module structure, we are now ready to apply the PID structure theorem to prove the following. Problem 5.2.5. Suppose that G is a finitely generated abelian group. Show that G is isomorphic as a group to n M r Z ⊕ Z /d Z , i i =1 for some positive integers d , d , . . . , d and nonnegative integers r, n. 1 2 r 5.3 Jordan Canonical Form As a second, significantly less straightforward application of the PID structure theorem, we have a way to find a relatively simple matrix for a linear transformation T from a finite dimensional vector space V to itself. In this particular case, we specify a single basis for V, and use this basis to represent the matrix of T : V → V. First, we will see how we can apply the PID structure theorem to obtain an interest- ing result, and then from there convert the result from the PID structure theorem into a statement about the linear transformation T. To begin, given a linear transformation T on V, we will once again try to find a module structure. We already have the addition operation and scalar multiplication by C , from the definition of a vector space. n P i Problem 5.3.1. Show that V is a C [ x ] − module, where for a polynomial p ( x ) = a x i i =0 n P i we define p ( x ) · v = a T v for each v ∈ V. i i =0

Since we know that C [ x ] is a PID, we can apply the PID structure theorem. Because we also have that V is a finite-dimensional vector space, we are actually able to say something a little bit stronger. 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 1 2 n 1 2 n will need the Fundamental Theorem of Algebra (see Problem 1.1.5). r i Our goal is to now understand how T behaves on the vector space C [ x ] / ( x − λ ) . Let i L n r i ϕ be the map from V to C [ x ] / ( x − λ ) . 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 i 1 2 r i T v = λ v , and for j = 2 , 3 , . . . , r , we have that T v = λ v + v , and that 1 i 1 i j i j j − 1 v , v , . . . , v are linearly independent. 1 2 r i
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. From here, we are ready to prove the following. 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 1 2 n matrix form   J 0 · · · 0 1   0 J · · · 0 2   ,   . . . . . . . .   . . . . 0 0 · · · J k 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 i is known as the Jordan canonical form for a linear transformation/matrix.

For the block matrix form, one can think of a matrix as being divided up into rectangles,   1 0 0 0   2 1 0 0   and then viewing those rectangles as “blocks.” For instance, in the matrix ,   0 0 5 − 4 0 0 1 2 A 0 we can think of this matrix as having block matrix , where A is the 2 × 2 matrix 0 B 1 0 5 − 4 and B is the 2 × 2 matrix . We also think of the 0s in the block form as 2 1 1 2 the zero matrices, rather than simply the number zero.

Team Number: PUMaC 2022* Power Round Cover Sheet Remember that this sheet comes first in your stapled solutions. You should submit solutions for the problems in increasing order. Write on one side of the page only. The start of a solution to a problem should start on a new page. Please mark which questions for which you submitted a solution to help us keep track of your solutions. Problem Number Points Attempted? Problem Number Points Attempted? 1.1.1 15 2.4.4 30 1.1.2 5 2.4.5 10 1.1.3 5 2.4.6 10 1.1.4 5 2.4.7 25 1.1.5 10 2.4.8 20 1.1.6 5 3.0.1 5 1.2.1 10 3.0.2 15 1.2.2 5 3.0.3 10 1.2.3 10 3.0.4 20 1.2.4 10 4.1.1 30 1.2.5 10 4.1.2 25 1.3.1 10 4.1.3 15 1.3.2 10 4.1.4 25 1.3.3 25 4.1.5 40 1.3.4 10 4.2.1 10 2.1.1 10 4.2.2 15 2.1.2 10 4.2.3 20 2.2.1 10 4.2.4 25 2.2.2 20 4.2.5 30 2.2.3 10 4.3.1 10 2.2.4 10 4.3.2 5 2.2.5 20 4.3.3 40 2.2.6 5 4.3.4 30 2.2.7 10 5.1.1 25 2.3.1 15 5.2.1 25 2.3.2 5 5.2.2 10 2.3.3 15 5.2.3 15 2.3.4 10 5.2.4 20 2.3.5 15 5.2.5 15 2.3.6 10 5.3.1 15 2.4.1 15 5.3.2 10 2.4.2 10 5.3.3 30 2.4.3 15 5.3.4 10