About eliminate(...)

 

This post is motivated by a recent answer where I needed a necessary and sufficient condition for three straight lines in space be concurrent. I had to use determinants because the eliminate command did not provide the correct answer.
Investigating the cause, I saw that eliminate uses an heuristic algorithm, instead of using Groebner bases (when possible).


Here is an example.

We want to eliminate the unknowns x an y in the system

a*x + y = 0,  b*x+y+1 = 0, c*x+2*y = 0

 

sys:=[a*x + y, b*x + y + 1, c*x + 2*y];

[a*x+y, b*x+y+1, c*x+2*y]

(1)

eliminate(sys, [x,y]);

[{x = 0, y = 0}, {1}]

(2)

So, apparently, the elimination is not possible, i.e. for each triple (a,b,c), the system in x and y is incompatible.
This is not true. For example,

 

eval(sys,[a=1,b=3,c=2]);

[x+y, 3*x+y+1, 2*x+2*y]

(3)

eval(%, [x=-1/2, y=1/2]);

[0, 0, 0]

(4)

eliminate  obtained its result this way (just like a superficial human):

solve(sys[[1,3]], [x,y]);
eval(sys[2],%[]); # The result obtained by eliminate

[[x = 0, y = 0]]

 

1

(5)

Now, the correct result (also by hand):

solve(sys[[1,2]], {x,y});
eval(sys[3],%);
numer(simplify(%));

{x = 1/(a-b), y = -a/(a-b)}

 

c/(a-b)-2*a/(a-b)

 

c-2*a

(6)

So, for c = 2*a  (and a <> b)  the system in x,y  is compatible.

 

This result can be obtained with Groebner bases.

Groebner:-Basis(sys, plex(x,y,a,b,c));

[2*a-c, 2*b*y-c*y-c, c*x+2*y, b*x+y+1]

(7)

remove(has, %, {x,y});

[2*a-c]

(8)

Note that it is more efficient to use lexdeg([x,y], [a,b,c])  instead of plex(x,y,a,b,c).

Groebner:-Basis(sys, lexdeg([x,y], [a,b,c]));

[2*a-c, 2*b*y-c*y-c, c*x+2*y, b*x+y+1]

(9)

The conclusion is that eliminate should use internally Groebner:-Basis for polynomial systems.
Until then, we can use it ourselves!

 


Please Wait...