Let \(w_1, \dots, w_n\) be any list of distinct elements of \(I \cup \{v\}\) and suppose that \(\sum_i c_i w_i = 0\) for some \(c_i \in F\). If none of the \(w_i\)'s is equal to \(v\), then \(c_i = 0\) for all \(i\), since \(I\) is linearly independent. Without loss of generality, say \(w_1 = v\). If \(c_1 = 0\) then \(c_i = 0\) for all \(i\) by the same reasoning as in the previous case. If \(c_1 \ne 0\), then

contrary to assumption. This proves that \(I \cup \{v\}\) is a linearly independent set.

For this first part, apply the theorem with \(I = \varnothing\) and \(S = V\). For the second and third, use \(I\) arbitrary and \(S = V\) and \(I = \varnothing\) and \(S\) arbitrary, respectively.

Let \(\mathcal{P}\) denote the collection of all subsets \(X\) of \(V\) such that \(I \subseteq X \subseteq S\) and \(X\) is linearly independent. We make \(\mathcal{P}\) into a poset by the order relation given by set containment \(\subseteq\). We note that \(\mathcal{P}\) is not empty since, for example \(I \in \mathcal{P}\).

Let \(\mathcal{T}\) be any nonempty chain in \(\mathcal{P}\). Let \(Z = \bigcup_{Y \in \mathcal{T}} Y\). We claim \(Z \in \mathcal{P}\). Given \(z_1, \dots, z_m \in Z\), for each \(i\) we have \(z_i \in Y_i\) for some \(Y_i \in T\). Since \(T\) is totally ordered, one of \(Y_1, \dots, Y_m\) contains all the others and hence contains all the \(z_i\)'s. Since \(Y_i\) is linearly independent, this shows \(z_1, \dots, z_m\) are linearly independent. Thus \(Z\) is linearly independent. Since \(\mathcal{T}\) is non-empty, \(Z \supseteq I\) and hence \(Z \in \mathcal{P}\). It is an upper bound for \(\mathcal{T}\) by construction.

By Zorn's Lemma, \(\mathcal{P}\) has a maximal element \(B\), which we claim is a basis for \(V\). Note that \(B\) is linearly independent and \(I \subseteq B \subseteq S\) by construction. We need to show that it spans \(V\). Suppose not. Since \(S\) spans \(V\), if \(S \subseteq \mathrm{span}(B)\), then \(\mathrm{span}(B)\) would have to be all of \(V\). So, there is at least one \(v \in S\) such that \(v \notin \mathrm{span}(B)\), and set \(X := B \cup \{v\}\). Clearly, \(I \subset X \subseteq S\) and, by Lemma 12.1.1, \(X\) is linearly independent. This shows that \(X\) is an element of \(\mathcal{P}\) that is strictly bigger than \(B\), contrary to the maximality of \(B\).

Apply Theorem 12.1.2 with \(B = I\) and \(S = V\). Since \(B\) is a basis of \(W\), \(B\) is linearly independent, and \(B\) remains linearly independent when regarded as a subset of \(V\).

First we show we can swap out one element of \(B\) for one nonzero element \(\{v\}\). In this case, we will show the stronger statement that for any subset \(B_0 \subseteq B\), and any element \(a\notin \mathrm{span}(B_0)\), there is some \(b\in B\smallsetminus B_0\) such that \(B\smallsetminus \{b\} \cup \{v\}\) is a basis for \(V\).

Since \(B\) is a basis, we can write

for some elements \(b_i \in B\). Since \(v\notin \mathrm{span}(B_0)\), we have \(\lambda_i\neq 0\) for some \(b_i\notin B_0\); say \(\lambda_1\neq 0\). We claim that \(B' := B\smallsetminus \{ b_1\} \cup \{v\}\) is a basis.

\(B'\) is linearly independent: By Lemma 12.1.1, it suffices to show that \(v\notin \mathrm{span}(B\smallsetminus \{b_1\})\). Indeed, if it were, then writing \(v\) as a linear combination of \(B\smallsetminus \{b_1\}\) and the linear combination \(v = \sum_i \lambda_i b_i\) with \(b_1\neq 0\) would give two different expressions of \(v\) in the basis \(B\), a contradiction.

\(B'\) spans \(V\): First, we note that it suffices to show that \(b_1\) in the span of \(V\): once we have shown this, we can write any element of \(V\) as a linear combination of elements of \(B\), and just replace the term with \(b_1\) with a linear combination of elements of \(B'\) by substituting. To this end, by the contrapositive of Lemma 12.1.1, it suffices to show that \(B' \cup \{b_1\}\) is not linearly dependent, and our starting expression \(v = \sum_i \lambda_i b_i\) does this.

Consider the collection of pairs \((I', A')\) with \(I' \subseteq I\), \(A' \subseteq A\), and \(|I'|=|A'|\) with the property that \(B\smallsetminus A' \cup I'\) is a basis for \(V\). By a Zorn's Lemma argument (left as an exercise), there is a maximal such pair under the partial order \((I',A')\leq (I'',A'')\) if \(I'\subseteq I''\) and \(A'\subseteq A''\). Let \((I_0,A_0)\) be a maximal element. We will argue that \(I_0=I\).

To obtain a contradiction, suppose otherwise, and let \(a\in I \smallsetminus I_0\). Apply the special case above to the basis \((B\smallsetminus A_0) \cup I_0\) and special subset \(I_0\): since \(I\) is linearly independent, \(a\notin \mathrm{span}(I_0)\). Then by the special case, there is some \(b\in B\smallsetminus A_0\) such that \( B\smallsetminus (A_0 \cup \{b\}) \cup (I_0 \cup \{a\})\) is a basis. This contradicts the maximality of \((I_0,A_0)\), so we deduce that \(I_0=I\) as required.

Let \(\varphi\!:\mathrm{Hom}_R(V, W) \to \mathrm{Mat}_{m,n}(R)\) be defined by \(\varphi(f)=[f]_B^C\). We need to check that \(\varphi\) is a homomorphism of \(R\)-modules, which translates into \([f+g]_B^C=[f]_B^C+[g]_B^C\) and \([\lambda f]_B^C=\lambda[f]_B^C\) for any \(f,g \in \mathrm{Hom}_R(V, W)\) and \(\lambda\in R\). Let \(A=[f]_B^C\) and \(A'=[g]_B^C\). Then

gives \([f+g]_B^C=A+A'\) and

gives \([\lambda f]_B^C=\lambda A\). We leave the proof that for \(f,g\in \mathrm{End}_R(V)\) we have \([f\circ g]_B^B=[f]_B^B[g]_B^B\) as an exercise.

Finally, the argument described in Example 12.2.6 also works for any ring \(R\), and it can be adapted for any two chosen basis \(B\) and \(C\), showing that \(\varphi\) is a bijection.

The isomorphism \(\mathrm{Hom}_F(V, W) \cong \mathrm{Mat}_{m,n}(F)\) gives

Let \(v\in V\) and write \([v]_B = (r_1,\dots,r_n)\), so \(v=\sum_j r_j b_j\). Write \([f]_B^C=[a_{i,j}]\). Then

Thus the \(i\)-th entry of \([f(v)]_C\) is \(\sum_j a_{i,j} r_j\). On the other hand, multiplying out \([f]_B^C \cdot [v]_B = [a_{i,j}](r_1,\dots,r_n)\), the \(i\)-th entry is also \(\sum_j a_{i,j} r_j\).

It suffices to check that \([g\circ f]_B^D \cdot p=[g]_C^D \cdot [f]_B^C \cdot p\) for any \(p\in R^n\) where \(n=\mathrm{rank}(V)\). (In fact, we can just take \(p=e_j\) for each \(j\), since \(Ae_j\) is the \(j\)th column of \(A\).) We can write \(p=[v]_B\) for some \(v\in V\). Then

Since \(f=\mathrm{id}_W\circ f\circ \mathrm{id}_V\), by Lemma 12.3.3 we have

Now set \(V=W,B=C,B'=C'\) and \(f=g\) in the displayed equation to obtain

1. By definition, the \(j\)-th column of \([\mathrm{id}]_{B'}^B\) gives the coefficients for \(b'_j\) as a linear combination of the elements of \(B\). In each case, we check that the matrix \(E\) agrees with the specified combinations in the definition of the basis operation.
2. It suffices to check this for a row vector, since the \(i\)-th row of \(BE\) can be computed as the \(i\)-th row of \(B\) multiplied by \(E\). Then one can verify this by case-by-case multiplication.
3. Similar to (2).

First, we consider the case of the transposition \((1\, 2)\). Note that

so \(\phi(v_2, v_1,\dots,v_n) = - \phi(v_1, v_2,\dots,v_n)\). The case of an arbitrary transposition follows in the same way. For an arbitrary permutation \(\sigma\), we can write \(\sigma\) as a product of \(t\) transpositions for some \(t\). Applying the case of one transposition \(t\) times yields

The verification that \(\det\) has these properties is straightforward but messy. To show uniqueness, we can use multlinearity to show that the value of a function with these properties is determined by the values when each column is a standard vector \(e_i\). We can then use the alternating property and Lemma 12.4.4 to show that the value is determined by the value at the identity matrix.

The first case follows from multilinearity and alternating properties: For notational simplicity say \(A = (v_1, v_2, \dots)\) and \(B = (v_1 + rv_2, v_2, \dots)\). Then

The second case is immediate from (the second part of) \(R\)-multilinearity. The last case is a special case of Lemma 12.4.4.

The final claim comes from noting that \(\det(E)=1,u,-1\) in the three cases, respectively.

If \(A\) is not invertible, then the span of the columns of \(A\) is a proper subspace of \(F^n\) and hence the columns of \(A\) must be linearly dependent. Say the \(i\)-th column is a linear combination of the rest: \(v_i = \sum_{j \ne i} c_j v_j\). Then

If \(A\) is invertible, then we can write \(A\) as a product of elementary matrices (this is a result that we stated before, but will prove soon). The result thus follows from the Proposition 12.4.6 and the fact that \(\det(I_n) = 1\).

First we will consider the case where \(R=F\) is a field.

If \(A\) is not invertible, neither is \(AB\), since \(\mathrm{im}(AB) \subseteq \mathrm{im}(A)\), and if \(B\) is not invertible, neither is is \(AB\), since \(\ker(AB) \supseteq \ker(A)\). So, by the Proposition 12.4.6, if either \(A\) or \(B\) is not invertible, both sides of the equation are \(0\).

Assume now that \(A\) and \(B\) are both invertible. Then by the Proposition 12.4.6 we have

and

and hence

where the \(E_i\)'s and \(F_j\)'s are elementary matrices.

Applying Corollary 12.4.7 repeatedly gives

and similarly

Now, for an integral domain \(R\), consider its fraction field \(F\), and identify \(R\subseteq F\) as a subring. To compute \(\det(A)\), \(\det(B)\), and \(\det(AB)\) we can replace \(R\) by \(F\), and are done by the field case.

One can apply a similar trick for arbitrary commutative rings, but we'll skip this for now.

Let \(a_1,\dots,a_m\) be the columns of \(A\). We can write the \(j\)-th column of \(AB\) as \(\sum_{i=1}^m b_{i,j} a_i\). Then, by multilinearity,

By the alternating property, we can rewrite each \(\det\begin{bmatrix} a_{i_1} & \cdots & a_{i_n} \end{bmatrix}\) as either zero, or the determinant of a submatrix with columns \( i_1 < i_2 < \cdots < i_n \), up to sign. This gives \(\det(AB)\) as an \(R\)-linear combination of the determinants \(\det(A_I)\).

Let \(S\) be a generating set for \(M\), and let \(F= F_R(S)\) be the free module with basis \(S\). By the UMP for free modules, there is a unique homomorphism \(\phi\) such that for each \(s\in S\), \(\phi(s) =s\). Since \(S\) generates \(M\), this map is surjective by an Exercise from earlier.

Let \(K=\ker(\phi)\), and let \(S'\) be a generating set for \(K\). Set \(G=F_R(S')\) to be the free module with basis \(S'\). By the UMP for free modules again, there is a unique \(\alpha\colon G\to F\) such that for each \(s'\in S'\), \(\alpha(s') =s'\). We claim that \(\mathrm{im}(\alpha) = K\) (left as an exercise).

Thus, the First Isomorphism Theorem, \(M\cong F/K = F/\mathrm{im}(\alpha)\).

We will first prove that for each \(n \geqslant 1\), every submodule of \(R^n\) is finitely generated. The base case \(n=1\) holds by the definition, since a submodule of \(R^1\) is the same thing as an ideal of \(R\), and every ideal is generated by one element. Assume \(n > 1\) and that every submodule of \(R^{n-1}\) is finitely generated. Let \(M\) be any submodule of \(R^n\). Define

to be the projection onto the last component of \(R^n\). The kernel of \(\pi\) may be identified with \(R^{n-1}\), and so \(N := \ker(\pi) \cap M\) is a submodule of \(R^{n-1}\). By assumption, \(N\) is finitely generated. The image \(\pi(M)\) is a submodule of \(R^1\), that is, an ideal of \(R\), and so it too is principal. Furthermore, by the First Isomorphism Theorem \(M/\ker(\pi)\cong \pi(M)\). By the Exercise above, we deduce that \(M\) is a finitely generated module.

Now let \(T\) be any finitely generated \(R\)-module and \(N \subseteq T\) any submodule. Since \(T\) is finitely generated, there exists a surjective \(R\)-module homomorphism \(q\!: R^n \twoheadrightarrow T\) for some \(n\). Then \(q^{-1}(N)\) is a submodule of \(R^n\) and hence it is finitely generated by the case we already proved, say by element \(v_1, \dots , v_m \in q^{-1}(N)\). We claim that \(q(v_1), \dots, q(v_m)\) generate \(N\). Given any \(a \in N\), since \(q\) is surjective we can find some \(b \in q^{-1}(N)\) such that \(q(b) = a\). Since \(v_1, \ldots, v_m\) generated \(q^{-1}(N)\), we can find \(c_1, \ldots, c_m \in R\) such that

Let \(M\) be a finitely generated module over a PID. We follow the argument of Theorem 13.2.1. Choose a finite generating set \(y_1, \dots y_m\) of \(M\) and obtain an \(R\)-module map \(\pi\!: R^m \to M\) that sends \(e_i\) to \(y_i\), by using the UMP for free modules. Since every element in \(M\) is given as a linear combination of the \(y_i\), the map \(\pi\) is surjective. Notice, however, that this representation as a linear combination of the \(y_i\) is not necessarily unique, so \(\pi\) might have a nontrivial kernel.

Since \(R^m\) is finitely generated and \(R\) is a PID, the submodule \(\ker(\pi)\) is also finitely generated, say by \(z_1, \dots, z_n\). This too leads to a surjective \(R\)-module map \(g\!: R^n \to \ker(\pi)\) that sends \(e_i \mapsto z_i\). The composition of \(g\!: R^n \twoheadrightarrow \ker(\pi)\) followed by the inclusion of \(\iota\!: \ker(\pi) \hookrightarrow R^m\) is an \(R\)-module homomorphism \(t=\iota \circ g:R^n \to R^m\) and hence by the correspondence between matrices and homomorphisms, we know \(t\) is given by a \(m \times n\) matrix \(A=[t]_B^C\) with respect to the standard bases of \(R^m\) and \(R^n\) respectively, meaning \(t=t_A\).

It remains to show that \(M\cong R^m/\mathrm{im}(t_A)\). First note that since \(t_A=\iota \circ g\) and \(g\) is surjective we have

By the First Isomorphism Theorem we now have

Existence:

By Theorem 13.2.3, \(M\) has a presentation matrix \(A\). By Theorem 13.3.1, \(A\) can be put into Smith Normal Form \(B\), where the diagonal entries of \(B\) are \(b_1, \ldots, b_\ell\) and satisfy \(b_1 \mid b_2 \mid \cdots \mid b_k\). Moreover, \(k\) is unique and the \(d_i\) are uniquely determined up to associates (ie, up to multiplication by units) by \(A\), hence by \(B\). By Theorem 13.2.3, \(M\) is isomorphic to the module presented by \(B\). By Lemma 13.3.2, this is isomorphic to

Finally, some of these \(b_i\) might be units; let \(d_1 \mid \cdots \mid d_k\) be the nonunits among the \(b_i\), and note that if \(u\) is a unit, then \(R/(u) \cong (0)\). We conclude that

as desired.

Uniqueness:

For uniqueness, we show by induction on \(\max\{k,k'\}\) that if \[M = R^r \oplus R/(d_1) \oplus \dots \oplus R/(d_k) \cong N= R^{r'} \oplus R/(d'_1) \oplus \dots \oplus R/(d'_{k'})\] with \(d_1 | \cdots | d_k\) and \(d'_1 | \cdots | d'_{k'}\), then \(r=r'\), \(k=k'\), and \(d_i\) and \(d'_i\) are associates for all \(i\). If \(k=k'=0\) then this follows from invariance of rank for free modules over commutative rings, which you proved in the homework. If \(k>0\), then consider the element \(m=\iota(1+(d_k))\in M\) and let \(n=\iota(1+(d'_{k'}))\in N\). Note that \(\mathrm{ann}_R(m)= (d_k)\), and since \(\phi\) is an isomorphism, we also have \(\mathrm{ann}_R(\phi(m))= (d_k)\). On the other hand, any element of \(N\) with nonzero annihilator must have \(R^{r'}\) component zero, and must then be annihilated by \(d'_{k'}\). It follows that \(d'_{k'}\in (d_k)\), so \(d_k \ | \ d'_{k'}\). Switching roles, we must also have \(d'_{k'} \ | \ d_k\), so \(d_k\) and \(d'_{k'}\) are associates. Now, we claim that there is an \(R\)-module isomorphism \(\psi: N \to N\) such that \(\psi(\phi(m)) = n\) (left as exercise). It follows that \(\psi \circ \phi: M\to N\) is an isomorphism and \(\psi\circ \phi(\iota(R/(d_k))) = \iota(R/(d'_{k'}))\). We get an induced isomorphism \[ R^r \oplus R/(d_1) \oplus \dots \oplus R/(d_{k-1}) \cong M/ \iota(R/(d_k)) \cong N/ \iota(R/(d'_{k'})) \cong R^{r'} \oplus R/(d'_1) \oplus \dots \oplus R/(d'_{k'-1}).\] It then follows from the induction hypothesis that \(r=r'\), \(k=k'\), and \(d_i\) and \(d'_i\) are associates for \( i\lt k \). Since we already saw that \(d_k\) and \(d'_{k'}\) are associates, the induction is complete.

First, write \(M\) in invariant factor form \(M \cong R^r \oplus R/(d_1) \oplus \dots \oplus R/(d_k)\). Then write each invariant factor as a product of prime powers

and recall that by the CRT we have

Substituting into the invariant factor form gives the desired result. Uniqueness follows from the uniqueness of the invariant factor form and of the prime factorizations of each \(d_i\).

We first prove part (1). Let \(g\) be a gcd of \(x\) and \(y\), so \((x,y) = (\gcd(x,y))\). Thus, there exist \(a, b \in R\) such that \(ax+by = g\). Since \(g\) divides \(x\), we can write \(x=g x'\) for some \(x'\in R\), and likewise we can write \(y=gy'\) for some \(y'\in R\). Then \(a g x' + b g y' = g\), and since \(R\) is a domain, \(a x' + b y' =1\). Set \(P= \begin{bmatrix} a & b \\ -y' & x' \end{bmatrix}\). Then \(P \begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} g & 0\end{bmatrix}\), since \(-y' x + x' y = g(-y' x' + x' y') = 0\). To check that \(P\) is invertible, we claim that \(P^{-1} = \begin{bmatrix} x' & -b \\ y' & a\end{bmatrix}\), which can be checked directly by multiplying this matrix on both sides with \(P\).

We now prove part (2). Let \(N\) be a Euclidean norm for \(R\). We proceed by induction on \(M= \min\{N(x),N(y)\}\). If \(M=0\) then either \(x\) or \(y\) has norm zero and hence is a unit. Swapping rows if necessary (which is an elementary operation), we can assume \(x\) is a unit, and hence the GCD of \(x\) and \(y\). Then

For the inductive step, again swapping if necessary, we can assume that \(N(x)\geq N(y)\). By the division algorithm, we can write \(x=qy+r\) with either \(r=0\) or \(N(r) \lt N(y)\). Note that the GCD \(g\) of \(x\) and \(y\) is equal to the GCD of \(y\) and \(r\). We have

If \(r=0\) we are done; otherwise we can apply the induction hypothesis to find some product of elementary matrices \(P\) such that

Then \(\begin{bmatrix} 1 & -q \\ 0 & 1\end{bmatrix} P\) is the product we seek.

We show the existence of such matrices \(P\), \(Q\) in steps.

Proof of existence: To construct \(P,Q\), we note first that it suffices to show the following:

Key Claim: Given a matrix \(A\), there exist invertible (products of elementary matrices, if \(R\) is Euclidean) \(P',Q'\) matrices such that

with \(d_1=\gcd(A)\) and the \(0\)'s denote a row and column of zeroes.

Indeed, once we have shown this, note that \(d_1\) divides every entry of \(B\), so \(d_1 \ | \ \gcd(B)\). Then we can apply the claim to get

where \(d_2= \gcd(B_1)\) and \(d_1 \ | \ d_2 \ | \ \gcd(B_2)\). Repeating this process ends in a matrix of the form we seek.

Proof of Key Claim, case 1: In the setting of the key claim, suppose that \(d_1= \gcd(A)\) occurs as some entry of \(A\). After swapping rows and columns (which corresponds to multiplication by elementary matrices), we can assume that \(d_1\) is the top left entry of \(A\). Now, every element of the first row and the first column (and every entry!) is a multiple of \(d_1\), so we can subtract a suitable multiple of row one from each row (which corresponds to multiplication by elementary matrices) to get zeroes in the other entries of the first row. After that, do the same with the columns. Then we are done.

Proof of Key Claim, case 2: Without assuming that \(d_1=\gcd(A)\) occurs as an entry of \(A\), choose an entry \(a\) of \(A\) for which the number of irreducible factors of \(a/d_1\) is minimal. We proceed by induction on the number of such factors; the base case where this number is zero is case 1 above. Using row and column operations, we can put \(a\) in the top left entry.

If \(a\) does not divide some entry \(b\) of the first row, use a column operation to put \(b\) in the \(1,2\) position. Using the Lemma, we can multiply by a suitable matrix to replace \(a,b\) by \(\gcd(a,b)\) and \(0\). Since \(a\) does not divide \(b\) and \(d_1 \ | \ \gcd(a,b) \ | \ a\), the number of irreducible factors of \(\gcd(a,b)/d_1\) must be strictly less than that of \(a/d_1\). We can then apply the induction hypothesis.

A similar argument applies if \(a\) does not divide some entry of the first column.

If \(a\) does divide every entry of the first row and first column, proceed as in case 1 to clear out the rest of the first row and column, and then add a row containing an entry \(b\) that does not divide \(a\) to the first row. Then proceed as in the first part of this case.

Proof of uniqueness: For a matrix of the form \(D\), the only minors that are nonzero are those where the choices of columns and rows are the same, and hence the only nonzero \(t \times t\) minors of \(M\) are \(d_{s_1} \cdots d_{s_t}\) for some \(s_1 < \cdots < s_t\). Since \(d_{s_1} \cdots d_{s_t}\) divide each other, it follows that \(I_t(A) = I_t(D) = d_1 \cdots d_t\). This proves uniqueness, for it shows that \(d_1, \dots, d_{\ell}\) are all defined from \(A\) directly, without any choices.