Lecture 21 Notes: Smith Normal Form

Lecture 21: Modules 21 21.1 Smith Normal Form Review Last time, we looked at presentation matrices for a module. We saw that if we perform elementary row and column operations on the presentation matrix, then this leads to an isomorphic module. We then stated the theorem that we can use such operations to reduce any matrix to Smith normal form. We will prove this today; but first, let’s look at a few examples. 21.2 Some Examples in Z We’ll consider the case of 2 × 2 matrices over Z — consider the presentation matrix   a c B= , b d whose corresponding module is MB = Z2 / Span((a, b)t , (c, d)t ). The simplest case is when B is diagonal: Example 21.1 Consider the presentation matrix In this case, we have  2 B= 0  0 . 3 MB ∼ = Z/2Z ⊕ Z/3Z, since given any vector (m, n), its coset mod Span((2, 0)t , (0, 3)t ) is just given by taking the first component mod 2 and the second mod 3. (To be pedantic, the isomorphism is given by (m, n) 7→ (m mod 2, n mod 3) — given any vector, we can subtract multiples of our two vectors to bring it into the rectangle.) Example 21.2 Consider the presentation matrix B=  5 0  0 . 1 Now the corresponding module is MB = Z/5Z — the second coordinate is “useless” since we’re allowed to subtract multiples of (0, 1)t , so we can always eliminate it. So to keep track of the coset of a vector, we only need to keep track of the first component mod 5. Now we’ll look at a more complicated example, where the original matrix is not diagonal. Example 21.3 Consider the presentation matrix  2 B= 1 95  1 . 3 Lecture 21: Modules w v We can see det(B) = 5, so we can use elementary column operations to make one column a multiple of 5 — if we add twice the first column to the second, then we get     1 2 2 5 ′ B =B = . 0 1 1 5 So we’ve replaced w with w′ = 5(1, 1)t , without changing the lattice spanned by our vectors: w′ v But (2, 1)t and (1, 1)t form a basis for Z2 ! So this means to get our lattice, we started with a basis for Z2 , then fixed one of the basis vectors and scaled the other by 5. So this is isomorphic to the previous example — by changing the basis we use for Z2 , we can rewrite v and w′ as (1, 0)t and (0, 5)t . So we have MB ∼ = Z/5Z. 21.3 Smith Normal Form Now we’ll return to the general case, and prove the theorem. Theorem 21.4 For a Euclidean domain R, any n×m matrix B can be reduced using elementary row and column operations to a matrix D, where dij = 0 for all i ̸= j, and d11 | d22 | · · · . One example of a matrix written in this form (which  2 D = 0 0 is called Smith normal form) is  0 0 0 6 0 0 . 0 12 0 Note that if D can be obtained from B by elementary row and column operations, then we can write D = ABC, where A is an invertible n × n matrix and C is an invertible m × m matrix. For any such D, we then have MD ∼ = MB . Note 21.5 In a PID, it’s still possible to obtain D in Smith normal form with D = ABC (for A and C invertible). However, it may not be possible to obtain D by using the elementary operations. 96 Lecture 21: Modules To motivate the proof, notice that the greatest common divisor of all the matrix entries does not change under elementary operations — it’s clear that scaling by a unit doesn’t change the gcd; meanwhile if we perform the operation aij 7−→ aij + cakj , we have gcd(aij , akj ) = gcd(aij + cakj , akj ). (This is the same idea as in the Euclidean algorithm.) So if we are able to obtain a matrix D in Smith normal form, then we must have d11 = gcd(bij ) (since d11 divides all other entries of D). So this suggests the main idea of the proof — we want to run some sort of Euclidean algorithm in order to isolate the gcd of all matrix entries in the top-left corner. Proof of Theorem 21.4. Recall that in a Euclidean domain, we have a size function σ : R \ {0} → Z≥0 such that we can divide with remainder — given any a and b, with b ̸= 0, we can write a = bq + r where r = 0 or σ(r) < σ(b). For convenience, we write |a| instead of σ(a). If B = 0, we are done, so assume B ̸= 0. Then we’ll use induction on the size of the matrix; the key step is the following. Lemma 21.6 By row and column operations, we can arrive at a matrix B ′ such that b′11 = gcd(bij ) = gcd(b′ij ). Proof. By permuting the rows and columns, we can ensure that b11 ̸= 0, and b11 is the nonzero element of minimal size. Now if b11 | bij for all i and j, then we’re done, so assume not. Now the main idea is to modify the matrix to make a smaller element appear (which we can again move to the top-left corner by rearranging rows and columns). First, if there is an entry with b11 ∤ bij in the first row or column, then we can perform a row or column operation to reduce it — if bij = qb11 + r, then we can subtract q times the first row or column from the row or column of bij , which replaces bij with r. If not, then we can use b11 to eliminate all other entries in the first row and column (by subtracting multiples of the first column and row), to get a matrix of the form   b11 0 · · · 0  0 ∗ · · · ∗    .. .. . . ..  .  . . . . 0 ∗ ··· ∗ Now there must be some bij with b11 ∤ bij . We can add its row to the first row; this adds 0 to b11 , so we now have a matrix   b11 ∗ bij · · · ∗  0 ∗ ∗ · · · ∗    0 ∗ ∗ · · · ∗  .  .. .. .. ..  ..  . . . . . 0 ∗ ∗ ··· ∗ Then we can again add a multiple of the first column to the jth column in order to produce an entry with smaller size. So either way, we’ve now produced a matrix with an element smaller in size than b11 . Now permute the rows and columns to move this element to the position of b11 . Then we repeat the process. At every step, we replace b11 with a nonzero entry of smaller size. Since the size is always a nonnegative integer, at some point this process must terminate; this means that b11 now divides all entries. To complete the proof of Theorem 21.4, we induct on the size of B. By Lemma 21.6, we can replace B with a matrix B ′ where b′11 divides b′ij for all i and j. 97 Lecture 21: Modules Now using row and column operations, we can eliminate the first row and b′1j all zero). So we get   ′  ′ b11 ∗ · · · ∗ b11 0 · · ·  ∗ ∗ · · · ∗  0 ∗ ···     .. .. . . .  ⇝  .. .. . .  .  . . ..  . . . ∗ ∗ ··· ∗ 0 ∗ ··· and column (meaning that we make b′i1  0 ∗  ..  . . ∗ Now we ignore the first row and column, and use elementary operations on rows and columns 2, . . . , n. (These do not affect the first row or column.) By the induction assumption, we can reduce the submatrix of ∗s to Smith normal form (since b′11 already divides all other entries, this will remain true when we perform the operations). The theorem has more theoretical value than computational value, but we will compute an example nonetheless. Example 21.7 We have Example 21.8 We have  4 1 21.4  2 1 2 2   6 1 ⇝ 3 4 2 2   1 1 ⇝ 3 2      3 1 3 1 0 ⇝ ⇝ . 1 0 −5 0 −5       3 1 0 0 1 0 0 1 0 ⇝ ⇝ ⇝ 6 4 −6 −6 0 −6 −6 0 −6  0 . 0 Applications As a corollary, by taking R to be Z, we can classify all finitely presented abelian groups. Corollary 21.9 Every finitely presented abelian group is isomorphic to Z/d1 Z × Z/d2 Z × · · · × Z/dn Z × Za , for some positive integers di with d1 | d2 | · · · | dn . Sometimes, it’s more useful to write this classification in a different form. Recall that the Chinese Remainder Theorem states that if n = ab with gcd(a, b) = 1, then Z/nZ ∼ = Z/aZ × Z/bZ. So then if we factor di = pa1 i1 · · · panin , we can decompose Z/di Z as a product of groups of the form Z/pm Z (cyclic groups of prime power order). Another application of Theorem 21.4 is in the case R = F [x], where F is a field. A finitely generated module over R must then be of the form Ra ⊕ R/(P1 ) ⊕ · · · ⊕ R/(Pn ), where P1 | · · · | Pn . Alternatively, again using the Chinese Remainder Theorem, we can instead assume that each Pi is a power of an irreducible polynomial. In particular, consider F = C; then the only irreducible polynomials are linear, so we must have Pi = (x − λi )ni . If we only consider finite-dimensional modules, then as we said earlier, a module over F [x] is equivalent to a (finite-dimensional) vector space along with one linear operator (corresponding to the action of x). So it turns out that this classification of modules actually implies the Jordan decomposition theorem — we will discuss this in more detail next lecture. 98