Each Matrix Is Equivalent to an Extended
Diagonal Matrix

It is easy to see that any two equivalent matrices must have the same size, say $m \times n$. A non-square matrix is never equivalent to any diagonal matrix. Thus, the following definition is called for:

Definition 78   (Extended Diagonal Matrix )

An extended diagonal matrix is defined to be the matrix obtained by taking a diagonal matrix, adding enough zero rows at the bottom and enough zero columns on the right so that it becomes a matrix of the desired size.

Proposition: Applying a secondary row (column) operation, we may change a matrix $M = \left[\!\! \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ a_{21} & \cdot... ...s & a_{3n} \\ & \ddots & \\ a_{m1} & \cdots & a_{mn} \end{array}\!\!\right]$ to $\left[\!\! \begin{array}{ccc} d & * & * \\ 0 & * & * \\ a_{31} & \cdots & a_{3n} \\ & \ddots & \\ a_{m1} & \cdots & a_{mn} \end{array}\!\!\right]$ $\left(\left[\!\! \begin{array}{cccc} e & 0 & a_{13} & \cdots \\ \ * & * & a_... ...s \\ & & \ddots & \\ \ * & * & a_{m3} & \cdots\end{array}\!\!\right]\right)$, where $d = \gcd\{a_{11}, a_{21}\}$ ( $e =\gcd\{a_{11}, a_{12}\}$).

Proof:

Let $d = \gcd\{a_{11}, a_{21}\}$, there are $s, t \in {\cal D}$ so that $s \cdot a_{11} + t \cdot a_{21} = d$. Since $d = \gcd\{a_{11}, a_{21}\}$, $a_{11} = d \cdot b$, $a_{21} = d \cdot c$, $s \cdot a_{11} + t \cdot a_{21} = s \cdot d \cdot b + t \cdot d \cdot c = d$ which implies that $s \cdot b + t \cdot c = 1$. Notice that $a_{11} \cdot c = a_{21} \cdot b = {\rm lcm}\{a_{11}, a_{21}\}$. Let $A$ be the invertible matrix $\left[\!\! \begin{array}{rc} s & t \\ -c & b \end{array}\!\! \right]$. Multiplying $A \oplus I$ to the left of $M$, we are done.

Q.E.D.

Recall from Chapter 4 that a P.I.D. is a unique factorization domain, we hence are able to define the following length function on a P.I.D ${\cal D}$:

Definition 79   (Length Function on a $P.I.D.\ {\cal D}$)

Let $N$ be the natural number system (including the additive identity $0$), ${\cal D}$ be any $P.I.D.$. For any non-zero, non-unit element $a \in {\cal D}$, let $a = c \cdot p_{1}^{r_{1}} \cdots p_{k}^{r_{k}}$ denote its primary decomposition. We define the length function on ${\cal D}$ by

$$\begin{array}{ccccll} \theta & : & {\cal D} - \{0\} & \longr... ... } a = c \cdot p_{1}^{r_{1}} \cdots p_{k}^{r_{k}}. \end{array}$$

Remarks:

1. It is easy to see that this function $\theta : {\cal D} - \{0\} \longrightarrow N$ is a monoid homomorphism: $\theta(1) = 0$, $\theta(a \cdot b) = \theta(a) + \theta(b)$.

2. Let $N^{*} = \{\infty\} \bigcup N$ and define $\infty + n = n + \infty = \infty$ for all $n \in N^{*}$. $<\!\!N^{*}, +\!\!>$ is still a monoid. We can extend $\theta : {\cal D} - \{0\} \longrightarrow N$ to be $\raisebox{-1pt}{$\widetilde{\theta}$} : {\cal D} \longrightarrow N^{*}$ by defining $\raisebox{-1pt}{$\widetilde{\theta}$}(0) = \infty,\; \raisebox{-1pt}{$\widetilde{\theta}$}(d) = \theta(d)$ if $d \in {\cal D} - \{0\}$. Then $\raisebox{-1pt}{$\widetilde{\theta}$}$ is still a monoid homomorphism.

3. If $a, b \in {\cal D}$, $a \,\rule[-.05in]{0.005in}{.2in}\,\, b$, clearly, $\raisebox{-1pt}{$\widetilde{\theta}$}(a) \leq \raisebox{-1pt}{$\widetilde{\theta}$}(b)$. If $a \,\rule[-.05in]{0.005in}{.2in}\,\, b$ and $\raisebox{-1pt}{$\widetilde{\theta}$}(a) =\;\raisebox{-1pt}{$\widetilde{\theta}$}(b)$, then $a$ is an associate of $b$, $a \sim b$.

Observation:

Let $M \in {\cal M}\!\!\!\!\!\!\!{\cal M}_{m \times n}({\cal D})$. Let us also define ${\cal C}_{_{M}}$ to be the following class of $M$: ${\cal C}_{_{M}} \!=\! \{P M Q \,\rule[-.05in]{0.005in}{.2in}\,P, Q {\rm\ are\ finite\ products\ of\ elementary\ or\ secondary\ matrices.}\}$. ${\cal C}_{_{M}}$ is closed under the elementary and secondary operations. Let us define $\Theta : {\cal C}_{_{M}} \longrightarrow N^{*}$ by $\Theta(B) = \min \{\raisebox{-1pt}{$\widetilde{\theta}$}(b_{_{ij}}) \,\rule[-.05in]{0.005in}{.2in}\,1 \leq i \leq m, 1 \leq j \leq n\}$, where $b_{_{ij}}$ denotes the entry at the $i$-th row and $j$-th column of $B \in {\cal C}_{_{M}}$. Using the fact that $<\!\!N, \leq>$ is well-ordered, i.e. each non-empty subset of $N$ has a first element, the following three statements are easy but useful exercises:

Exercises:

1. For all $B_{o} \in {\cal C}_{_{M}}$ so that $\Theta(B_{o}) = n_{o} = \min \{\Theta(B) \,\rule[-.05in]{0.005in}{.2in}\,B \in {\cal C}_{_{M}}\}$, let $\raisebox{-1pt}{$\widetilde{\theta}$}(b_{_{kl}}) = \Theta(B_{o})$, where $b_{_{kl}}$ is some entry in $B_{o}$, then $b_{_{kl}} \,\rule[-.05in]{0.005in}{.2in}\,\, b_{_{il}}$, $b_{_{kl}} \,\rule[-.05in]{0.005in}{.2in}\,\, b_{_{kj}}$, for $1 \leq i \leq m$, $1 \leq j \leq n$. In other words, $b_{_{kl}}$ divides all of the entries on row $k$ and column $l$.
2. $\exists \left[\!\!\begin{array}{cccc} d & 0 & \cdots & 0 \\ 0 & a_{22} & \cd... ...& \\ 0 & a_{m2} & \cdots & a_{mn} \end{array}\!\!\right] \in {\cal C}_{_{M}}$ so that $\raisebox{-1pt}{$\widetilde{\theta}$}(d) = n_{o} = \min \{\Theta(B) \,\rule[-.05in]{0.005in}{.2in}\, B \in {\cal C}_{_{M}}\}$. For such matrix, $d \,\rule[-.05in]{0.005in}{.2in}\,\, a_{_{ij}}$, for all $2 \leq i \leq m$, $2 \leq j \leq m$.

3. 1. Let $M = \left[\!\! \begin{array}{cc} a_{1} & {\bf {\Huge0}} \\ {\bf {\Huge0}} & {\Huge N} \end{array}\!\! \right]$, ${\Huge N} = \left[\!\! \begin{array}{ccc} b_{22} & \cdots & b_{2n} \\ & \ddots & \\ b_{m2} & \cdots & b_{mn} \end{array}\!\! \right]$ is an $(m -1) \times (n-1)$ matrix and $a_{1}$ is a divisor for each entry $b_{ij}, 2 \leq i \leq n, 2 \leq j \leq m$, of ${\Huge N}$, then show that
      1. $\Delta_{1}(M) = a_{1}$ and
      2. $\Delta_{r + 1}(M) = a_{1} \cdot \Delta_{r}(N)$, for all $1 \leq r$.

   2. Similarly, let $M = \left[\!\! \begin{array}{ccc} a_{1} & 0 & {\bf {\Huge0}} \\ 0 & a_{2} & {... ...e0}} \\ {\bf {\Huge0}} & {\bf {\Huge0}} & {\Huge N} \end{array}\!\! \right]$, where ${\Huge N} = \left[\!\! \begin{array}{ccc} b_{33} & \cdots & b_{3n} \\ & \ddots & \\ b_{m3} & \cdots & b_{mn} \end{array}\!\! \right]$ is an $(m -2) \times (n-2)$ matrix and $a_{1}$ is a divisor for $a_{2}$ and $a_{2}$ is a divisor for each entry $b_{ij}, 3 \leq i \leq n, 3 \leq j \leq m$, of ${\Huge N}$, prove that:
      1. $\Delta_{1}(M) = a_{1}$.
      2. $\Delta_{2}(M) = a_{1} \cdot a_{2}$.
      3. $\Delta_{r + 2}(M) = a_{1} \cdot a_{2} \cdot \Delta_{r}(N)$, for all $1 \leq r$.

   3. If $L$ is an extended diagonal matrix with the property that its upper diagonal entries being divisors of lower diagonal entries and $a_{1}, \ldots, a_{k}$ be all of the non-zero diagonal entries of the diagonal submatrix from which $L$ is extended, please predict $(\Delta_{r}(L))$, for all $1 \leq r \leq k$.

Hint:

1. The well-ordering of $N$ guarantees the existence of $B_{o}$. Without loss of generality, may assume that $\raisebox{-1pt}{$\widetilde{\theta}$}(b_{11}) = n_{o} = \Theta(B_{o})$. Applying the previous proposition to conclude that $b_{11}$ divides all of the entries on the first row and first column. Applying the third elementary row or column operations to get the matrix required by part 2.

2. To finish this, starting from the second row, we multiply each row by 1 and add it to the first row, then apply the previous statement, we can guarantee that $d$ is a divisor for each entry $a_{_{ij}}$.
3. 1. If $1 \in H \bigcap J$, ${\mathfrak m}^{H}_{J} = a_{1} \cdot {\mathfrak m'}^{H'}_{J'}$, where the two shuffles $H', J'$ are defined as $H' = H -\{1\} \in {\mathfrak S}_{n}^{r}, J' = J -\{1\} \! \in\! {\mathfrak S}_{m}^{r}$.
   2. If $1 \in H$ or $1 \in J$, but $1 \not\in H \bigcap J$, then ${\mathfrak m}^{H}_{J} = 0$.
   3. If $1 \not\in H$, $1 \not\in J$, $\Delta_{r + 1}(N) \,\,\rule[-.05in]{0.005in}{.2in}\,\, {\mathfrak m}^{H}_{J}$.
   4. $a_{1} \cdot \Delta_{r}(N) \,\,\rule[-.05in]{0.005in}{.2in}\,\, \Delta_{r + 1}(N).$ Hint: Choose the first row of any $(r + 1) \times (r + 1)$ submatrix of $N$ to expand the determinant of the submatrix.
   5. $\Delta_{r + 1}(M) = \left(\left\{a_{1} \cdot {\mathfrak m'}^{H'}_{J'} \,\,\rule[-.05in]{0.005in}{.2in}\,\, H', J' \mbox{ are defined as above}.\right\}\right)$

   6. We will provide another proof for this part in the next subsection.

      Remark: This part will be helpful for the proving of Theorem 95.

Proposition: By a sequence of elementary and secondary row and column operations, an $m \times n$ matrix $M$ may be transfigured to $\left[\!\! \begin{array}{cc} d & 0 \\ 0 & {\Huge N} \end{array}\!\! \right]$, where ${\Huge N}$ is an $(m -1) \times (n-1)$ matrix and $d$ is a divisor for each entry of ${\Huge N}$.

With these two propositions on hand, we are now ready for the main theorem of this section:

Theorem 95  

Each $m \times n$ matrix $M$ may be transfigured to an extended diagonal matrix of the following format by a finite number of elementary or secondary operations:

Proof:

Let the rank of $M$ be $k$. We prove this theorem by induction on $k$. If $M$ is a zero matrix, there is nothing to be done. Assume that $M \not= {\bf\huge {0}}$. Without loss of generality, may assume that $a_{11} \not= 0$. By the above proposition, $M$ is equivalent to $\left[\!\! \begin{array}{cc} a_{1} & 0 \\ 0 & {\Huge N} \end{array}\!\! \right]$, where ${\Huge N}$ is an $(m -1) \times (n-1)$ matrix and $a_{1}$ is a divisor for each entry of ${\Huge N}$. Clearly, $a_{1} \not= 0$. Otherwise, $N$ would be a zero matrix, so is matrix $M$. By the previous exercise, the determinantal rank of $N$ is $k-1$, hence a matrix of rank $k-1$. By the induction hypothesis, $N$ can be transfigured to a matrix of the specified format, so is $M$.

Q.E.D.

As an application of the last theorem, we have part one of the following corollary which is an extension of Theorem 8. More importantly, part 2 and part 3 are two of the main results of this chapter which we have struggled so hard to work out.

Corollary:

1. A square matrix over a P.I.D. ${\cal D}$ is invertible if and only if it is a product of a sequence of elementary and secondary matrices.
2. Each matrix is equivalent to an extended diagonal matrix whose upper diagonal entries are divisors of lower diagonal entries.
3. Matrices $M$ and $N$ are equivalent if and only if $M$ may be transfigured to $N$ by a sequence of elementary and secondary operations.

Proof:

1. $\Longleftarrow:$ Trivial!! $\Longrightarrow:$ By the last theorem, an invertible matrix $P$ may be transfigured to a genuine diagonal matrix by a sequence of elementary and secondary operations, i.e., $L = E_{1} \cdot E_{2} \cdots E_{k} \cdot P \cdot E_{k+1} \cdots E_{n}$. Since $P$ is invertible, so is $L$, and hence each diagonal entry of $L$ must be a unit. This implies that, for each row of $L$, multiplying it by a suitable unit, $L$ becomes an identity matrix. Multiplying a suitable unit on any row of $L$ is again an elementary operation. We may as well assume that $I = E_{1} \cdot E_{2} \cdots E_{k} \cdot P \cdot E_{k+1} \cdots E_{n}$. Since each $E_{i}$ is clearly invertible, $P = E_{k}^{-1} \cdot E_{k-1}^{-1} \cdots E_{1}^{-1} \cdot I \cdot E_{n}^{-1} \cdots E_{k+1}^{-1}$.
2. Each $m \times n$ matrix $M$ may be transfigured to an extended diagonal matrix with the specified property by a finite number of elementary or secondary operations, i.e. by multiplying elementary and secondary matrices on the left and right hand sides of $M$, it becomes the desired extended diagonal matrix. Since each elementary or secondary matrix is invertible, using the associative law of matrix multiplication, we may multiply the elementary or secondary matrices on the left (right) hand side of $M$ together to get an invertible matrix $P$ ($Q$) and $P \cdot M \cdot Q$ is the desired extended diagonal matrix.
3. Easy exercise.

Q.E.D.

Remark:

If ${\cal D}$ is a Euclidean domain, $\gcd\{a, b\}$ can be computed by the so called "Division Algorithm". (Recall from high school, let $n\,, m \in Z$, how can we compute $\gcd\{n, m\}$ without appealing to factoring $n, m$ as products of prime numbers?) Transferring to the matrix language, each secondary operation may be replaced by a finite number of elementary operations. The exact statement of Theorem 8 holds for the matrices over any Euclidean domain.

Exercise: Show that the matrices $M$ and $N$ are equivalent to the matrices you predicted in the exercises at the end of the last subsection (Page ).

$\begin{array}{ccc} M = \left[\!\!\begin{array}{rrrr} 6 & 2 & 3 & 0\\ 2 & 3 ... ... & -1 & x - 4 & 4 \\ -4 & 2 & 2 & x - 3 \end{array}\!\!\right]. \end{array}$