In mathematics, the Smith normal form (sometimes abbreviated SNF) is a normal form that can be defined for any matrix (not necessarily square) with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith. Definition Let A be a nonzero m×n matrix over a principal ideal domain R. There exist invertible and -matrices S, T (with coefficients in R) such that the product S A T is and the diagonal elements satisfy for all . This is the Smith normal form of the matrix A. The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as where (called i-th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix A and . Algorithm The first goal is to find invertible square matrices and such that the product is diagonal. This is the hardest part of the algorithm. Once diagonality is achieved, it becomes relatively easy to put the matrix into Smith normal form. Phrased more abstractly, the goal is to show that, thinking of as a map from (the free -module of rank ) to (the free -module of rank ), there are isomorphisms and such that has the simple form of a diagonal matrix. The matrices and can be found by starting out with identity matrices of the appropriate size, and modifying each time a row operation is performed on in the algorithm by the corresponding column operation (for example, if row is added to row of , then column should be subtracted from column of to retain the product invariant), and similarly modifying for each column operation performed. Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant where denote current values and denotes the original matrix; eventually the matrices in this