6
$\begingroup$

For the computation of elimination ideals via Mathematica's GroebnerBasis method, e.g.

grob = GroebnerBasis[eqs, {a, b, c, d, e}, {x, y}, MonomialOrder -> EliminationOrder];

what is the default monomial-ordering weight matrix? I imagine that the weight matrix for this example is composed of a $2\times 2$ block and a $5\times 5$ block, but I'm not sure what their contents should be.

  • I don't think they're both lex (the identity weight matrix for each block).
  • I don't think they 're both grevlex (1s on the upper-triangular entries for each block) either.

Any insight would be very helpful.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

It's not actually a block ordering. EliminationOrder constructs the weight matrix as follows. Order variables so that those to be eliminated precede (are to the left of) the ones to retain. Then row 1 is a vector of ones for the elimination variables and zeros for the rest. Row two is a vector of all ones. The remaining rows break ties based on grevlex (for all variables).

Here is pedestrian code I often use for constructing such matrices. The first argument is the number to eliminate, the second is the total variable count. An auxiliary function creates a matrix suitable for the grevlex term order.

drlMatrix[n_] := 
 Prepend[Table[-KroneckerDelta[j + k - (n + 1)], {j, n - 1}, {k, n}], 
  Table[1, {n}]]

elimMatrix[n1_, n2_] := 
 Module[{row1, rest}, row1 = Join[Table[1, {n1}], Table[0, {n2 - n1}]];
  rest = drlMatrix[n2];
  rest = Drop[rest, {-n1}];
  Prepend[rest, row1]]

Example: weight matrix to eliminate three variables from a total of seven.

In[105]:= elimMatrix[3, 7]

(* Out[105]= {{1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 
  0, 0, -1}, {0, 0, 0, 0, 0, -1, 0}, {0, 0, 0, 0, -1, 0, 0}, {0, 
  0, -1, 0, 0, 0, 0}, {0, -1, 0, 0, 0, 0, 0}} *)
In[82]:= elimMatrix[3, 7]

Here is the slightly incorrect one I had previously created, before the mistake was caught.

(* Out[82]= {{1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 
  0, 0, -1}, {0, 0, 0, 0, -1, 0, 0}, {0, 0, 0, -1, 0, 0, 0}, {0, 
  0, -1, 0, 0, 0, 0}, {0, -1, 0, 0, 0, 0, 0}} *)

I think I have been using the "wrong" variant for 15 years in some work, and never noticed. They both give valid elimination orders so it's not a huge issue. But still...

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for this. Executing sys = {-a d - a b c x - a b e y, a b c x - e x - 2 d x^2, 2 x^2 - c y - a b e y, a*x + b*y^2}; g1 = GroebnerBasis[sys, {a, b, c, d, e}, {x, y}, MonomialOrder -> EliminationOrder]; g2 = GroebnerBasis[sys, {a, b, c, d, e}, {x, y}, MonomialOrder -> elimMatrix[2, 7]]; results in distinct bases, i.e. g1 != g2. Should I interpret this as Mathematica using a slightly different matrix than your solution, or am I misunderstanding? $\endgroup$
    – Kathryn
    Commented Oct 26, 2018 at 21:17
  • 1
    $\begingroup$ Good catch. You could interpret it as me falling on my face (thud; ouch). I had a mistake in that matrix and I will edit to fix it. $\endgroup$
    – Daniel Lichtblau
    Commented Oct 27, 2018 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.