# smithNormalForm(Matrix) -- smith normal form for a matrix over ZZ or a PID

## Synopsis

• Function: smithNormalForm
• Usage:
(D,P,Q) = smithNormalForm M
(D,P) = smithNormalForm(M,ChangeMatrix=>{true,false})
(D,Q) = smithNormalForm(M,ChangeMatrix=>{false,true})
D = smithNormalForm(M,ChangeMatrix=>{false,false})
• Inputs:
• M,
• Optional inputs:
• ChangeMatrix => a list, default value {true, true}, of two Boolean elements. This determines whether the change of basis matrices P and/or Q are computed
• KeepZeroes => , default value true, whether to keep rows and columns that are completely zero
• Outputs:
• D, , The Smith normal form of M
• P, , invertible (left) change of basis matrix
• Q, , invertible (right) change of basis matrix

## Description

This function produces a diagonal matrix D, and invertible matrices P and Q such that D = PMQ. Warning: even though this function is called the Smith normal form, it doesn't necessarily satisfy the more stringent condition that the diagonal entries d1, d2, ..., dn of D satisfy: d1|d2|...|dn..
 i1 : M = matrix{{1,2,3},{1,34,45},{2213,1123,6543},{0,0,0}} o1 = | 1 2 3 | | 1 34 45 | | 2213 1123 6543 | | 0 0 0 | 4 3 o1 : Matrix ZZ <--- ZZ i2 : (D,P,Q) = smithNormalForm M o2 = (| 135654 0 0 |, | 1 33471 -43292 0 |, | 171927 -42421 54868 |) | 0 1 0 | | 0 1 0 0 | | 93042 -22957 29693 | | 0 0 1 | | 0 0 1 0 | | -74119 18288 -23654 | | 0 0 0 | | 0 0 0 1 | o2 : Sequence i3 : D == P * M * Q o3 = true i4 : (D,P) = smithNormalForm(M, ChangeMatrix=>{true,false}) o4 = (| 135654 0 0 |, | 1 33471 -43292 0 |) | 0 1 0 | | 0 1 0 0 | | 0 0 1 | | 0 0 1 0 | | 0 0 0 | | 0 0 0 1 | o4 : Sequence i5 : D = smithNormalForm(M, ChangeMatrix=>{false,false}, KeepZeroes=>true) o5 = | 135654 0 0 | | 0 1 0 | | 0 0 1 | 3 3 o5 : Matrix ZZ <--- ZZ

This function is the underlying routine used by minimalPresentation in the case when the ring is ZZ, or a polynomial ring in one variable over a field.

 i6 : prune coker M o6 = cokernel | 135654 | | 0 | 2 o6 : ZZ-module, quotient of ZZ
In the following example, we test the result be checking that the entries of D1, P1 M Q1 are the same. The degrees associated to these matrices do not match up, so a simple test of equality would return false.
 i7 : S = ZZ/101[t] o7 = S o7 : PolynomialRing i8 : D = diagonalMatrix{t^2+1, (t^2+1)^2, (t^2+1)^3, (t^2+1)^5} o8 = | t2+1 0 0 0 | | 0 t4+2t2+1 0 0 | | 0 0 t6+3t4+3t2+1 0 | | 0 0 0 t10+5t8+10t6+10t4+5t2+1 | 4 4 o8 : Matrix S <--- S i9 : P = random(S^4, S^4) o9 = | 24 19 -8 -38 | | -36 19 -22 -16 | | -30 -10 -29 39 | | -29 -29 -24 21 | 4 4 o9 : Matrix S <--- S i10 : Q = random(S^4, S^4) o10 = | 34 -18 -28 16 | | 19 -13 -47 22 | | -47 -43 38 45 | | -39 -15 2 -34 | 4 4 o10 : Matrix S <--- S i11 : M = P*D*Q o11 = | -33t10+37t8+46t6+48t4-24t2+5 -36t10+22t8-16t6+21t4+27t2+33 | 18t10-11t8+2t6+7t4-37t2-13 38t10-12t8+13t6+42t4-50t2-29 | -6t10-30t8-10t6+t4+33t2+46 21t10+4t8+43t6+41t4+19 | -11t10+46t8+8t6-4t4+29t2-16 -12t10+41t8+3t6+20t4-31t2 ----------------------------------------------------------------------- 25t10+24t8+47t6-40t4-13t2-26 -21t10-4t8+36t6+37t4+35t2+17 | -32t10+42t8-45t6+16t4-12t2-46 39t10-7t8+6t6-41t4+10t2+2 | -23t10-14t8-19t6-36t4-25t2-17 -13t10+36t8-21t6-23t4+49t2+2 | 42t10+8t8+13t6-44t4+2t2-8 -7t10-35t8-39t6-9t4+35t2+33 | 4 4 o11 : Matrix S <--- S i12 : (D1,P1,Q1) = smithNormalForm M; i13 : D1 - P1*M*Q1 == 0 o13 = true i14 : prune coker M o14 = cokernel | t10+5t8+10t6+10t4+5t2+1 0 0 0 | | 0 t6+3t4+3t2+1 0 0 | | 0 0 t4+2t2+1 0 | | 0 0 0 t2+1 | 4 o14 : S-module, quotient of S
This routine is under development. The main idea is to compute a Gröbner basis, transpose the generators, and repeat, until we encounter a matrix whose transpose is already a Gröbner basis. This may depend heavily on the monomial order.

## Caveat

The Smith normal form itself is NOT returned! This function is under development, and its performance might need to be improved. Also, this function doesn't warn the user if the ring is not a PID.