Every square matrix over a Euclidean domain can be diagonalized by elementary row and column operations

Show that if A is a matrix over a Euclidean domain R, then there is a sequence of elementary row and column operations (as described here and here) which, when performed on A, result in a matrix \begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix} such that D = [d_{i,j}] is square and diagonal and if d_{1,1},\ldots, d_{k,k} are the nonzero diagonal entries of D (k \leq n), we have d_{i,i} | d_{j,j} whenever i \leq j.

Conclude that if M is a finitely generated R-module with relations matrix A (see here for a discussion of relations matrices) then M \cong R^{n-k} \oplus \bigoplus_{i=1}^k R/(d_i).


Let N : R \rightarrow \mathbb{N} denote the Euclidean norm on R.

Note first that if A = 0, there is nothing to show. If A \neq 0, we proceed by induction on the number m of rows of A.

For the base case m = 1, say A = [a_{1,1}\ a_{1,2}\ \cdots\ a_{1,n}]. If n = 1 there is nothing to show, so we assume n \geq 2. We now proceed by induction on \sum_{i=2}^n N(a_{1,i}). For the base case, if \sum_{i=2}^n N(a_{1,i}) = 0, then a_{1,i} = 0 for each 2 \leq i \leq n, and so A = [a_{1,1} | 0] has the desired form. For the inductive step, suppose that for all 1 \times n matrices B = [b_{1,1}\ b_{1,2}\ \cdots\ b_{1,n}] such that \sum_{i=2}^n N(b_{1,i}) \leq K, B can be diagonalized by some sequence of elementary row and column operations. Now suppose \sum_{i=2}^n N(a_{1,i}) = K+1. Using column operation 1 (swap two columns), rearrange the columns of A so that a_{1,1} has minimal norm. By the Division Algorithm, there exist q_i and r_i such that a_{1,i} = q_ia_{1,1} + r_i and either r_i = 0 or N(r_i) < N(a_{1,1}) for each 2 \leq i \leq n. Using column operation 2 (add a multiple of one column to a different one) n-1 times, one for each column after the first, we can put A in the form [a_{1,1}\ r_2\ \cdots\ r_n]. Now \sum_{i=2}^n N(r_i) < \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^n N(a_{1,i}). By the inductive hypothesis, there is a sequence of elementary row and column operations which diagonalize this new matrix, and so there is a sequence of elementary row and column operations which diagonalizes A. This proves our base case, where A has one row.

Suppose now that the result holds for every matrix having at most m rows, and let A be an (m+1) \times n matrix. Say A = \begin{bmatrix} a_{1,1} & R_1 \\ C_1 & A_1 \end{bmatrix}, where R_1 = [r_{1,2}\ cdots\ r_{1,n}] and C_1 = [c_{2,1}\ \cdots\ c_{m+1,1}]^\mathsf{T}.

We next claim that there is a sequence of elementary row and column operations which transforms A into a matrix of the form \begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}. To prove this, we proceed by induction on \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}). (Note that it may be the case that n = 1. In this case the sum over the r is empty and thus 0. However, the sum over the c is not empty.) If \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = 0, then we have c_{i,1} = r_{1,j} = 0 for each 2 \leq i \leq m+1 and 2 \leq j \leq n, and so A = \begin{bmatrix} a_{1,1} & 0 \\ 0 & A_1 \end{bmatrix} has the desired form. For the induction hypothesis, suppose that for some K \in \mathbb{N}, every matrix B can be put in the desired form provided \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) \leq K, and suppose that for our A we have \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1. Now among the entries of our matrix, choose a nonzero element of minimal norm and use elementary row and column operations of type 1 (swap) to put this entry in position (1,1). (If no such entry exists, then A = 0 and there is nothing to show.) Now by the Division Algorithm in R, there exist q_i,t_j,u_i,v_j such that r_{1,i} = q_ia_{1,1} + u_i, c_{j,1} = t_ja_{1,1} + v_j, 0 \leq N(u_i) < N(a_{1,1}), and 0 \leq N(v_j) < N(a_{1,1}). Using elementary row and column operations of type 2 (add a multiple of one row/column to a different row/column) we can replace r_{1,i} with u_i and likewise replace c_{j,1} by v_j. Note now that \sum_{i=2}^{m+1} N(v_j) + \sum_{i=2}^n N(u_i) < \sum_{i=2}^{m+1} N(a_{1,1}) + \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1. By the induction hypothesis, there is a sequence of elementary row and column operations which puts the new A in the desired form, and so (performing these one after the other) we can put the original matrix A in the desired form.

Now A can be put in the form \begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix} by elementary row and column operations. Note that any row or column operation we perform on A_1, when performed analogously on A, does not change the entry a_1 or introduce new nonzero elements to row and column 1. Since (as we assume by the induction hypothesis) the matrix A_1 can be diagonalized, then A can also be diagonalized by elementary row and column operations.

We have thus shown by induction that every matrix A over a Euclidean domain can be diagonalized. It remains to be seen that these diagonal entries can be ordered by divisibility. We can assume that our matrix D is square and has all nonzero entries on the main diagonal. We proceed by induction on the dimension of D. For the base case, where D has dimension 1 \times 1, there is nothing to show. Suppose now that every square diagonal matrix D of dimension n can have its diagonal entries divisibility-ordered by elementary row and column operations and let D = \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix} be a square diagonal matrix of dimension n+1. We claim that d_1 can be replaced by the greatest common divisor of all the d_i, and that each remaining d_i can be replaced by a linear combination of the d_is, via elementary row and column operations. We will show this for one d_i. Note that if D is diagonal, then row and column operations which only operate on two rows and columns (say a and b) do not affect the rest of the matrix. For this reason we can focus on a 2 \times 2 matrix, say \begin{bmatrix} d_1 & 0 \\ 0 & d_i \end{bmatrix}. Since R is a Euclidean domain, using the extended Euclidean Algorithm we can find x and y such that \mathsf{gcd}(d_1,d_i) = xd_1 + yd_i. Using a column/row operation of type 2, we can obtain \begin{bmatrix} d_1 & xd_1 + yd_i \\ 0 & d_i \end{bmatrix}. Swapping rows (or columns), we have \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & d_1 \\ d_i & 0 \end{bmatrix}. If d_1 = a_1\mathsf{gcd}(d_1,d_i), then again we can obtain \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ d_i & a_1d_i \end{bmatrix}, and so \begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ 0 & a_1d_i \end{bmatrix}. Repeating this procedure for each diagonal entry (except the first), and since greatest common divisor is associative, we have a diagonal matrix \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix} where d_1 divides each diagonal entry of D_1. By induction, D is row/column equivalent to a diagonal matrices whose diagonal entries are ordered by divisibility.

Finally, suppose we have a finitely generated R-module M, with (say) a generating set of cardinality n and corresponding surjective homomorphism \varphi : R^n \rightarrow M. By the preceding result, there exists a basis B = \{e_1, \ldots, e_n\} for R^n and a generating set E = \{e_1,\ldots,e_m\} for \mathsf{ker}\ \varphi such that the corresponding relations matrix is of the form \begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}, D is square of dimension k \leq n and has no zero diagonal entries, and the diagonal entries of D are ordered by divisibility. In particular, we have \mathsf{ker}\ \varphi = Rd_1 + \cdots Rd_k = (d_1) \oplus \cdots \oplus (d_k) \oplus 0^{n-k}. Then by this previous exercise, M \cong R/\mathsf{ker}\ \varphi \cong R/(d_1) \oplus \cdots \oplus R/(d_k) \oplus R^{n-k}. Note that if any d_i are units, then the corresponding quotient R/(d_i) is trivial.

By the uniqueness portion of the Fundamental Theorem of Finitely Generated Modules over a PID, the (nonunit) d_i are precisely the invariant factors of M.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: