Try
Work with polynomial entries over a field F, and let t be an indeterminate. Start with A=diag(t,t−1). It is diagonal, but t does not divide t−1. Their difference is 1, so a reversible polynomial operation might uncover a unit pivot. Predict the other diagonal entry if we obtain a monic divisibility chain.
The answer will be diag(1,t(t−1)). This is an identity of polynomial matrices. We are not choosing a numerical value of t, and we are not replacing every nonzero polynomial by an invertible scalar. In F[t], the units are precisely the nonzero constant polynomials. This distinction is what preserves information about polynomial relations.
For an m by n matrix A over F[t], we will construct polynomial matrices U and V with polynomial inverses such that UAV=D. The only nonzero entries of D are monic diagonal polynomials d₁,…,dᵣ satisfying d₁|d₂|…|dᵣ. A polynomial is monic when its leading coefficient is 1; the only monic constant is 1. Zero entries come after the nonzero entries, and zero is never normalized to monic.
Predict
Which changes are reversible in F[t]?
- Adding (t²+1) times one row to another.
- Multiplying a row by a nonzero field element c.
- Multiplying a row by t.
The first is reversed by subtraction and the second by multiplication by c⁻¹. The third is not generally reversible in F[t], since 1/t is not a polynomial. Over F=ℚ, dividing a row by 2 is permitted; over F=F₂, the scalar 2 is zero and cannot be inverted. Always state the coefficient field before using a scalar inverse.
Compare this with integer Smith reduction: positive integer pivots will become monic polynomial pivots, and strict decrease of a positive pivot will become strict decrease of its degree. Predict what should happen when a nonzero constant becomes the pivot.
Experiment
Carry out the following reduction without substituting for t. Rᵢ and Cⱼ denote rows and columns. Each multiplication or addition is in F[t], so the calculation works in every characteristic; in characteristic two, minus and plus agree.
| Operation | Current matrix, given by rows |
|---|
| Start | (t,0); (0,t−1) |
| R₁ ← R₁−R₂ | (t,1−t); (0,t−1) |
| C₁ ← C₁+C₂ | (1,1−t); (t−1,t−1) |
| R₂ ← R₂−(t−1)R₁ | (1,1−t); (0,t(t−1)) |
| C₂ ← C₂+(t−1)C₁ | (1,0); (0,t(t−1)) |
The accumulated matrices are U with rows (1,−1),(1−t,t) and V with rows (1,t−1),(1,t). Both determinants are 1. Multiplying first gives UA with rows (t,1−t),(−t(t−1),t(t−1)); multiplication by V gives the stated diagonal. Check both off-diagonal cancellations explicitly.
If the current matrix is M=UAV, a row operation E changes U to EU, while a column operation H changes V to VH. Initialize U and V as identities of sizes m and n. The entries of these matrices may be polynomials; they are not required to be constant changes of basis over F. Polynomial equivalence and constant-matrix similarity are different relations.
Understand
Units, division and the allowed operations
For nonzero polynomials, deg(fg)=deg f+deg g. Consequently a product can equal 1 only if both factors are nonzero constants, proving the assertion about units. A square polynomial matrix is invertible over F[t] exactly when its determinant is a nonzero constant. One direction follows by taking determinants of a polynomial inverse. Conversely, the adjugate formula divides only by a nonzero field element and therefore gives a polynomial inverse. Such matrices are called unimodular over F[t].
Row and column swaps, multiplication of one row or column by a nonzero constant, and addition of a polynomial multiple of another row or column are allowed. Their inverses have the same form. Products of their elementary matrices are unimodular. We do not allow multiplication of a row by a general nonzero polynomial.
For a nonzero polynomial p and any b, the polynomial division algorithm gives b=qp+r, where r=0 or deg r<deg p. The field assumption permits division by the leading coefficient. See Euclidean domains for the division argument. The zero remainder is handled separately; no degree of zero is needed below.
Clearing with a strictly decreasing degree
If the active rectangular block is zero, stop there. Otherwise move a nonzero entry to its upper-left corner by row and column swaps. Multiply its row by the inverse of its leading coefficient to make the pivot p monic.
Divide every other entry b in the pivot column by p, and subtract q times the pivot row from its row. A zero remainder clears that entry. A nonzero remainder is moved to the pivot position by a row swap and normalized to monic by a constant row scaling. Its degree is strictly smaller than the previous pivot degree. Restart the clearing procedure.
If the column is cleared without a restart, clear the pivot row by the analogous column operations. A nonzero remainder is swapped into the pivot position and made monic; again its degree strictly decreases and the procedure restarts. The swap can disturb the previously cleared column, so do not assume it remains zero. Without a restart these are finite scans. During the row-clearing scan, subtracting multiples of the cleared pivot column leaves all entries below the pivot row in the other columns unchanged. Thus a completed scan gives diag(p,B).
Why the lower-block divisibility test is essential
If p divides every entry of B, freeze it. Otherwise choose an entry b of B not divisible by p. Add its row to the pivot row. Because that row has zero in the pivot column, the pivot remains p, while b now occurs in the pivot row. Divide b=qp+r; here r≠0 and deg r<deg p. Subtract q times the pivot column from that entry’s column, swap that column into the pivot position, and normalize its new pivot r to monic. This produces a strictly smaller pivot degree. Restart clearing.
All restarts at a given active stage strictly decrease a nonnegative integer, the degree of a nonzero pivot. Between restarts there are only finitely many scans and a finite test of B. Hence that stage terminates. A degree-zero monic pivot is 1: every polynomial is divisible by it, so all remainders are zero and a divisibility repair is impossible. This is a valid terminal stage, not a request for a negative-degree pivot.
Now recurse inside B, extending its operations by identity matrices on all frozen coordinates. Induct on min(m,n). When p divides every entry of B, every later entry produced from B by polynomial additions, swaps and constant scalings remains divisible by p. Thus the next nonzero diagonal polynomial is divisible by p. Induction proves the remaining chain. Normalizing later pivots by nonzero constants preserves divisibility. This proves existence and termination of the complete monic Smith reduction, including the matrices U,V accumulated along the way.
Rectangles and zero boundaries
For a zero m by n matrix take identity U,V and no nonzero pivots. If either dimension is zero, the same convention gives an empty list of pivots; the empty square identity has determinant 1. For a nonzero rectangle, the number of pivots is at most min(m,n). Unused rows and columns are zero in D.
Over the fraction field F(t), U and V remain invertible. Thus the number r of nonzero diagonal entries equals the rank of A over F(t). This is useful for checking the zero portion of D, but fraction-field row reduction alone loses the nonunit polynomial factors. For example, (t) and (1) have equal fraction-field rank but are not unimodularly equivalent over F[t].
Monic minors determine the unique diagonal
For k≥1, let Δₖ(A) be the monic gcd of the k by k minors. If all such minors are zero, or none exist, put Δₖ(A)=0. Set Δ₀(A)=1. Polynomial Euclidean division ensures that finitely many polynomials generate the ideal of their gcd; normalizing to monic makes that generator unique.
Allowed operations preserve the ideal generated by the k-minors. For a row addition, multilinearity expresses a new minor as an old one plus a polynomial multiple of another old minor, with a possible row-order sign. If the source row is also selected, the extra determinant has a repeated row and vanishes. Swaps change selection or sign, and scaling by a nonzero constant changes a selected minor by a unit. The inverse operation proves the reverse ideal inclusion. Column operations have the same proof. Therefore Δₖ(UAV)=Δₖ(A) for the U,V constructed by the algorithm. The same statement for arbitrary unimodular U,V follows by expanding minors of their products: each new minor is a polynomial combination of old minors, and the polynomial inverses give the reverse inclusion.
For a Smith diagonal D, its nonzero k-minors are products of k selected diagonal entries. If their increasing indices are j₁,…,jₖ, then jᵢ≥i, so dᵢ divides the entry indexed by jᵢ. Hence d₁…dₖ divides every such product, and the product itself is one of the minors. Since it is monic, Δₖ(D)=d₁…dₖ for 1≤k≤r; all later Δₖ are zero. It follows that
dₖ=Δₖ(A)/Δₖ₋₁(A) for 1≤k≤r.
The quotient is exact polynomial division with a nonzero denominator in this range. Do not extend the ratio past rank. This proves uniqueness of the monic nonzero diagonal entries of a fixed matrix, including entries equal to 1. Without monic normalization they would be determined only up to nonzero constant factors.
The proof was for F[t]. It does not establish a degree-decreasing algorithm for an arbitrary principal ideal domain, nor a Smith theorem for every polynomial ring over a nonfield coefficient ring.
Apply
Change A to the rectangle with rows (t²,0,t²),(0,t(t−1),t(t−1)). Its third column is the sum of the first two. Clear it by two column subtractions. The remaining 2 by 2 block is t times the worked block. Use the same U and the corresponding extended V to predict the monic Smith form. Then check it by gcds of entries and minors, without cancelling the nonunit t from the original matrix.
Check the rectangular certificate and invariant factors
Use U with rows (1,−1),(1−t,t) and V with rows (1,t−1,−1),(1,t,−1),(0,0,1). Both determinants are 1. Multiplication gives rows (t,0,0),(0,t²(t−1),0). The first entry divides the second, and both are monic.
The entry gcd is t because gcd(t,t−1)=1. The three 2-minors of the original rectangle are t³(t−1), t³(t−1), and −t³(t−1); their monic gcd is t³(t−1). Dividing by Δ₁=t gives d₂=t²(t−1), agreeing with the certificate. In characteristic two the signs agree, but the gcd and proof are unchanged. The third column of V is (−1,−1,1), generating the polynomial kernel: the first two diagonal entries are nonzero in the domain F[t], so the first two transformed kernel coordinates must be zero.
Finally compare diag(t,t−1) with diag(t,t). The first has Δ₁=1; the second has Δ₁=t and is already a monic divisibility form. Equal matrix size and equal fraction-field rank do not imply the same polynomial presentation.
Continue
The integer Smith classification provides the parallel determinantal-divisor argument over ℤ. Here the field coefficients and polynomial degree supply the required division and descent, rather than positivity or integer size.
Continue to operator presentations. That lesson proves why a linear operator is represented by the polynomial relation matrix tI−A. Polynomial equivalence will become a statement about operator modules only after that connection is proved; it is not itself a constant change of matrix coordinates.
