next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Macaulay2Doc :: smithNormalForm(Matrix)

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

Synopsis

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.

See also