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 is a total ordering < on the set of monomials (power products) which is compatible with the natural semigroup structure, i.e. implies for any .
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 as follows (matrix ordering):
Let be the rows of A, then if and only if there is an i with for j < i and . Thus, if and only if is smaller than with respect to the lexicographical ordering of vectors in .
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 , , let be the leading monomial with respect to the ordering <1 and the coefficient of L(g) in g, that is g = c(g)L(g) + smaller terms with respect to <.
< is an elimination ordering for iff implies ).