Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Smith normal form
Summary
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.
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 .
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.