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