Try
The integer relations 4e₁=0 and 6e₂=0 are described by the diagonal matrix A with rows (4,0),(0,6). This matrix is already diagonal. Nevertheless, its two positive entries do not form a divisibility chain: 4 does not divide 6. Can changes of integer generators and relations produce diagonal entries that do?
We will construct integer matrices U and V with integer inverses such that UAV has diagonal entries 2 and 12. These are changes of integer coordinates, not permission to divide a relation by an arbitrary integer. A matrix with determinant 2 is invertible over ℚ but is not an invertible change of coordinates on ℤ².
For an m by n integer matrix A, a Smith diagonal form is an m by n matrix D whose only nonzero entries are positive diagonal entries d₁,…,dᵣ, with d₁ dividing d₂, d₂ dividing d₃, and so on. Here r can be zero. We will prove the existence of U and V with D=UAV, where U is m by m, V is n by n, and both are unimodular: integer matrices with integer inverses. Their determinants are ±1. This lesson proves an algorithm and its termination; the next lesson explains classification and uniqueness.
Predict
Predict which operations are reversible over the integers:
- Swap two rows or two columns.
- Negate a row or a column.
- Add an integer multiple of one row to another, or one column to another.
- Divide a row containing only even entries by 2.
The first three have integer inverses of the same kind. The last operation need not preserve the integer presentation: the relation 2x=0 is different from x=0. Exact divisibility of displayed entries does not make division an allowed coordinate change.
Also predict why simply finding a diagonal matrix is insufficient. The starting matrix diag(4,6) will be our test case for the additional divisibility repair.
Experiment
Apply the following operations in order. Rᵢ means row i and Cⱼ means column j; an assignment replaces only the indicated row or column. Fill in one matrix yourself before reading its row-pair entry.
| Operation just completed | Current matrix, given by rows | Purpose |
|---|
| Start | (4,0); (0,6) | Diagonal but not a divisibility chain |
| R₁ ← R₁+R₂ | (4,6); (0,6) | Bring the offending 6 into the pivot row |
| C₂ ← C₂−C₁ | (4,2); (0,6) | Euclidean remainder of 6 modulo 4 |
| Swap C₁,C₂ | (2,4); (6,0) | Replace pivot 4 by the smaller positive pivot 2 |
| R₂ ← R₂−3R₁ | (2,4); (0,−12) | Clear the first column |
| C₂ ← C₂−2C₁ | (2,0); (0,−12) | Clear the first row |
| R₂ ← −R₂ | (2,0); (0,12) | Normalize the final sign |
Keeping the row operations and column operations in their respective orders gives U with rows (1,1),(3,2) and V with rows (−1,3),(1,−2). Check the multiplication directly: UA has rows (4,6),(12,12), and multiplying these rows by V gives (2,0),(0,12). Both determinants are −1, so this is an exact unimodular certificate.
The two kinds of operations may be interleaved, but their records have different update rules. If M=UAV, a row operation E changes U to EU. A column operation F changes V to VF. Start with the identity matrices. Confusing left and right multiplication can invalidate an otherwise plausible list of operations.
Understand
The elementary integer tools
Each permitted operation is multiplication by an integer elementary matrix with an explicit integer inverse. For example, adding q times one row to another is undone by adding −q times that row. These elementary matrices have determinant ±1. Products remain unimodular. Conversely an integer square matrix of determinant ±1 has an integer inverse by the adjugate formula. The algorithm below only needs the explicit elementary inverses.
Use integer Euclidean division with a positive divisor p: for any integer b there are integers q,r such that b=qp+r and 0≤r<p. Negative b causes no problem; q may be negative. This is division of numbers used to choose an allowed subtraction, not division of an entire row.
First clear a pivot row and column
If the current active matrix is zero, stop on that block. Otherwise swap a nonzero entry into its upper-left corner and negate its row if necessary. Its pivot p is now positive.
For each other entry b in the pivot column, divide b=qp+r and subtract q times the pivot row from its row. If r=0, this clears that entry. If r>0, swap its row with the pivot row: the new positive pivot is r, strictly smaller than p. Restart the clearing procedure at this smaller pivot.
If the column has been cleared without a restart, apply the analogous procedure to the entries in the pivot row, using column operations. A zero remainder clears an entry. A positive remainder is moved to the pivot position by a column swap and again strictly decreases the positive pivot. A column swap can spoil the already cleared column, which is why the procedure restarts rather than assuming it remains clear.
Without a pivot decrease, these are finite scans of the other rows and columns. In the column-operation scan, subtracting a multiple of the already cleared pivot column does not change any entry below the pivot row in the other columns. Thus, when no positive remainder occurs, both the pivot row and column are cleared. We have a block matrix with p in the corner, zeros in the rest of its row and column, and a lower-right block B.
Repair divisibility before freezing the pivot
Clearing alone does not establish Smith form. Test whether p divides every entry of B. If it does, freeze p and proceed to the smaller block. If not, choose an entry b in row i and column j of the active matrix below and to the right of the pivot, with p not dividing b.
Add row i to the pivot row. Because the first entry of row i is zero, the pivot is still p; the chosen entry in the pivot row is now b. Write b=qp+r with 0<r<p. Subtract q times the pivot column from column j, producing r at that position. Swap column j with the pivot column. The new pivot is the positive integer r, strictly smaller than p. Restart clearing.
This is the promised repair, including its decreasing quantity. It does not merely rearrange a diagonal matrix and hope for divisibility. It deliberately reintroduces off-diagonal entries to obtain a smaller pivot.
Why the algorithm terminates and gives the whole chain
At a fixed active block, every restart strictly decreases the positive integer pivot. There can be only finitely many restarts. Between restarts the scans and the finite divisibility test require finitely many operations. Therefore this stage eventually produces a positive pivot p, a cleared row and column, and a remaining block all of whose entries are multiples of p.
Now apply the same algorithm only inside that lower-right block. Induct on the smaller of its numbers of rows and columns. Empty-dimensional blocks require no operations. A zero block contributes only zeros; otherwise the next stage produces another positive pivot and a yet smaller block.
All operations used inside the lower block have integer coefficients. Consequently, if every entry initially is a multiple of p, every entry throughout that lower-block computation remains a multiple of p. In particular its first positive Smith entry is divisible by p. Induction gives the divisibility chain among its own entries, so attaching p gives the full chain. Extending each lower-block row or column operation by an identity on the frozen coordinates preserves the earlier diagonal entries and zeros.
The algorithm therefore constructs U and V and terminates with the claimed rectangular Smith diagonal form. No compactness argument or bound on the total size of intermediate entries was used. The decreasing pivot proves termination, not an efficient bit-complexity bound.
Zero matrices, rectangular matrices, and what is preserved
For a zero m by n matrix, take U and V to be the identity matrices and r=0. If m=0 or n=0, the form has no nonzero diagonal entries and the same convention applies, using the empty identity where appropriate. For a general rectangle there are at most min(m,n) nonzero pivots. Surplus rows or columns remain zero after the active block is exhausted.
Every elementary operation also is invertible over ℚ. Thus rational rank is preserved, and the number r of nonzero diagonal entries equals rankℚ A. However, rational row reduction alone would not prove this stronger integer equivalence. For instance, multiplying a single row by 1/2 can turn (2) into (1) over ℚ, although it changes the integer quotient.
There is also a useful check before classification: the set of all integer linear combinations of the matrix entries is preserved. Each new entry is an integer combination of old entries, and the inverse operation proves the reverse inclusion. For a nonzero Smith diagonal form with d₁ dividing all its other entries, this set is d₁ℤ. Thus d₁ is the positive greatest common divisor of all original entries. This check alone does not determine every later diagonal entry of a general matrix.
Apply
Change the matrix to the 2 by 3 rectangle with rows (6,0,6),(0,10,10). Its last column is the sum of its first two. First use C₃ ← C₃−C₁−C₂, implemented as two allowed operations. Then reduce the remaining diag(6,10) block using a divisibility repair. Predict the final nonzero diagonal entries and the number of zero columns. Keep enough operation history to verify the result directly.
Compare an exact rectangular certificate
After clearing C₃, perform on the first two columns and rows: R₁ ← R₁+R₂; C₂ ← C₂−C₁; swap C₁,C₂; R₂ ← R₂−2R₁; swap R₁,R₂; R₂ ← R₂−2R₁; C₂ ← C₂+6C₁. The successive 2 by 2 blocks are (6,10);(0,10), then (6,4);(0,10), then (4,6);(10,0), then (4,6);(2,−12), then (2,−12);(4,6), then (2,−12);(0,30), and finally (2,0);(0,30). No final sign change is needed.
The correct completed form has rows (2,0,0),(0,30,0). A compact certificate is U with rows (−2,−1),(5,3) and V with rows (−1,−5,−1),(1,6,−1),(0,0,1). Both square determinants are −1. Multiplying the original rectangle by these matrices verifies the claimed result. The nonzero entries have product 60 and their first entry is the gcd 2; the extra zero column is required by the rectangular shape.
Explain why a run that stopped at (6,0,0),(0,10,0) would be incomplete despite having cleared every off-diagonal entry. Then try a matrix all of whose entries are multiples of 3: justify why no later pivot can cease to be a multiple of 3, regardless of the sequence of permitted operations.
Continue
Return to integer presentations and changes of generators for the meaning of the two coordinate changes. Continue to Smith form and classification to distinguish existence of a reduction from uniqueness of the resulting invariant factors and to interpret the quotient group.
