The first goal is to find invertible square matrices formula_11 and formula_12 such that the product formula_13 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 formula_14 as a map from formula_15 (the free formula_16-module of rank formula_17) to formula_18 (the free formula_16-module of rank formula_20), there are isomorphisms formula_21 and formula_22 such that formula_23 has the simple form of a diagonal matrix. The matrices formula_11 and formula_12 can be found by starting out with identity matrices of the appropriate size, and modifying formula_11 each time a row operation is performed on formula_14 in the algorithm by the corresponding column operation (for example, if row formula_28 is added to row formula_29 of formula_14, then column formula_29 should be subtracted from column formula_28 of formula_11 to retain the product invariant), and similarly modifying formula_12 for each column operation performed. Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant formula_35 where formula_36 denote current values and formula_14 denotes the original matrix; eventually the matrices in this invariant become diagonal. Only invertible row and column operations are performed, which ensures that formula_11 and formula_12 remain invertible matrices.