Matrix reduction plays a fundamental role in the study of vector spaces and linear transformations. Reduction of a matrix to a canonical or normal form finds its use in almost all applied fields of science. While there are many different normal forms a matrix can be reduced to, a normal form is usually the product of much simpler and well-understood (e.g., diagonal, upper/lower triangular, etc) matrices. Since, the reduction process faithfully carries most of the nice properties of the original matrix, one can use a normal form to infer some of those properties from matrices with relatively simple structure.
The choice of the normal form can sometimes be demanded by a particular application, or be limited by the algebraic operations one is allowed to perform on the entries of the original matrix. Today we consider, for reduction, only \mathbb Z -matrices, i.e., matrices that are allowed to have only integer entries. As a consequence, the only permitted operations on the entries of such a matrix are addition and multiplication—but not division. We denote by \mathcal_(\mathbb Z) the set of all integer matrices with n rows and m columns. In the special case of square matrices ( m=n ), we simply call it \mathcal_(\mathbb Z) or \mathcal_(\mathbb Z) . Note that the identity matrix, I_ , of dimension m is a \mathbb Z -matrix, i.e., I_m\in\mathcal_(\mathbb Z) .
Although our hands are now tied by the restriction on the operations allowed on a matrix A\in\mathcal_(\mathbb Z) , we can still follow the usual definitions of matrix addition, subtraction, and multiplication— also determinant and inverse of a square matrix. For a square matrix A\in\mathcal_(\mathbb Z) , its determinant is defined the usual way. Also, A is said to have an inverse B\in\mathcal_(\mathbb Z) if AB=BA=I_n . The set of all invertible (square) matrices of dimension n is denoted by GL_(\mathbb Z) .
Given an A\in\mathcal_(\mathbb Z) , we seek invertible matrices P\in GL_(\mathbb Z) and Q\in GL_(\mathbb Z) such that D=Q^AP, where D is an n\times m diagonal integer matrix: \newcommand\bigzero<\makebox(0,0)<\text<\huge0>>> \begin \begin \begin d_1 & 0 & \ldots & 0 \\ 0 & d_2 & \ldots & 0\\ 0 & \ldots & \ldots & 0 \\ 0 & \ldots & 0 & d_k \\ \end & <\huge0>_ \\ \hdashline \\ <\huge0>_ & <\huge0>_ \end \end with d_i\geq0 for all i=1, 2, \ldots, k and d_1| d_2| \ldots | d_k .
Note: - the diagonal matrix D always exists, as we allow it to be a zero matrix; it is also unique. - P,Q may not, however, be unique [artin]. - if A is viewed as the matrix of a linear transformation T:G_1\to G_2 between two finitely-generated free abelian groups, then P and Q are the basechange matrices for G_1 and G_2 , respectively.
Unlike the other popular canonical forms—e.g., the Jordan normal form for matrices over an algebraically-closed field—the Smith normal form is particularly relevant in the context of \mathbb Z -modules, more generally R -modules [artin]. In the field of combinatorial topology, the reduction to Smith normal form facilitates the computation of the homology groups of finte simplicial complexes [Munkres84].
As stated above without a proof that the reduction of an integer matrix to a Smith normal form always exists. We now present the steps one can perform to decompose a given matrix. The basis of the reduction process involves three elementary operations. We invoke them repeatedly on the original matrix in the right order. We are going to use three elementary row operations and three corresonding column operations.
Each of the following row (and column) operations can also be described as pre (and post) multiplication by an elementary matrix. For each elementary operation, there is an associated elementary matrix, which is obtained by performing the same operation on the identity matrix of the right size.
We first define and then demonstrate the elementary row operations. The outcome A' of each row operation on A is a pre-multiplication of A by an elementary matrix E , i.e., A'=EA . The three types of row operations are as follows:
The outcome A' of each column operation on A is post-multiplication of A by an elementary matrix E , i.e., A'=AE . The three types of column operations are as follows:
The operations are best understood when demonstrated on an example matrix. To that end, we first generate a random matrix A with integer (between -5 and 5 ) entries by choosing the number of rows and columns using the sliders.
viewof m = Inputs.range([1, 6], value: 5, step: 1, label: "Number of rows (n):" >) viewof n = Inputs.range([1, 6], value: 4, step: 1, label: "Number of cols (m):" >)