1.1 Monomial orderings

The basis ingredience for all standard basis algorithms is the ordering of the monomials (and the concept of the leading term: the term with the highest monomial).

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\vert\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$.

The ordering < is called a wellordering iff 1 is the smallest monomial. Most of the algorithms work for general orderings.

Robbiano (cf.[R]) proved that any semigroup ordering can be defined by a matrix $A \in GL(n, {\rm\bf R})$ as follows (matrix ordering):

Let $a_1, \ldots, a_k$ be the rows of A, then $x^\alpha < x^\beta$ if and only if there is an i with $a_j \alpha = a_j\beta$ for j < i and $a_i \alpha < a_i \beta$. Thus, $x^\alpha < x^\beta$ if and only if $A\alpha$ is smaller than $A\beta$ with respect to the lexicographical ordering of vectors in ${\rm\bf R}^n$.

We call an ordering a degree ordering if it is given by a matrix with coefficients of the first row either all positive or all negative.

Let K be a field; for $g \in K[\underline{x}]$, $g \not= 0$, let $\bf L(g)$ be the leading monomial with respect to the ordering <¹ and $\bf c(g)$ the coefficient of L(g) in g, that is g = c(g)L(g) + smaller terms with respect to <.

< is an elimination ordering for $x_{r+1}, \ldots, x_n$ iff $L(g) \in K[x_1, \ldots, x_r]$ implies $g \in K[x_1, \ldots, x_r]$).