next up previous contents
Next: Recipe 5---Linear Algebra Up: Recipes Previous: Recipe 3---reduction to

Recipe 4---the Shape Lemma

In practice, the lex order Gröbner bases for many problems have the following shape. (I don't give the technical conditions that ensure this because (a) I don't know them, and (b) it doesn't matter anyway, just compute the Gröbner basis and see if it has the shape. The theorem says that it will usually happen).

That is, once is determined, all the other variables are determined by evaluation of polynomials at . This simple shape is quite convenient to work with, on occasion.

Example. Eigenvalue problems. Eigenvalue problems with simple eigenvalues (i.e. no repeated roots) lead to Gröbner bases which have the specified shape. That is, we start with the polynomial system in the variables . Then our ordinary analysis gives the equivalent system from the characteristic polynomial, and once is identified we solve the linear system for the x's. This gives (on first blush) a solution rational function of (e.g. by Cramer's rule on a nonsingular submatrix), but remember that if we can transform any rational function of into a polynomial in by simplification (e.g. ). (I'm not certain simplicity of the eigenvalues is required).

This is clearly a Gröbner basis, and has the required shape.

Robert Corless
Tue Mar 12 21:09:19 EST 1996