Smith normal form

Smith normal form is the PID version of the familiar idea reduce a matrix to a clean diagonal. Given a matrix over a PID R (think F[x] or Z), you are allowed invertible row and column operations over that ring, and the goal is to push every entry off the diagonal to zero. What you reach is a diagonal matrix diag(d1, d2, ..., dr, 0, ..., 0) with d1 | d2 | ... | dr.

The allowed moves are exactly the invertible R-matrix operations: swap rows or columns, add an R-multiple of one row (or column) to another, and scale by a unit. You may not divide by a non-unit, which is the whole difference from field Gaussian elimination — over F[x] you cannot turn a degree-2 polynomial into 1, so the diagonal carries real polynomial content.

The diagonal entries d1, ..., dr, made monic and called the invariant factors of the matrix, are uniquely determined: they are gcds of the minors. For the matrix xI - A over F[x], the nonunit Smith diagonal entries are precisely the invariant factors of the operator A — so computing Smith normal form of xI - A is a direct, eigenvalue-free algorithm for the rational canonical form.

A practical caveat: doing this by hand with polynomial entries is bookkeeping-heavy, and over Z or finite fields naive elimination suffers from coefficient blow-up. Real implementations use modular or fraction-free methods, but the existence and uniqueness of the SNF are exactly what guarantee the canonical-form theorems.