MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

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] ====


  • Prev by Date: Re: Q: optimal swap file settings with win3.11
  • Next by Date: Re: Aligning Graphs in GraphicsArray
  • Previous by thread: An "Assume" type command
  • Next by thread: ISSAC'96 ADVANCE PROGRAM AND REGISTRATION