Gröbner Bases and Elimination of Variables

Given a system of polynomial equations such as


that are satisfied by some points (x,y,z), one might ask what other equations are implied by these? For example, if we multiply these equations by some other arbitrary polynomials and add them together, such as

(y2+x2 y +x4) (y-x2 = 0 )
+ (-z-x3) (z-x3 = 0 )
y3-z2 = 0
a new equation.

One says in this situation that y3-z2 lies in the ideal generated by y-x2, z-x3 in the set R[x,y,z]. Here R[x,y,z] is just the set of all polynomials in x,y,z with real coefficients. In other words, y3-x2 is a linear combination of y-x2 and z-x3 using arbitrary polynomials as coefficients. If (x,y,z) is a point satisfying y-x2=0, z-x3=0, then any other element g(x,y,z) in the ideal generated by y-x2, z-x3 gives another valid equation g(x,y,z)=0 satisfied by (x,y,z).

In various contexts, one might not like the generators for the ideal that were given to us by a system of polynomial equations, and would prefer to "trade them in" for generators of the same ideal that have some better form. For example, this is what one wants to do when one wishes to eliminate the variable x from the above equations, i.e. one is trying to find the elements of the ideal that do not involve x. This is something that Gröbner bases allow us to do.

A Gröbner basis for an ideal I is a set of generators for I having a certain property with respect to an ordering < on the monomials, but we first need to explain what a monomial ordering is. A monomial ordering is a total ordering < of all the monomials {1, x, y, z, x2, y2, z2, xy, xz, yz, x3, ...}, which means that it is a binary relation that allows one to compare any two monomials m, m' and decide whether either m < m' or m > m'. In order to be a monomial ordering, the total ordering < is also required to have two other properties:

An example of such an order is the "lexicographic order" based on x > y > z. This ordering says that to compare two monomials m, m' we first see if one of them has smaller power of x and say this monomial is smaller in < if so. If they have same power of x, see if one has smaller power of y, and then this one is smaller in <. If they have same power of x and y, the one with smaller power of z is smaller in <. Here is part of the lexicographic order on monomials in R[x,y,z] based on x > y > z:

1 < z < z2 < ... < y < yz < yz2 < ... < y2 < y2z < y2z2 < ... < x < xz <...

For a given monomial order <, any polynomial f will have a unique term whose monomial is largest in the < order, called the <-leading term of f (NB: we are ignoring the coefficient in front of each term to obtain a monomial, e.g. a term like -5 x y3 has monomial x y3). If I is the ideal generated by polynomials f1, f2, ..., fr then we say {f1, f2, ..., fr} forms a Gröbner basis for I if any polynomial f in I has its <-leading term divisible by the <-leading term of some fi.

For example, if we use the lexicographic order based x > y > z, then f1 = y-x2, f2= z - x3 do NOT form a Gröbner basis for their ideal, since f= y3-z2 has <-leading term y3, which is not divisible by either the <-leading term of f1 (which is x2) or the <-leading term of f2 (which is x3). On the other hand, there is an algorithm due to Buchberger for computing the Gröbner basis of the ideal generated by polynomials {f1,f2,...,fr} with respect to any monomial orderings, and we can apply this for lexicographic orderings in Maple by using the "gbasis" command and specify the monomial ordering to be "plex":

> with(grobner);

  [finduni, finite, gbasis, gsolve, leadmon, normalf, solvable, spoly]

> gbasis({y-x^2,z-x^3},[x,y,z],plex);

                  2                2           2    3
          [- y + x , - z + x y, - y  + x z, - z  + y ]
Notice that the output Gröbner basis contains the element f=y3-z2. This illustrates the following crucial fact about lexicographic Gröbner bases and elimination of variables (see Cox, Little, and O'Shea Section 3.1):

FACT: Let {f1,...,fr} be polynomials in the variables x1,...,xn and compute a Gröbner basis for their ideal I with respect to the lexicographic monomial order based on x1 > x2 > ... > xn. Then any polynomial f in I that does not involve x1,..., xk-1 is in the ideal generated by those elements of the Gröbner basis that do not involve x1,...,xk-1.

In other words, the latter subset of the Gröbner basis generates all the polynomials one can obtain from f1,...,fr by elimination of the variables x1,...,xk-1.

We should point out that there is a more classical alternative to using Gröbner bases for eliminating variables in polynomial equations. This technique uses resultants, which one can read about in Cox, Little, and O'Shea Sections 3.5 and 3.6.

Elimination of variables also has a very simple geometric intepretation related to projections. For an explanation, see Projections, profiles, and envelopes

Go To: Transforming a Parametrization into an Implicit Algebraic Equation
Go To: Gröbner bases and Elimination of Variables
Up: Introduction
Vic Reiner <>
Frederick J. Wicklin <>
Last modified: Thu May 2 10:43:36 1996