<?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>Schreyer orders -- induced monomial order on a free module</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_packing_spmonomials_spfor_spefficiency.html">next</a> | <a href="_monomial_sporders_spfor_spfree_spmodules.html">previous</a> | forward | backward | <a href="_monomial_sporders_spfor_spfree_spmodules.html">up</a> | <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>
<div><a href="index.html" title="">Macaulay2Doc</a> > <a href="_rings.html" title="">rings</a> > <a href="_monomial_sporderings.html" title="">monomial orderings</a> > <a href="_monomial_sporders_spfor_spfree_spmodules.html" title="">monomial orders for free modules</a> > <a href="___Schreyer_sporders.html" title="induced monomial order on a free module">Schreyer orders</a></div>
<hr/>
<div><h1>Schreyer orders -- induced monomial order on a free module</h1>
<div>The Schreyer order is a monomial order on a free module that is particularly efficient for computing Gröbner bases and syzygies. The size of Gröbner bases of submodules using such orders is often much much smaller than if a position over term or term over position order would be used. We call these Schreyer orders, after Frank Olaf-Schreyer, who used them to give an algorithm for syzygies, and who also recognized many of their beneficial properties. See Schreyer.... for more information.<p/>
Given a free <i>R</i>-module <i>G</i>, a set of monomials <i>m<sub>0</sub>, ..., m<sub>(</sub>s-1)</i> of <i>G</i>, and a monomial order on the monomials of <i>G</i>, the induced order, or, Schreyer order on <i>F = R<sup>s</sup></i> is defined by: <i>a F<sub>i</sub> > b F<sub>j</sub></i> (in <i>F</i>) iff <i>a m<sub>i</sub> > b m<sub>j</sub></i> (in <i>G</i>), or <i>a m<sub>i</sub> and b m<sub>j</sub></i> are scalar multiples of each other, and <i>i>j</i>, where <i>F<sub>i</sub></i> are the unit column vectors of <i>F</i> <p/>
In Macaulay2, free modules with a Schreyer order on them can be created using <a href="_schreyer__Order_lp__Matrix_rp.html" title="create a matrix with the same entries whose source free module has a Schreyer monomial order">schreyerOrder(Matrix)</a>.<table class="examples"><tr><td><pre>i1 : R = ZZ/101[a..f];</pre>
</td></tr>
<tr><td><pre>i2 : m = matrix{{a,b,c,d}};
1 4
o2 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i3 : m1 = schreyerOrder m
o3 = | a b c d |
1 4
o3 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i4 : F = source m1
4
o4 = R
o4 : R-module, free, degrees {1, 1, 1, 1}</pre>
</td></tr>
<tr><td><pre>i5 : g = syz m1
o5 = {1} | -b 0 -c 0 0 -d |
{1} | a -c 0 0 -d 0 |
{1} | 0 b a -d 0 0 |
{1} | 0 0 0 c b a |
4 6
o5 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i6 : leadTerm g
o6 = {1} | 0 0 0 0 0 0 |
{1} | a 0 0 0 0 0 |
{1} | 0 b a 0 0 0 |
{1} | 0 0 0 c b a |
4 6
o6 : Matrix R <--- R</pre>
</td></tr>
</table>
In Macaulay2, free modules are displayed without any indication of whether they are endowed with a Schreyer order or not. To determine whether one is, use <a href="_schreyer__Order_lp__Module_rp.html" title="obtain Schreyer order information">schreyerOrder(Module)</a>. If the result is the zero matrix, then the monomial order associated with this free module is not a Schreyer order. In that case, the monomial order for the free module is the one determined directly from the ring.<table class="examples"><tr><td><pre>i7 : schreyerOrder target m
o7 = 0
1
o7 : Matrix 0 <--- R</pre>
</td></tr>
<tr><td><pre>i8 : schreyerOrder source g
o8 = 0
6
o8 : Matrix 0 <--- R</pre>
</td></tr>
</table>
Over quotient rings, the multiplications <i>a m<sub>i</sub></i> and <i>b m<sub>j</sub></i> are over the ambient polynomial ring, not the quotient.<p/>
It is fine for the free module <tt>G</tt> above to be endowed with a Schreyer order too.<p/>
The only places that Schreyer orders are considered is in computation of Gröbner bases, syzygies, and free resolutions, and with the <a href="_lead__Term.html" title="get the greatest term">leadTerm</a> routine.<p/>
The size of the Gröbner bases of syzygy modules is often dramatically smaller if the monomial order is the Schreyer order, as in the following example.<table class="examples"><tr><td><pre>i9 : R = QQ[a..f];</pre>
</td></tr>
<tr><td><pre>i10 : I = ideal"abc-def,a2c-d2f,aef-bcd,a3-d3,af2-cd2"
2 2 3 3 2
o10 = ideal (a*b*c - d*e*f, a c - d f, - b*c*d + a*e*f, a - d , - c*d +
-----------------------------------------------------------------------
2
a*f )
o10 : Ideal of R</pre>
</td></tr>
<tr><td><pre>i11 : F = syz gens I
o11 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3 0
{3} | 0 0 aef-def abe-bde 0 a3-d3
{3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0 0
{3} | -bc-ef 0 -bcf-cef -b2c-bce -abc+def -a2c+d2f
{3} | 0 0 0 0 0 0
-----------------------------------------------------------------------
acd-acf a2c-a2f+acf-d2f -a2f+acf a2d-a2f
-bcd-ace+bcf+aef ace-bcf-aef+def abc+ace-bcf-aef -a2e+ade
d2f-df2 cd2-adf-d2f+df2 cd2-adf-d2f+df2 d3-d2f
c2e-cef -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
-cde+def cde-def cde-def -ade+d2e
-----------------------------------------------------------------------
a2e+bdf+aef d3-d2f 0 0 0 cd2-af2 0 ad2-adf
ae2-bef a2e-d2e -ade+abf 0 a2c-df2 0 cd2-af2 -ade+bdf
ade+d2e+abf ad2-adf -d3+d2f -cd2+af2 0 0 0 0
-bce-ce2 -ace+ef2 cde-bcf 0 -ac2+f3 0 0 cde-bf2
-abe+de2 -a2e+ade bd2-d2e bcd-aef acd-a2f abc-def a2c-d2f a2b-d2e
-----------------------------------------------------------------------
0 abc2-def2 ac2f-df3 ab2c+bdef+ae2f cdef-bcf2 |
0 -b2c2+e2f2 ac2e-bc2f-acef+ef3 -b3c+abe2+ae3-be2f 0 |
0 bcdf-acef cdf2-af3 bd2e+d2e2+b2df -bc2d+ef3 |
cd2-af2 0 -c3e+c2ef -bce2-ce3 0 |
a3-d3 0 c2de-acef-cdef+aef2 -b2de+de3 b2c2-e2f2 |
5 23
o11 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i12 : betti gens gb syz F
0 1
o12 = total: 23 67
5: 1 .
6: 18 19
7: 4 27
8: . 8
9: . 8
10: . 5
o12 : BettiTally</pre>
</td></tr>
<tr><td><pre>i13 : G = schreyerOrder F
o13 = {3} | a2+ad+d2 bcd-aef cd2+a2f+d2f a2b+bd2+ade a3-d3 0
{3} | 0 0 aef-def abe-bde 0 a3-d3
{3} | a2+ad+d2 abc-def acd+adf+d2f abd+bd2+d2e 0 0
{3} | -bc-ef 0 -bcf-cef -b2c-bce -abc+def -a2c+d2f
{3} | 0 0 0 0 0 0
-----------------------------------------------------------------------
acd-acf a2c-a2f+acf-d2f -a2f+acf a2d-a2f
-bcd-ace+bcf+aef ace-bcf-aef+def abc+ace-bcf-aef -a2e+ade
d2f-df2 cd2-adf-d2f+df2 cd2-adf-d2f+df2 d3-d2f
c2e-cef -bc2-c2e+bcf+cef -bc2-c2e+bcf+cef -bcd+ace-cde+bcf
-cde+def cde-def cde-def -ade+d2e
-----------------------------------------------------------------------
a2e+bdf+aef d3-d2f 0 0 0 cd2-af2 0 ad2-adf
ae2-bef a2e-d2e -ade+abf 0 a2c-df2 0 cd2-af2 -ade+bdf
ade+d2e+abf ad2-adf -d3+d2f -cd2+af2 0 0 0 0
-bce-ce2 -ace+ef2 cde-bcf 0 -ac2+f3 0 0 cde-bf2
-abe+de2 -a2e+ade bd2-d2e bcd-aef acd-a2f abc-def a2c-d2f a2b-d2e
-----------------------------------------------------------------------
0 abc2-def2 ac2f-df3 ab2c+bdef+ae2f cdef-bcf2 |
0 -b2c2+e2f2 ac2e-bc2f-acef+ef3 -b3c+abe2+ae3-be2f 0 |
0 bcdf-acef cdf2-af3 bd2e+d2e2+b2df -bc2d+ef3 |
cd2-af2 0 -c3e+c2ef -bce2-ce3 0 |
a3-d3 0 c2de-acef-cdef+aef2 -b2de+de3 b2c2-e2f2 |
5 23
o13 : Matrix R <--- R</pre>
</td></tr>
<tr><td><pre>i14 : betti gens gb syz G
0 1
o14 = total: 23 45
5: 1 .
6: 18 19
7: 4 22
8: . 4
o14 : BettiTally</pre>
</td></tr>
</table>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_lead__Term.html" title="get the greatest term">leadTerm</a> -- get the greatest term</span></li>
<li><span><a href="_schreyer__Order_lp__Matrix_rp.html" title="create a matrix with the same entries whose source free module has a Schreyer monomial order">schreyerOrder(Matrix)</a> -- create a matrix with the same entries whose source free module has a Schreyer monomial order</span></li>
<li><span><a href="_schreyer__Order_lp__Module_rp.html" title="obtain Schreyer order information">schreyerOrder(Module)</a> -- obtain Schreyer order information</span></li>
<li><span><a href="_gb.html" title="compute a Gröbner basis">gb</a> -- compute a Gröbner basis</span></li>
<li><span><a href="_syz.html" title="the syzygy matrix">syz</a> -- the syzygy matrix</span></li>
<li><span><a href="_resolution.html" title="projective resolution">resolution</a> -- projective resolution</span></li>
<li><span><a href="_betti.html" title="display degrees">betti</a> -- display degrees</span></li>
</ul>
</div>
</div>
</body>
</html>
