Gröbner Bases and Elimination of Variables

y-x²=0
z-x³=0

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

(y²+x² y +x⁴) (y-x² = 0 )
+ (-z-x³) (z-x³ = 0 )
gives
y³-z² = 0

One says in this situation that y³-z² lies in the ideal generated by y-x², z-x³ 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, y³-x² is a linear combination of y-x² and z-x³ using arbitrary polynomials as coefficients. If (x,y,z) is a point satisfying y-x²=0, z-x³=0, then any other element g(x,y,z) in the ideal generated by y-x², z-x³ 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, x², y², z², xy, xz, yz, x³, ...}, 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:

• The monomial 1 is smaller than any other monomial m.
• Given any three monomials m, m', m'' with m' < m'' we can conclude that m m' < m m''.

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 < z² < ... < y < yz < yz² < ... < y² < y²z < y²z² < ... < 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 y³ has monomial x y³). If I is the ideal generated by polynomials f₁, f₂, ..., f_r then we say {f₁, f₂, ..., f_r} forms a Gröbner basis for I if any polynomial f in I has its <-leading term divisible by the <-leading term of some f_i.

For example, if we use the lexicographic order based x > y > z, then f₁ = y-x², f₂= z - x³ do NOT form a Gröbner basis for their ideal, since f= y³-z² has <-leading term y³, which is not divisible by either the <-leading term of f₁ (which is x²) or the <-leading term of f₂ (which is x³). On the other hand, there is an algorithm due to Buchberger for computing the Gröbner basis of the ideal generated by polynomials {f₁,f₂,...,f_r} 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 ]

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

In other words, the latter subset of the Gröbner basis generates all the polynomials one can obtain from f₁,...,f_r by elimination of the variables x₁,...,x_k-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