@comment -*-texinfo-*-
@comment $Id: math.doc,v 1.6 1998-05-06 11:49:30 Singular Exp $
@comment this file contains the mathematical background of Singular

@menu
* Monomial orderings::
* Standard bases::
* Syzygies and resolutions::
* Characteritic sets::
* References::
@end menu
@c ---------------------------------------------------------------------------
@node Monomial orderings, Standard bases, , Mathematical background
@section Monomial orderings
@cindex Monomial orderings
@tex
A monomial ordering (term ordering) on $K[x_1, \ldots, x_n]$ is
a total ordering $<$ on the
set of monomials (power products) $\{x^\alpha|\alpha \in \bf{N}^n\}$
which is compatible with the
natural semigroup structure, i.e.\ $x^\alpha < x^\beta$ implies $x^\gamma
x^\alpha < x^\gamma x^\beta$ for any $\gamma \in \bf{N}^n$.
We do not require
$<$ to be  a wellordering.
@end tex
@ifinfo
A monomial ordering (term ordering) on $[x_1, ..., x_n] is
a total ordering < on the
set of monomials (power products) @{x^a | a in N^n@}
which is compatible with the
natural semigroup structure, i.e. x^a < x^b implies x^c*x^a < x^c*x^b for any
c in N^n.
We do not require
< to be  a wellordering.
@end ifinfo
@ifset singularmanual
See the literature cited in @ref{Introduction}, (section 'Background').
@end ifset

@sc{Singular} offers the following monomial orderings which are implemented
in an effective way:
@menu
* Global orderings:: lp, dp, wp, Dp, Wp.
* Local orderings:: ls, ds, ws, Ds, Ws.
* Module orderings:: c, C.
* Matrix orderings:: M.
* Product orderings::
* Extra weight vector:: a.
@end menu
@iftex
@itemize @bullet
@item
global orderings or p-orderings: @code{lp, dp, Dp, wp, Wp} (p refers to polynomial ring)
@item
local orderings or s-orderings: @code{ls, ds, Ds, ws, Ws} (s refers to series ring)
@item
module orderings @code{c, C} (ordering of the components of a vector)
@item
matrix orderings @code{M} (may be used to define any allowed ordering)
@item
any of the above orderings may be combined to yield product or
block orderings.
@item
ordering @code{a} (inserting an extra weight vector)
@end itemize
@end iftex

@tex
Global orderings are wellorderings (i.e.\ $1 < x_i$ for each variable
$x_i$), local orderings satisfy $1 > x_i$ for each variable.   If some variables are ordered globally and others locally we
call it a mixed ordering.   Local or mixed orderings are not wellorderings.

If $K$ is the groundfield, $x = (x_1, \ldots, x_n)$ the
variables and $<$ a monomial ordering, then {\bf Loc K}$[x]$ denotes the
localization of $K[x]$ with respect to the multiplicatively closed set $\{1 +
g \mid g = 0$ or $g \in K[x]\backslash \{0\}$ and $L(g) < 1\}$.   $L(g)$
denotes the leading monomial of $g$, i.e.\ the biggest monomial of $g$ with
respect to $<$.   The result of any computation which uses standard basis
computations has to be interpreted in {\bf Loc K}$[x]$ (like @code{std, syz, res,
mres, sres, mult, degree, dim, hilb, mstd}, etc.).
@end tex
@ifinfo
Global orderings are wellorderings (i.e.1 < x_i for each variable
x_i), local orderings satisfy 1 > x_i for each variable.
If some variables are ordered globally and others locally we
call it a mixed ordering.   Local or mixed orderings are not wellorderings.

If K is the groundfield, x = (x_1, @dots{}, x_n) the
variables and < a monomial ordering, then Loc K[x] denotes the
localization of K[x] with respect to the multiplicatively closed set @{1 +
g | g = 0 or g in K[x]\@{0@} and L(g) < 1@}.   L(g)
denotes the leading monomial of g, i.e. the biggest monomial of g with
respect to <.   The result of any computation which uses standard basis
computations has to be interpreted in Loc K[x] (like @code{std, syz, res,
mres, sres, mult, degree, dim, hilb, mstd}, etc.).
@end ifinfo
@c --------------------------------------------------------------------------
@node Global orderings, Local orderings, , Monomial orderings
@subsection Global orderings
@cindex Global orderings

For all these orderings: Loc K[x] = K[x]

@table @asis
@item lp:
lexicographical ordering.
@*
@ifinfo
x^a < x^b  <==> there is an i,  1 <= i <= n :
@* a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
$x^\alpha < x^\beta  \Leftrightarrow  \exists\; 1 \le i \le n :
\alpha_1 = \beta_1, \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i <
\beta_i$.
@end tex
@item dp:
degree reverse lexicographical ordering.
@*
@ifinfo
x^a < x^b <==>
@* deg(x^a) < deg(x^b), where deg(x^a) = a_1 + @dots{} + a_n,
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_n = b_n, @dots{}, a_(i+1) = b_(i+1), a_i > b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) < \deg(x^\beta)$,
where $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ or
@end tex
@*@tex
    \phantom{$x^\alpha < x^\beta \Leftrightarrow $}$ \deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:$
@end tex
@*@tex
    \phantom{$x^\alpha < x^\beta \Leftrightarrow$}$\alpha_n = \beta_n,
    \ldots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i$.
@end tex
@item Dp:
degree lexicographical ordering.
@*
@ifinfo
x^a < x^b <==>
@* deg(x^a) < deg(x^b)
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) < \deg(x^\beta)$,
where $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ or
@end tex
@*@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow $} $\deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:$
@end tex
@*@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow $} $\alpha_1 = \beta_1,
    \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i < \beta_i$.
@end tex
@item wp:
weighted reverse lexicographical ordering.
@*
@ifinfo
 wp(w_1, @dots{}, w_n), w_i
@end ifinfo
@tex
${\tt wp}(w_1, \ldots, w_n),\; w_i$
@end tex
 positive integers,
 is defined as @code{dp}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@item Wp:
weighted lexicographical ordering.
@*
@ifinfo
 Wp(w_1, @dots{}, w_n), w_i
@end ifinfo
@tex
${\tt Wp}(w_1, \ldots, w_n),\; w_i$
@end tex
 positive integers,
 is defined as @code{Dp}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@end table
@c --------------------------------------------------------------------------
@node Local orderings, Module orderings, Global orderings, Monomial orderings
@subsection Local orderings
@cindex Local orderings

For ls, ds, Ds and, if the weights are positive integers, also for ws and
Ws,  we have
@ifinfo
Loc K[x] = K[x]_(x),
@end ifinfo
@tex
$Loc\, K[x] = K[x]_{(x)}$,
@end tex
 the localization of K[x] at the
maximal ideal
@ifinfo
 (x_1, @dots{}, x_n).
@end ifinfo
@tex
\ $(x_1, ..., x_n)$.
@end tex

@table @asis
@item ls:
negative lexicographical ordering.
@*
@ifinfo
x^a < x^b  <==> there is an i,  1 <= i <= n :
@* a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i > b_i.
@end ifinfo
@tex
$x^\alpha < x^\beta  \Leftrightarrow  \exists\; 1 \le i \le n :
\alpha_1 = \beta_1, \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i >
\beta_i$.
@end tex
@item ds:
negative degree reverse lexicographical ordering.
@*
@ifinfo
x^a < x^b <==>
@* deg(x^a) > deg(x^b), where deg(x^a) = a_1 + @dots{} + a_n,
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_n = b_n, @dots{}, a_(i+1) = b_(i+1), a_i > b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) > \deg(x^\beta)$,
where $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ or
@end tex
@*@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow$ } $\deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:$
@end tex
@*@tex
    \phantom{ $x^\alpha < x^\beta \Leftrightarrow $} $\alpha_n = \beta_n,
    \ldots, \alpha_{i+1} = \beta_{i+1}, \alpha_i > \beta_i$.
@end tex
@item Ds:
negative degree lexicographical ordering.
@*
@ifinfo
x^a < x^b <==>
@* deg(x^a) > deg(x^b)
@* or
@* deg(x^a) = deg(x^b) and there exist an i, 1 <= i <= n:
@*     a_1 = b_1, @dots{}, a_(i-1) = b_(i-1), a_i < b_i.
@end ifinfo
@tex
    $x^\alpha < x^\beta \Leftrightarrow \deg(x^\alpha) > \deg(x^\beta)$,
where $\deg(x^\alpha) = \alpha_1 + \cdots + \alpha_n,$ or
@end tex
@*@tex
    \phantom{$ x^\alpha < x^\beta \Leftrightarrow$ }$ \deg(x^\alpha) =
    \deg(x^\beta)$ and $\exists\ 1 \le i \le n:$
@end tex
@*@tex
    \phantom{$ x^\alpha < x^\beta \Leftrightarrow$ } $\alpha_1 = \beta_1,
    \ldots, \alpha_{i-1} = \beta_{i-1}, \alpha_i < \beta_i$.
@end tex
@item ws:
(general) weighted reverse lexicographical ordering.
@*
@ifinfo
 ws(w_1, @dots{}, w_n), w_1
@end ifinfo
@tex
${\tt ws}(w_1, \ldots, w_n),\; w_1$
@end tex
 a nonzero integer,
@ifinfo
w_2,@dots{},w_n
@end ifinfo
@tex
$w_2,\ldots,w_n$
@end tex
 any integer (including 0),
 is defined as @code{ds}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@item Ws:
(general) weighted lexicographical ordering.
@*
@ifinfo
 Ws(w_1, @dots{}, w_n), w_1
@end ifinfo
@tex
${\tt Ws}(w_1, \ldots, w_n),\; w_1$
@end tex
 a nonzero integer,
@ifinfo
w_2,@dots{},w_n
@end ifinfo
@tex
$w_2,\ldots,w_n$
@end tex
 any integer (including 0),
 is defined as @code{Ds}
 but with
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@end table

@c --------------------------------------------------------------------------
@node Module orderings, Matrix orderings, Local orderings, Monomial orderings
@subsection Module orderings
@cindex Module orderings

@sc{Singular} offers also orderings on the set of ``monomials''
@ifinfo
@{ x^a*gen(i) | a in N^n, 1 <= i <= r @} on Loc K[x]^r = Loc K[x]gen(1)
+ @dots{} + Loc K[x]gen(r), where gen(1), @dots{}, gen(r) denote the canonical
generators of Loc K[x]^r, the r-fold direct sum of Loc K[x].
@end ifinfo
@tex
$\{ x^a gen(i) | a \in N^n, 1 \leq i \leq r \}$ on Loc K$[x]^r$ = Loc K[x]$gen(1)
+ \ldots +$Loc K[x]$gen(r)$, where $gen(1), \ldots, gen(r)$ denote the canonical
generators of Loc K[x]$^r$, the r-fold direct sum of Loc K[x].
@end tex

We have two possibilities, either to give priority to the component of a
vector of
@ifinfo
Loc K[x]^r
@end ifinfo
@tex
\ $Loc K[x]^r$\
@end tex
or (which is the default in @sc{Singular}) to give priority
to the coefficients.
The orderings @code{(<,c)} and @code{(<,C)} give priority to the coefficients;
@code{(c,<)} and @code{(C,<)} give priority to the components.
@*Let < be any of the monomial orderings of Loc K[x] as above.

@table @asis
@item (<,C):
@ifinfo
<_m = (<,C) denotes the module ordering (giving priority to the coefficients):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* x^a < x^b
@* or
@* x^a = x^b  and  i < j.
@end ifinfo
@tex
$<_m = (<,C)$ denotes the module ordering (giving priority to the coefficients):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow x^\alpha < x^\beta$,
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{\quad \quad $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow $}
      or $x^\alpha = x^\beta $ and $ i < j$.
@end tex

@strong{Example:}
@example
@c example
  ring r = 0, (x,y,z), ds;
  // the same as ring r = 0, (x,y,z), (ds, C);
  [x+y2,z3+xy];
  [x,x,x];
@c example
@end example

@item (C,<):
@ifinfo
<_m = (C, <) denotes the module ordering (giving priority to the
component):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* i<j
@* or
@* i = j and x^a < x^b.
@end ifinfo
@tex
$<_m = (C, <)$ denotes the module ordering (giving priority to the component):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad   $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow i < j$,
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{$\quad \quad x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow $}
      or $ i = j $ and $ x^\alpha < x^\beta $.
@end tex

@strong{Example:}
@example
@c example
  ring r = 0, (x,y,z), (C,lp);
  [x+y2,z3+xy];
  [x,x,x];
@c example
@end example

@item (<,c):
@ifinfo
<_m = (<,c) denotes the module ordering (giving priority to the coefficients):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* x^a < x^b
@* or
@* x^a = x^b  and  i > j.
@end ifinfo
@tex
$<_m = (<,c)$ denotes the module ordering (giving priority to the coefficients):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow x^\alpha < x^\beta$,
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{\quad \quad $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow $}
      or $x^\alpha = x^\beta $ and $ i > j$.
@end tex

@strong{Example:}
@example
@c example
  ring r = 0, (x,y,z), (lp,c);
  [x+y2,z3+xy];
  [x,x,x];
@c example
@end example

@item (c,<):
@ifinfo
<_m = (c, <) denotes the module ordering (giving priority to the
component):
@* x^a*gen(i) <_m x^b*gen(j) <==>
@* i>j
@* or
@* i = j and x^a < x^b.
@end ifinfo
@tex
$<_m = (c, <)$ denotes the module ordering (giving priority to the component):
@end tex
@iftex
@*
@end iftex
@tex
\quad \quad   $x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow i > j$,
@end tex
@iftex
@*
@end iftex
@tex
    \phantom{$\quad \quad x^\alpha gen(i) <_m x^\beta gen(j) \Leftrightarrow $}
      or $ i = j $ and $ x^\alpha < x^\beta $.
@end tex

@strong{Example:}
@example
@c example
  ring r = 0, (x,y,z), (c,lp);
  [x+y2,z3+xy];
  [x,x,x];
@c example
@end example
@end table

@ifinfo
The output of a vector v in K[x]^r with components v_1,
@dots{}, v_r has the format v_1 * gen(1) + @dots{} + v_r * gen(r)
@end ifinfo
@tex
The output of a vector $v$ in $K[x]^r$ with components $v_1,
\ldots, v_r$ has the format $v_1 * gen(1) + \ldots + v_r * gen(r)$
@end tex
unless the ordering starts with @code{c}.
@ifinfo
In this case a vector will be written as [v_1, @dots{}, v_r].
@end ifinfo
@tex
In this case a vector will be written as $[v_1, \ldots, v_r]$.
@end tex
In all cases @sc{Singular} can read the
input in both formats.

@c --------------------------------------------------------------------------
@node Matrix orderings, Product orderings, Module orderings,Monomial orderings
@subsection Matrix orderings
@cindex Matrix orderings

Let M be an invertible n x n matrix with integer coefficients and
@ifinfo
M_1, @dots{}, M_n
@end ifinfo
@tex
M$_1, \ldots,$ M$_n$
@end tex
 the rows of M.

The M-ordering < is the following:
@ifinfo
x^a < x^b <==> there exists an i: 1 <= i <= n :
M_1*a = M_1*b, @dots{}, M_(i-1)*a = M_(i-1)*b, M_i*a < M_i*b.
@end ifinfo
@tex
$x^a < x^b \Leftrightarrow$  there exists an $i: 1 <= i <= n :$
M$_1*a = $M$_1*b, \ldots, $M$_{i-1}*a = $M$_{i-1}*b$ and M$_i*a < $M$_i*b$.
@end tex

Thus,
@ifinfo
x^a < x^b
@end ifinfo
@tex
$x^a < x^b$
@end tex
if and only if M*a is smaller than M*b
with respect to the lexicographical ordering.

It is known that any monomial ordering can be represented by a matrix M in
GL(n,R), but, of course, only integer coefficients are of relevance in
practice.

The following matrices represent (for 3 variables) the global and
local orderings defined above (note that the matrix is not uniquely determined
by the ordering):

@ifinfo
@table @asis
@item lp:
 1   0   0
@* 0   1   0
@* 0   0   1
@item dp:
 1   1   1
@* 0   0  -1
@* 0  -1   0
@item Dp:
 1   1   1
@* 1   0   0
@* 0   1   0
@item wp(1,2,3):
 1   2   3
@* 0   0  -1
@* 0  -1   0
@item Wp(1,2,3):
 1   2   3
@* 1   0   0
@* 0   1   0
@item ls:
-1   0   0
@* 0  -1   0
@* 0   0  -1
@item ds:
-1  -1  -1
@* 0   0  -1
@* 0  -1   0
@item Ds:
-1  -1  -1
@* 1   0   0
@* 0   1   0
@item ws(1,2,3):
-1  -2  -3
@* 0   0  -1
@* 0  -1   0
@item Ws(1,2,3):
-1  -2  -3
@* 1   0   0
@* 0   1   0
@end table
@end ifinfo
@tex

lp:
$\left(\matrix{
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 0 & 0 & 1 \cr
 }\right)$
\quad dp:
$\left(\matrix{
 1 & 1 & 1 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Dp:
$\left(\matrix{
 1 & 1 & 1 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

wp(1,2,3):
$\left(\matrix{
 1 & 2 & 3 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Wp(1,2,3):
$\left(\matrix{
 1 & 2 & 3 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

ls:
$\left(\matrix{
-1 & 0 & 0 \cr
 0 &-1 & 0 \cr
 0 & 0 &-1 \cr
 }\right)$
\quad ds:
$\left(\matrix{
-1 &-1 &-1 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Ds:
$\left(\matrix{
-1 &-1 &-1 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$

ws(1,2,3):
$\left(\matrix{
-1 &-2 &-3 \cr
 0 & 0 &-1 \cr
 0 &-1 & 0 \cr
 }\right)$
\quad Ws(1,2,3):
$\left(\matrix{
-1 &-2 &-3 \cr
 1 & 0 & 0 \cr
 0 & 1 & 0 \cr
 }\right)$
@end tex

Product orderings represented by  a matrix:

@ifinfo
@table @asis
@item (dp(3), wp(1,2,3)):
1  1  1  0  0  0
@*0  0  -1  0  0  0
@*0  -1  0  0  0  0
@*0  0  0  1  2  3
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@item (Dp(3), ds(3)):
1  1  1  0  0  0
@*1  0  0  0  0  0
@*0  1  0  0  0  0
@*0  0  0  -1  -1  -1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@end table
@end ifinfo
@tex
@table @asis
@item (dp(3), wp(1,2,3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
0&  0&  -1&  0&  0&  0 \cr
0&  -1&  0&  0&  0&  0 \cr
0&  0&  0&  1&  2&  3 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@item (Dp(3), ds(3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
1&  0&  0&  0&  0&  0 \cr
0&  1&  0&  0&  0&  0 \cr
0&  0&  0&  -1&  -1&  -1 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@end table
@end tex

Orderings with extra weight vector (see below) represented by  a matrix:

@ifinfo
@table @asis
@item (dp(3), a(1,2,3),dp(3)):
1  1  1  0  0  0
@*0  0  -1  0  0  0
@*0  -1  0  0  0  0
@*0  0  0  1  2  3
@*0  0  0  1  1  1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@item (a(1,2,3,4,5),Dp(3), ds(3)):
1  2  3  4  5  0
@*1  1  1  0  0  0
@*1  0  0  0  0  0
@*0  1  0  0  0  0
@*0  0  0  -1  -1  -1
@*0  0  0  0  0  -1
@*0  0  0  0  -1  0
@end table
@end ifinfo
@tex
@table @asis
@item (dp(3), a(1,2,3),dp(3)):
$\left(\matrix{
1&  1&  1&  0&  0&  0 \cr
0&  0&  -1&  0&  0&  0 \cr
0&  -1&  0&  0&  0&  0 \cr
0&  0&  0&  1&  2&  3 \cr
0&  0&  0&  1&  1&  1 \cr
0&  0&  0&  0&  0&  -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@item (a(1,2,3,4,5),Dp(3), ds(3)):
$\left(\matrix{
1&  2&  3&  4&  5&  0 \cr
1&  1&  1&  0&  0&  0 \cr
1&  0&  0&  0&  0&  0 \cr
0&  1&  0&  0&  0&  0 \cr
0&  0&  0&  -1&  -1&  -1 \cr
0&  0&  0&  0&  0 & -1 \cr
0&  0&  0&  0&  -1&  0 \cr
 }\right)$
@end table
@end tex

@*@strong{Example}:
@example
@c example
  ring r = 0, (x,y,z), M(1, 0, 0,
                         0, 1, 0,
                         0, 0, 1);
@c example
@end example
@*which may also be written as:
@example
@c example
  intmat m[3][3]=1, 0, 0, 0, 1, 0, 0, 0, 1;
  m;
  ring r = 0, (x,y,z), M(m);
  r;
@c example
@end example

If the ring has n variables and the matrix contains less than n x n entries
an error message is given, if there are more entries,
the last ones will be ignored.

@strong{WARNING:} @sc{Singular}
does not check whether the matrix has full rank.   In such a case some
computations might not terminate, others might give a nonsense result.

Having these matrix orderings @sc{Singular} can compute standard bases for
any monomial ordering which is compatible with the natural semigroup structure.
In practice the global and local orderings together with block orderings should be
sufficient in most cases. These orderings are faster than the corresponding
matrix orderings, since evaluating a matrix product is time consuming.

@c --------------------------------------------------------------------------
@node Product orderings, Extra weight vector, Matrix orderings, Monomial orderings
@subsection Product orderings
@cindex Product orderings

Let
@ifinfo
x = (x_1, @dots{}, x_n) = x(1..n) and y = (y_1, @dots{}, y_m) =
y(1..m)
@end ifinfo
@tex
$x = (x_1, \ldots, x_n) = x(1..n)$ and $y = (y_1, \ldots, y_m) =
y(1..m)$
@end tex
 be two ordered sets of variables,
@ifinfo
<_1 a monomial
ordering on Loc K[x] and <_2 a monomial ordering on Loc K[y].   The product
ordering (or block ordering) < = (<_1,<_2) on Loc K[x,y] is the following:
@*x^a y^b < x^A y^B <==>
@*x^a <_1 x^A
@*or
@*x^a = x^A  and  y^b <_2 y^B.
@end ifinfo
@iftex
@tex
$<_1$ a monomial
ordering on $Loc K[x]$ and $<_2$ a monomial ordering on $Loc K[y]$.   The product
ordering (or block ordering) $<\ := (<_1,<_2)$ on $Loc K[x,y]$ is the following:
@end tex
@*@tex
\quad \quad $x^a y^b < x^A y^B \Leftrightarrow x^a <_1 x^A$
@end tex
@*@tex
\phantom{\quad \quad $x^a y^b < x^A y^B \Leftrightarrow$}
or $x^a = x^A$ and $y^b <_2 y^B$.
@end tex
@end iftex

Inductively one defines the product ordering of more than two monomial
orderings.

In @sc{Singular}, any of the above global orderings, local orderings or matrix
ordering may be combined (in an arbitrary manner and length) to a product
ordering.   E.g. @code{(lp(3), M(1, 2, 3, 1, 1, 1, 1, 0, 0), ds(4), ws(1,2,3))}
defines: @code{lp} on the first 3 variables, the matrix ordering
@code{M(1, 2, 3, 1, 1, 1, 1, 0, 0)} on the next 3 variables,
@code{ds} on the next 4 variables and
@code{ws(1,2,3)} on the last 3 variables.

@c --------------------------------------------------------------
@node Extra weight vector, , Product orderings, Monomial orderings
@subsection Extra weight vector
@cindex Extra weight vector

@ifinfo
a: a(w_1, @dots{}, w_n),
@end ifinfo
@tex
a:\quad ${\tt a}(w_1, \ldots, w_n),\; $
@end tex
@ifinfo
w_1,@dots{},w_n
@end ifinfo
@tex
$w_1,\ldots,w_n$
@end tex
 any integer (including 0), defines
@ifinfo
  deg(x^a) = w_1 a_1 + @dots{} + w_n a_n.
@end ifinfo
@tex
$\deg(x^\alpha) = w_1 \alpha_1 + \cdots + w_n\alpha_n.$
@end tex
@*
@ifinfo
x^a < x^b <== deg(x^a) < deg(x^b)
@end ifinfo
@tex
    $$x^\alpha < x^\beta \Leftarrow \deg(x^\alpha) < \deg(x^\beta),$$
@end tex
@ifinfo
@*
x^a > x^b <== deg(x^a) > deg(x^b)
@end ifinfo
@tex
    $$x^\alpha > x^\beta \Leftarrow \deg(x^\alpha) > \deg(x^\beta)$$
@end tex
@*An extra weight vector does not define a monomial ordering by itself:
it can only be used in combination with other orderings
to insert an extra line of weights into the ordering
matrix.
@*@strong{Example}:
@example
  ring r = 0, (x,y,z), (a(1,2,3),
                       wp(4,5,2));
  ring s = 0, (x,y,z), (a(1,2,3),dp);
  ring q=  0, (a,b,c,d),(lp(1),a(1,2,3),ds);
@end example
@c ---------------------------------------------------------------------------
@node Standard bases, Syzygies and resolutions,Monomial orderings, Mathematical background
@section Standard bases
@cindex Standard bases

@table @code
@item @strong{Definition:}
@tex
Let $I \subseteq Loc_< K[\underline{x}]$ be an ideal.
${\bf L}(I)$ denotes the ideal of $Loc_< K[\underline{x}]$ generated
by $\{L(f) | f \in I\}$.

$f_1, \ldots, f_s \in I$ is called a {\bf standard basis} of $I$ if
$\{L(f_1), \ldots, L(f_s)\}$ generates the ideal
$L(I) \subset Loc_< K[\underline{x}]$.
@end tex
@ifinfo
Let I in Loc K[x] be an ideal.
L(I) denotes the ideal of Loc K[x] generated by @{ L(f) | f in I@}.

f_1, @dots{}, f_s in I is called a @strong{standard basis} of I if
@{ L(f_1), @dots{}, L(f_s) @} generates the ideal L(I) in Loc K[x].
@end ifinfo
@item @strong{Properties:}
@table @asis
@item Normalform:
@tex
A function $NF : K[\underline{x}]^r \times \{G | G\  standard basis\} \to K[\underline{x}]^r, (p,G) \mapsto NF(p|G)$, is called a {\bf normal form}
if for any $p \in K[\underline{x}]^r$ and any $G$ the following holds:  if $NF(p|G)
\not= 0$ then $L(g) \not| L(NF(p|G))$ for all $g \in G$.   $NF(g|G)$ is called
the {\bf normal form of} $\bf p$ {\bf with respect to} $\bf G$.
@end tex
@ifinfo
A function NF : K[x]^r x @{G | G  standard basis@} -> K[x]^r, (p,G) -> NF(p|G),
is called a  @strong{normal form}
if for any p in K[x]^r and any G the following holds:  if NF(p|G) <> 0
then L(g) does not divide L(NF(p|G)) for all g in G.   NF(g|G) is called
the @strong{normal form} of p with respect to G.
@end ifinfo
@item ideal membership:
@tex
$f \in I$ iff $NF(f,std(I)) = 0$ for $I \subseteq R$ resp. $I \subseteq R^r$.
@end tex
@ifinfo
f in I iff NF(f,std(I)) = 0 for I in R resp. I in R^r.
@end ifinfo
@end table

@item @strong{Example:}
@end table

@c ---------------------------------------------------------------------------
@node Syzygies and resolutions, Characteritic sets, Standard bases, Mathematical background
@section Syzygies and resolutions
@cindex Syzygies and resolutions

Let A=matrix(M), then a free resolution of
@ifinfo
M1=coker(A)=coker(A1)
is a long exact sequence
@*...--> F2 --A2-> F1 --A1-> F0-->M1-->0,
@end ifinfo
@tex
$M_1=coker(A)=coker(A_1)$
is a long exact sequence
$$...\longrightarrow F_2 \buildrel{A_2}\over{\longrightarrow} F_1 \buildrel{A_1}\over{\longrightarrow} F_0\longrightarrow M_1\longrightarrow 0,$$
@end tex
@*where the columns of the matrix
@tex
$A_1$
@end tex
@ifinfo
A1
@end ifinfo
are generators
of M.
The length of the sequence is at most n, where n is the number of variables in
the polynomial resp. power series ring.
Free resolutions over other rings may be infinite.
Considered as modules,
@tex
$A_1$
@end tex
@ifinfo
A1
@end ifinfo
is a set of generators of the input,
@tex
$A_2$
@end tex
@ifinfo
A2
@end ifinfo
consists of a set of generators of the first szyzgy module of
@tex
$A_1$,
@end tex
@ifinfo
A1,
@end ifinfo
etc.
@c ---------------------------------------------------------------------------
@node Characteritic sets,References,Syzygies and resolutions,Mathematical background
@section Characteritic sets
@cindex Characteritic sets

@tex
Let $>$ be the lexicographical ordering $x_1 < ... < x_n$ on $R=K[x_1,...,x_n]$.
For $f \in R$ let lvar(f) (the leading variable of f) be the largest
variable in lead(f) (the leading term of f with respect to $>$),
i.e. if $f=a_k(x_1,...,x_{k-1})x_k^s+...+a_0(x_1,...,x_{k-1})$ for some
$k \leq n$ then $lvar(f)=x_k$, moreover let $ini(f):=a_k(x_1,...,x_{k-1})$.

A set $T=\{f_1,...,f_r\} \subset R$ is called triangular if $lvar(f_1)<...<lvar(f_r)$.
The pseudoremainder $r=prem(g,f)$ of $g$ with respect to $f$ is defined by
$ini(f)^a*g=q*f+r$ with the property $deg_{lvar(f)}(r)<deg_{lvar(f)}(f)$,
a minimal.

(T,U) is called a triangular system, if T is a triangular set such that ini(T)
does not vanish on $Zero(T) \setminus Zero(U)
( =:Zero(T\setminus U))$.

T is called irreducible if for every i there are no $d_i$,$f_i'$,$f_i''$ with
the property:
$$   lvar(d_i)<lvar(f_i) $$
$$   lvar(f_i')=lvar(f_i'')=lvar(f_i)$$
$$   0 \not\in prem(\{ d_i, ini(f_i'), ini(f_i'')\},\{ f_1,...,f_(i-1)\})$$
such that $prem(d_i*f_i-f_i'*f_i'',\{f_1,...,f_(i-1)\})=0$.

(T,U) is irreducible if T is irreducible.

Let $G=\{g_1,...,g_s\}$ then there are irreducible triangular sets $T_1,...,T_l$
such that $Zero(G)=\bigcup(i=1..l: Zero(T_i\setminus I_i))$
where $I_i=\{ini(f), f \in T_i \}$.
@end tex
@ifinfo
Let > be the lexicographical ordering x_1 < ... < x_n on R=K[x_1,...,x_n].
For f in R let lvar(f) (the leading variable of f) be the largest
variable in lead(f) (the leading term of f with respect to >),
i.e. if f=a_k(x_1,...,x_(k-1))x_k^s+...+a_0(x_1,...,x_(k-1)) for some
k<=n then lvar(f)=x_k, moreover let ini(f):=a_k(x_1,...,x_(k-1)).

A set T=@{f_1,...,f_r@} in R is called triangular if lvar(f_1)<...<lvar(f_r).
The pseudoremainder r=prem(g,f) of g with respect to f is defined by
ini(f)^a*g=q*f+r with the property deg_(lvar(f))(r)<deg_(lvar(f))(f),s
a minimal.

(T,U) is called a triangular system, if T is a triangular set such that ini(T)
does not vanish on the zero set of T \ zero set of U
( =:Zero(T\U)).

T is called irreducible if for every i there are no d_i,f_i',f_i'' with
the property:
@*   lvar(d_i)<lvar(f_i)
@*   lvar(f_i')=lvar(f_i'')=lvar(f_i)
@*   0 not in prem(@{ d_i, ini(f_i'), ini(f_i'')@},@{ f_1,...,f_(i-1)@})
@*such that prem(d_i*f_i-f_i'*f_i'',@{f_1,...,f_(i-1)@})=0.

(T,U) is irreducible if T is irreducible.

Let G=@{g_1,...,g_s@} then there are irreducible triangular sets T_1,...,T_l
such that Zero(G)=Union(i=1..l: Zero(T_i\I_i))
where I_i=@{ini(f), f in T_i @}.
@end ifinfo

@*@strong{Example:}
@example
@c example
  ring R= 0,(x,y,z,u),dp;
  ideal i=-3zu+y2-2x+2,
          -3x2u-4yz-6xz+2y2+3xy,
          -3z2u-xu+y2z+y;
  print(char_series(i));
@c example
@end example
@c ---------------------------------------------------------------------------
@node References,,Characteritic sets,Mathematical background
@section References
@cindex References

For a description of the basic algorithms, together with many examples
and comparisons, cf. Grassmann, H.; Greuel, G.-M.; Martin, B.; Neumann,
W.; Pfister, G.; Pohl, W.;
@tex
Sch\"onemann,
@end tex
@ifinfo
 Schoenemann
@end ifinfo
 H.; Siebert, T.:  On an
implementation of standard bases and syzygies in  @sc{Singular},
Proceedings of the Workshop  Computational Methods in Lie theory in AAECC (1995).

For a mathematical background, in particular for general (global, local
or mixed) orderings and resolutions, cf. Greuel, G.-M.; Pfister, G.:
Advances and improvements in the theory of standard bases and
syzygies, Arch. d. Math. 63(1995)