<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>smithNormalForm(Matrix) -- smith normal form for a matrix over ZZ or a PID</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_solve.html">next</a> | <a href="___Size__Limit.html">previous</a> | <a href="_solve.html">forward</a> | <a href="___Size__Limit.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>smithNormalForm(Matrix) -- smith normal form for a matrix over ZZ or a PID</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>(D,P,Q) = smithNormalForm M</tt><br/><tt>(D,P) = smithNormalForm(M,ChangeMatrix=>{true,false})</tt><br/><tt>(D,Q) = smithNormalForm(M,ChangeMatrix=>{false,true})</tt><br/><tt>D = smithNormalForm(M,ChangeMatrix=>{false,false})</tt></div>
</dd></dl>
</div>
</li>
<li><span>Function: <a href="_smith__Normal__Form_lp__Matrix_rp.html" title="smith normal form for a matrix over ZZ or a PID">smithNormalForm</a></span></li>
<li><div class="single">Inputs:<ul><li><span><tt>M</tt>, <span>a <a href="___Matrix.html">matrix</a></span></span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>D</tt>, <span>a <a href="___Matrix.html">matrix</a></span>, The Smith normal form of <tt>M</tt></span></li>
<li><span><tt>P</tt>, <span>a <a href="___Matrix.html">matrix</a></span>, invertible (left) change of basis matrix</span></li>
<li><span><tt>Q</tt>, <span>a <a href="___Matrix.html">matrix</a></span>, invertible (right) change of basis matrix</span></li>
</ul>
</div>
</li>
<li><div class="single"><a href="_using_spfunctions_spwith_spoptional_spinputs.html">Optional inputs</a>:<ul><li><span><tt>ChangeMatrix => </tt><span><span>a <a href="___List.html">list</a></span>, <span>default value {true, true}</span>, of two Boolean elements. This determines whether the change of basis matrices <tt>P</tt> and/or <tt>Q</tt> are computed</span></span></li>
<li><span><tt>KeepZeroes => </tt><span><span>a <a href="___Boolean.html">Boolean value</a></span>, <span>default value true</span>, whether to keep rows and columns that are completely zero</span></span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div>This function produces a diagonal matrix <tt>D</tt>, and invertible matrices <tt>P</tt> and <tt>Q</tt> such that <tt>D = PMQ</tt>. Warning: even though this function is called the Smith normal form, it doesn't necessarily satisfy the more stringent condition that the diagonal entries <tt>d1, d2, ..., dn</tt> of <tt>D</tt> satisfy: <tt>d1|d2|...|dn.</tt>.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i3 : D == P * M * Q
o3 = true</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
<p>This function is the underlying routine used by <a href="_minimal__Presentation.html" title="compute a minimal presentation">minimalPresentation</a> in the case when the ring is <a href="___Z__Z.html" title="the class of all integers">ZZ</a>, or a polynomial ring in one variable over a field.</p>
<table class="examples"><tr><td><pre>i6 : prune coker M
o6 = cokernel | 135654 |
| 0 |
2
o6 : ZZ-module, quotient of ZZ</pre>
</td></tr>
</table>
In the following example, we test the result be checking that the entries of <tt>D1, P1 M Q1</tt> are the same. The degrees associated to these matrices do not match up, so a simple test of equality would return false.<table class="examples"><tr><td><pre>i7 : S = ZZ/101[t]
o7 = S
o7 : PolynomialRing</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i9 : P = random(S^4, S^4)
o9 = | 5 23 -6 -15 |
| 48 -12 15 -8 |
| -27 1 12 49 |
| -8 -21 32 3 |
4 4
o9 : Matrix S <--- S</pre>
</td></tr>
<tr><td><pre>i10 : Q = random(S^4, S^4)
o10 = | 16 -2 -23 -48 |
| 7 32 -50 49 |
| -32 32 33 -25 |
| 50 43 49 -50 |
4 4
o10 : Matrix S <--- S</pre>
</td></tr>
<tr><td><pre>i11 : M = P*D*Q
o11 = | -43t10-13t8-36t6+4t4-45t2-14 -39t10+7t8+24t6-28t4-16t2-10
| 4t10+20t8-36t6+31t4-12t2+6 -41t10-3t8-31t6+40t4-33t2-41
| 26t10+29t8-23t6+24t4-26t2+25 -14t10+31t8+42t6+34t4-12t2-49
| 49t10+43t8-29t6-2t4-17t2-38 28t10+39t8-9t6-47t4-35t2-8
-----------------------------------------------------------------------
-28t10-39t8+27t6-4t4-18t2+24 43t10+13t8-26t6-13t4-48t2-31 |
12t10-41t8+9t6-17t4+25t2+3 -4t10-20t8-11t6-36t4+21t2-39 |
-23t10-14t8-36t6-t4-22t2+35 -26t10-29t8+46t6-40t2+9 |
46t10+28t8+t6+32t4+26t2+13 -49t10-43t8+23t6+20t4+24t2+21 |
4 4
o11 : Matrix S <--- S</pre>
</td></tr>
<tr><td><pre>i12 : (D1,P1,Q1) = smithNormalForm M;</pre>
</td></tr>
<tr><td><pre>i13 : D1 - P1*M*Q1 == 0
o13 = true</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
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.</div>
</div>
<div class="single"><h2>Caveat</h2>
<div>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.</div>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_minimal__Presentation_lp__Module_rp.html" title="minimal presentation of a module">minimalPresentation(Module)</a> -- minimal presentation of a module</span></li>
</ul>
</div>
</div>
</body>
</html>
