| Version 8 |
Version 7 |
| This topic gives a version of the Gauss elimination algorithm for principal ideal domains which is |
|
| usually described only for commutative fields. |
|
|
|
| Let $A \ne 0$ be a $m \times n$-matrix with entries from a principal ideal |
Let $A \ne 0$ be a $m \times n$-matrix with entries from a principal ideal |
| domain $R$. For $a \in R \setminus \{0\}$ $\delta(a)$ denotes the number of |
domain $R$. For $a \in R \setminus \{0\}$ $\delta(a)$ denotes the number of |
| prime factors of $a$. Start with $t=1$ and choose $j_t$ to be the smallest |
prime factors of $a$. Start with $t=1$ and choose $j_t$ to be the smallest |
| column index of $A$ with a non-zero entry. |
column index of $A$ with a non-zero entry. |
| \begin{description} |
\begin{description} |
| \item[(I)] |
\item[(I)] |
| If $a_{t, j_t}=0$ and $a_{k,j_t} \ne 0$, exchange rows 1 and $k$. |
If $a_{t, j_t}=0$ and $a_{k,j_t} \ne 0$, exchange rows 1 and $k$. |
| \item[(II)] |
\item[(II)] |
| If there is an entry at position $(k,j_t)$ such that $a_{t,j_t} \nmid |
If there is an entry at position $(k,j_t)$ such that $a_{t,j_t} \nmid |
| a_{k,j_t}$, then set $\beta =\gcd\left(a_{t,j_t}, a_{k,j_t}\right)$ and choose |
a_{k,j_t}$, then set $\beta =\gcd\left(a_{t,j_t}, a_{k,j_t}\right)$ and choose |
| $\sigma, \tau \in R$ such that |
$\sigma, \tau \in R$ such that |
| \begin{equation*} |
\begin{equation*} |
| \sigma\cdot a_{t,j_t}-\tau \cdot a_{k,j_t}=1. |
\sigma\cdot a_{t,j_t}-\tau \cdot a_{k,j_t}=1. |
| \end{equation*} |
\end{equation*} |
| By left-multiplication with an appropriate matrix it can be achieved that row 1 |
By left-multiplication with an appropriate matrix it can be achieved that row 1 |
| of the matrix product is the sum of row 1 multiplied by $\sigma$ and row $k$ |
of the matrix product is the sum of row 1 multiplied by $\sigma$ and row $k$ |
| multiplied by $(-\tau)$. Then we get $\beta$ at position $(t,j_t)$, where |
multiplied by $(-\tau)$. Then we get $\beta$ at position $(t,j_t)$, where |
| $\delta(\beta) < \delta(a_{t,j_t})$. |
$\delta(\beta) < \delta(a_{t,j_t})$. |
| Repeating these steps one ends up with a matrix having an entry at position |
Repeating these steps one ends up with a matrix having an entry at position |
| $(t,j_t)$ that divides all entries in column $j_t$. |
$(t,j_t)$ that divides all entries in column $j_t$. |
| \item[(III)] |
\item[(III)] |
| Finally, adding appropriate multiples of row $t$, it can be achieved that all |
Finally, adding appropriate multiples of row $t$, it can be achieved that all |
| entries in column $j_t$ except for that at position $(t,j_t)$ are zero. This can |
entries in column $j_t$ except for that at position $(t,j_t)$ are zero. This can |
| be achieved by left-multiplication with an appropriate matrix. |
be achieved by left-multiplication with an appropriate matrix. |
| \end{description} |
\end{description} |
| Applying the steps described above to the remaining non-zero columns of the |
Applying the steps described above to the remaining non-zero columns of the |
| resulting matrix (if any), we get an $m \times n$-matrix with column indices |
resulting matrix (if any), we get an $m \times n$-matrix with column indices |
| $j_1, \ldots, j_r$ where $r \le \min(m,n)$, each of which satisfies the |
$j_1, \ldots, j_r$ where $r \le \min(m,n)$, each of which satisfies the |
| following: |
following: |
| \begin{enumerate} |
\begin{enumerate} |
| \item |
\item |
| the entry at position $(l,j_l)$ is non-zero; |
the entry at position $(l,j_l)$ is non-zero; |
| \item |
\item |
| all entries below and above position $(l,j_l)$ as well as entries left of |
all entries below and above position $(l,j_l)$ as well as entries left of |
| $(l,j_l)$ are zero. |
$(l,j_l)$ are zero. |
| \end{enumerate} |
\end{enumerate} |
| Furthermore, all rows below the $r$-th row are zero. |
Furthermore, all rows below the $r$-th row are zero. |
|
|
|
This is a version of the Gauss algorithm for principal ideal domains which is |
|
usually described only for commutative fields. |
|
|
| Now we can re-order the columns of this matrix so that elements on positions |
Now we can re-order the columns of this matrix so that elements on positions |
|
$(i,i)$ for $1 \le i\le r$ are nonzero and $\delta(a_{i,i}) \le
|
$(i,i)$ for $1 \le i\le r$ are nonzero and $\delta(a_{ii}) \le
|
| \delta(a_{i+1,i+1})$ for $1 \le i < r$; and all columns right of the $r$-th |
\delta(a_{i+1,i+1})$ for $1 \le i < r$; and all columns right of the $r$-th |
| column (if present) are zero. For short set $\alpha_i$ for the element at |
column (if present) are zero. For short set $\alpha_i$ for the element at |
| position $(i,i)$. $\delta$ has non-negative integer values; so |
position $(i,i)$. $\delta$ has non-negative integer values; so |
| $\delta(\alpha_1)=0$ is equivalent to $\alpha_1$ being a unit of $R$. |
$\delta(\alpha_1)=0$ is equivalent to $\alpha_1$ being a unit of $R$. |
| $\delta(\alpha_i) =\delta(\alpha_{i+1})$ can either happen if $\alpha_i$ and |
$\delta(\alpha_i) =\delta(\alpha_{i+1})$ can either happen if $\alpha_i$ and |
| $\alpha_{i+1}$ differ by a unit factor, or if they are relative prime. In the |
$\alpha_{i+1}$ differ by a unit factor, or if they are relative prime. In the |
| latter case one can add column $i+1$ to column $i$ (which doesn't change |
latter case one can add column $i+1$ to column $i$ (which doesn't change |
| $\alpha_i)$ and then apply appropriate row manipulations to get $\alpha_i=1$. |
$\alpha_i)$ and then apply appropriate row manipulations to get $\alpha_i=1$. |
| And for $\delta(\alpha_i)<\delta(\alpha_{i+1})$ and $\alpha_i \nmid |
And for $\delta(\alpha_i)<\delta(\alpha_{i+1})$ and $\alpha_i \nmid |
| \alpha_{i+1}$ one can apply step (II) after adding column $i+1$ to column $i$. |
\alpha_{i+1}$ one can apply step (II) after adding column $i+1$ to column $i$. |
| This diminishes the minimum $\delta$-values for non-zero entries of the matrix, |
This diminishes the minimum $\delta$-values for non-zero entries of the matrix, |
| and by reordering columns etc. we end up with a matrix whose diagonalelements |
and by reordering columns etc. we end up with a matrix whose diagonalelements |
| $\alpha_i$ satisfy $\alpha_i \mid \alpha_{i+1}\;\forall\;1 \le i < r$. |
$\alpha_i$ satisfy $\alpha_i \mid \alpha_{i+1}\;\forall\;1 \le i < r$. |
|
|
| Since all row and column manipulations involved in the process are invertible, |
Since all row and column manipulations involved in the process are invertible, |
| this shows that there exist invertible $m \times m$ and $n \times n$-matrices |
this shows that there exist invertible $m \times m$ and $n \times n$-matrices |
| $s,T$ so that $S\cdot A \cdot T$ is |
$s,T$ so that $S\cdot A \cdot T$ is |
| \begin{matrix} |
\begin{displaymath} |
|
\left( |
|
\begin{array}{ccccc} |
| \alpha_1 & 0 & \ldots & 0 \\ |
\alpha_1 & 0 & \ldots & 0 \\ |
| 0 & \alpha_2 & 0 & \ldots & 0 \\ |
0 & \alpha_2 & 0 & \ldots & 0 \\ |
| \vdots &\ddots & \vdots \\ |
\vdots & &\ddots \\ |
| 0 & \alpha_r & 0 \\ |
0 & \ldots & 0 & \alpha_r & 0 \\ |
| 0 & \ldots 0 & 0 |
0 & \ldots 0 |
| \end{matrix} |
\end{array}\right) |
| This is the \textbf{Smith normal form} of the matrix. The elements $\alpha_i$ are unique up to associates and are called |
\end{displaymath} |
|
This is the \textbf{Smith normal form} of the matrix. The elements $\alpha_i$ are unique up to associatedness and are called |
| elementary divisors. |
elementary divisors. |
