Re: Interpretation of Reduce results (long)
- To: mathgroup at smc.vnet.net
- Subject: [mg3906] Re: Interpretation of Reduce results (long)
- From: danl (Daniel Lichtblau)
- Date: Sun, 5 May 1996 23:12:11 -0400
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In article <4lse19$hjq at dragonfly.wolfram.com>
sherod at boussinesq.Colorado.EDU (Scott Herod) writes:
>
> I guess that I am a little surprised by the following output of Reduce.
>
> In[15]:=
> test = {z^2*p[1] + z*p[2] + p[4],
> y + z^2*q[1] + z*q[2] + q[4]}
>
> Out[15]=
> 2 2
> {z p[1] + z p[2] + p[4], y + z q[1] + z q[2] + q[4]}
>
> In[16]:=
> Reduce[test == 0, {y}, {p[1],q[1]}]
>
> Out[16]=
> p[4] == -(z p[2]) && y == -q[4] && z == 0 ||
>
> p[4] == -(z p[2]) && y == -q[4] && z == 0 || z != 0
>
>
> In particular I was worried that with the final case in Out[16], z != 0,
> more was not said. Certainly arbitrary values of z, y, p's and q's
won't
> satisfy the original equations even if z != 0.
>
> Can someone comment?
>
> Scott Herod
>
I will try to explain what happens using our development version because
it gives simpler results.
In[30]:= Reduce[{z^2*p1 + z*p2 + p4 == 0, y + z^2*q1 + z*q2 + q4 == 0},
{y}, {p1, q1}]
Out[30]= y == -q4 && p4 == 0 || z != 0
You can verify that the above version's result boils down to this. So the
question is, why does this make sense? (If you omit the "why", then the
answer is simply "Yes, it does," and I can go home early for my son's
birthday party).
Roughly speaking, when you eliminate two variables from two equations,
you are left with nothing. That is, generically you can only eliminate n-1
variables from n equations. In the case where the equations are linear it
is not hard to see why this is so. Let me first get a bit technical about
how it is done, and then give a simple linear example to demonstrate.
Variable elimination between polynomials is formed by projecting from
the full polynomial ideal to an elimination ideal (shoot, we were having a
fine time, and now I've gone and used some jargon). This is done
computationally by forming what is called a Groebner basis, where the
"elimination" variables are ordered highest. For those who have no idea
what I'm talking about, but remember their college linear algebra, this is
a generalization of Gaussian elimination aka row reduction. The
elimination variables become the first columns of your matrix. You row
reduce it to echelon form, and then get rid of (eliminate) all rows that
have nonzero entries in these columns. Simple example: say we want to
eliminate y from
{3*x + 4*y - 11 == 0, 2*x - y == 0}
As y is the elimination variable, we form a matrix whose first column
corresponds to it. So we get the matrix
{{4, 3, -11}, {-1, 2, 0}}
and the row echelon form is
{{1, 0, -2}, {0, 1, -1}}
We ditch the first row, and then translate the second row into an equation
involving the original variables. But it will not involve y, because we
specifically removed all rows that had nonzero values in the y column. We
obtain the equation x - 1 == 0. Note that this indeed agrees with the
Mathematica result below.
In[36]:= Eliminate[{3*x + 4*y - 11 == 0, 2*x - y == 0}, y]
Out[36]= -1 + x == 0
Note also that it was not really necessary to order the y column first
(provided wherever we put it, we eliminate rows that have nonzero entries
in that column), but when we get away from linear equations some
technicalities force us to use such an ordering in order to perform an
analogous elimination of variables. Let's see specifically what the
Groebner basis for the relevant polynomials looks like, when we explicitly
order the elimination variables first.
In[28]:= GroebnerBasis[{z^2*p1 + z*p2 + p4, y + z^2*q1 + z*q2 + q4}, {p1,
q1, y}] // InputForm
Out[28]//InputForm=
{q4 + y + q2*z + q1*z^2, p4 + p2*z + p1*z^2,
-(p4*q1) + p1*q4 + p1*y - p2*q1*z + p1*q2*z}
Now the ordering among terms in each polynomial is not obvious because
expressions with head of Plus get reordered by the Mathematica evaluator.
We can get the explicit order among terms by cheating and again using the
development version (or we could have figured it out the old fashioned
way, but cheating is more fun):
In[29]:= Map[MonomialList[#, {p1, q1, y}]&, %] // InputForm
Out[29]//InputForm=
{{q1*z^2, y, q4, q2*z}, {p1*z^2, p4, p2*z},
{p1*y, p1*q4, p1*q2*z, -(p4*q1), -(p2*q1*z)}}
The leading term of the first polynomial is thus seen to be q1*z^2; the
leading term of the second is p1*z^2, and the leading term of the third is
p1*y. As every polynomial leading term involves an elimination variable,
once we eliminate these variables there is nothing left (that is, we have
a vacuous system). Note that Mathematica again agrees:
In[37]:= Eliminate[{z^2*p1 + z*p2 + p4==0, y + z^2*q1 + z*q2 + q4==0},
{p1, q1}]
Out[37]= True
But wait. Reduce gave some nontrivial results. What gives? Recall that
Reduce also looks for nongeneric parameter values that give different
results from the generic case. This happens when leading terms of
polynomials in the Groebner basis involve parameters. We then check to see
what happens when such leading terms vanish due to specific choices of
parameter values. In this example the leading terms of the first two
polynomials vanish exactly when z is zero. In that case the system reduces
to the set of polynomials
{y + q4, p4, p1*y + p1*q4 - p4*q1}
But this third polynomial involves the elimination variables, hence does
not appear in the elimination ideal, which, to repeat in different
language, gives only the values of the remaining variables (y, because all
others were parameters) that satisfy the original equations/polynomials.
So we have the result that z==0, y == -q4, and p4==0.
Note that no value of parameters can make the leading term of the third
polynomial in the basis vanish, because that term involves only p1, an
elimination variable, and y, a solve variable. Hence there are no other
possibilities to check. Final result: if z is not zero, then any value for
y satisfies the polynomials in the elimination ideal (because it is
vacuous), while otherwise we must have y == -q4 and p4==0.
Finally I will address the last question in the original post. If z is
not zero, then there are no restrictions on the remaining parameters.
There are restrictions on the elimination p1 and q1. In fact, their values
are determined by polynomial equations once you fix values of all the
others. But as we eliminated these from the equations, there is correctly
no mention of their values in terms of the rest. There is also no
restriction on the value of y. If there were, we would see it in the
output, but remember that you cannot expect to solve two equations for
more than two variables, and we effectively solved for the two elimination
variables already prior to removing all trace of those solutions.
Sorry this got a bit long-winded.
Daniel Lichtblau
Wolfram Research, Inc.
danl at wolfram.com
==== [MESSAGE SEPARATOR] ====