From: minardi@ee.gatech.edu Subject: Re: roots of a polynomial fn fron R^N to R^N To: rusin@math.niu.edu (Dave Rusin) Date: Mon, 12 Dec 1994 10:15:46 -0500 (EST) According to Dave Rusin: > > In article <3bv96t$qrm@acmex.gatech.edu> you write: > >I have a system of third order polynomials which are all coupled together > >and represent a function from R^N to R^N, I am interested in the "roots" > >of these equations, i.e. the elements of R^N which map to the all zero vector. > > > >Can these roots be solved for explicitly (as they can be in the one > >dimensional case). Failing that, can anything concrete be said about the > >roots, e.g. how many are there, etc. Is there a textbook which discusses > >this subject? > In general, the solution to a set of polynomial equations in several variables > is the province of algebraic geometry. If you know the solution set is finite, > you can usually find the solutions by solving one polynomial of larger > degree. For example, given two quadratcis in x and y, the solution set > is usually found by eliminating y (say) and getting a quartic polynomial > satsified by x. The keyword here is "resolvents". > I got a 1976 book on algabraic geometry by Kendig from the library I'll check it for references to the word "resolvants" I'll also search the library database. I interpret what you are saying by "if you have two quadratics, each one a function of two independent variables, I can combine them into one 4th degree polynomial of one independant variable." Is this correct? > > > >The function looks like this (using MATLAB like notation): > > > >f(X) = G*((G'*X).^3 +3((ones(N,N)-eye(N))*(G'*X).^2).*(g'*X) - (G'*X)) > I assume you meant G (not g) here...................^ YES > > Let Y= G'*X so f(X) is actually a function of Y: > f(X) = G* h(Y), where (if K_{i,j} = 1 except K_{i,i}=0 ): > h(Y) = Y.^3 + 3( K* Y.^2).*Y - Y. > The i_th row of this is just y_i^3 + 3(Sum[ y_j^2 : j<> i] ).y_i - y_i, > if I understand your notation. Letting Z = Sum[ y_j^2, all j], this is > just -2y_i^3 + (3Z-1)y_i. So here's what you do. If you want to have > f(X)=0, you just need to find Y so that h(Y) lies in the kernel of > G (the set of vectors V such that G*V=0). It's standard linear > algebra to find such V's. Then for any such V, look for the Y's with > (for every i) V_i = -2y_i^3 + (3Z-1)y_i, where Z = Sum[ y_i^2]. Unfortunately the kernal is a sub-space and has an uncountably infinite number of points (except when G is invertible in which case the kernal has only one point, 0). This is bad because my equations are nonlinear so we have to examine each element of the kernal(G). We can't just look at a finite set which spans the kernal and use linearity to extend the results to every point in the space. > Now, for any given Z and V_i, there are in general 3 solutions to > this equation. I can help you with this a bit if you'd like, but it's going to > be messy. An interesting special case occurs if all the V_i are equal, > for example if all V_i=0. (This possibility occrs for all G, and for G > non-singular this is the only possibility). > > Then all the v_i are roots of the same cubic, > and so one solution is to take all y_i to be equal; indeed, if the cubic > has only one (real) root, then the y_i _must_ be equal. Then Z = N y_1^2, > and the y's satisfy the equation > V_1= -2y^3 + (3Ny^2 - 1) y = (3N-2) y^3 - y. > > In the special case V_i=0 for all i, we can find all possible solutions: > for every i, -2y_i^3+(3Z-1)y_i=0, so either y_i=0 or y_i=sqrt((3Z-1)/2). > If precisely K of the y_i's are non-zero, then Z=Sum[y_i^2]=K.(3Z-1)/2, > so that Z= K/(3K-2), and each of the non-zero y_i must equal > sqrt(1/(3K-2)). [The special case K=N is covered in the previous paragraph] > > Anyway, the original equation f(X)=0 became G*h(G'*X)=0, i.e, h(G'*X) is > one of the vectors V, which we just solved (more or less): G'*X has > to be one of the vectors with coordinates y_i as above. For any > such vector Y, you then solve the matrix equation Y = G'*X with traditional > linear algebra. The evening after my first post I had factored the case where G is invertible and got the same results as you did, except for the fact that its satisfied when abs(y_i)'s are equal so its y_i=0 or y_i=+/-sqrt((3Z-1)/2). So I was excited that you got the same results. The case where G is invertible represents a whole class of applications so I think that this result alone will be very helpful to me. I found out that for dimension N there are 3^N separate roots (X=all zeroes is also a root). > Maybe it would be clearer if you could describe the kinds of G's which > you will face -- will they be filled with specific constants, or are you > trying to describe qualitatively a general case? What sizes are the G's? > > dave The roots of these equations are the stable points of a nonlinear adaptive algorithm. For radar and radio communications applications G would typically be nonsingular or perhaps overdetermined (i.e. more rows than columns or "tall"). Also G will be complex valued. (i am only considering real valued G's so far). For applications involving communication channel equalization G will be underdetermined with less rows than columns, i.e. "flat". In this case G may be real or complex valued, however I am more interested in the real valued case. A typical size for G in my simulations is 7 rows and 13 columns. G does not have a totally random structure in this case. if [h_1,...,h_n] is the impulse response of the channel and the equalizer has m taps then G has m rows and n+m-1 columns. For n=3, m=3 we would get [ h_1 h_2 h_3 0 0 ] G = | 0 h_1 h_2 h_3 0 | [ 0 0 h_1 h_2 h_3 ] so you can see that there is a lot of structure in G, maybe that will save me! Once again thank you very much for your insights. -- Michael J. Minardi, Georgia Tech School of EE Atlanta, GA 30332-0250 E-MAIL: minardi@eecom.gatech.edu PHONE: (404) 894-1295 ============================================================================== Date: Mon, 12 Dec 94 12:19:27 CST From: rusin (Dave Rusin) To: minardi@ee.gatech.edu, rusin@math.niu.edu Subject: Re: roots of a polynomial fn fron R^N to R^N Thanks for the details, perhaps I'll have time to think about the non- invertible G later. It is interesting that you have a specific structure for G in the last case, because a very similar matrix shows up when computing the resolvents I mentioned earlier! If f(X) and g(X) are two polynomials in X, the resolvent is a certain polynomial made from the coefficients of f and g with the property that this polynomial is zero iff f and g have a common root (possibly complex or multiple). This applies even if the coefficients of f and g happen to be polynomials in other variables, so you see that for example the condition that f(X,Y) and g(X,Y) both be zero (for some X) can be stated as a polynomial condition on Y. In the case where you have k equations in k unknowns, you typically compute resolvents between the first and each of the remaining equations to get k-1 equations in k-1 unknowns; iterate k times until you get one polynomial equation in one unknown. [This may introduce extraneous solutions, but will find all correct ones.] One definition of the resolvent uses the coefficients directly. If f(X)=b0 X^n + b1 X^{n-1} + ... +bn and g(X)=c0 X^m + c1 X^{m-1} + ... +cm then the resultant of f and g is the determinant of the following (m+n) by (m+n) matrix: [b0 b1 b2 ... bn 0 0 ... 0] [0 b0 b1 ... bn-1 bn 0 ... 0] [0 0 b0 ... bn-2 bn-1 bn ... 0] ... [total: m copies of the first row, shifting to the right. Then,] [c0 c1 c2 ... cn cn+1 ... cm 0 ... 0] [0 c0 c1 ... cn-1 cn ... cm-1 cm .. 0] ... [total: n copies of this row, shifting to the right]. For example, for the curves x^2+3xy-y^2=1 and x^2+5x+6y=7 to meet at (x,y) requires that (1)x^2+(3y)x+(-y^2-1)=0 and (1)x^2+(5)x+(6y-7)=0 have a common root. This requires [1 3y -y^2-1 0 ] [0 1 3y -y^2-1 ] [1 5 6y-7 0 ] = 0 [0 1 5 6y-7 ] i.e., y^4+81y^3-154y^2+48y+11 = 0. The resolvent matrix is the matrix that I find to be similar in form to the matrix G you mentioned. I will have to consider whether the resemblence is superficial or significant. dave ============================================================================== From: minardi@ee.gatech.edu Subject: Re: roots of a polynomial fn fron R^N to R^N To: rusin@math.niu.edu (Dave Rusin) Date: Mon, 12 Dec 1994 14:29:03 -0500 (EST) Again I'll have to digest your post on resolvents, but I do have one quick remark/question. This resolvent theory boils my system of N polynomial equations in N variables down to one equation of one variable (albeit of much higher order). Since I know how many roots a single polynomial of one variable has don't I now have an upper bound on the number of possible solutions? -- Michael J. Minardi, Georgia Tech School of EE Atlanta, GA 30332-0250 E-MAIL: minardi@eecom.gatech.edu PHONE: (404) 894-1295 ============================================================================== Date: Mon, 12 Dec 94 13:37:02 CST From: rusin (Dave Rusin) To: minardi@ee.gatech.edu, rusin@math.niu.edu Subject: Re: roots of a polynomial fn fron R^N to R^N Yes, this is the content of Bezout's theorem: there are many variants with sophisticated formulas but I think if you have a set of k equations in k unknowns, then the number of solutions is either infinite (if the set of equations is indeterminate) or bounded by the product of the degrees of the polynomials. dave ============================================================================== From: Michael Joseph Minardi Subject: Re: roots of a polynomial fn fron R^N to R^N To: rusin@math.niu.edu (Dave Rusin) Date: Tue, 13 Dec 1994 09:13:10 -0500 (EST) According to Dave Rusin: > > Yes, this is the content of Bezout's theorem: there are many variants with > sophisticated formulas but I think if you have a set of k equations in > k unknowns, then the number of solutions is either infinite (if the > set of equations is indeterminate) or bounded by the product of the > degrees of the polynomials. > > dave > I'm looking at Bezout`s theorem right now (Elementary Algabraic Geometry by Kendig). And it only applies to two polynomials of two variables defined on P^2(C) (the 2-dimensional complex plane including the points at infinity). If I read you right you are saying that every time you iterate a set of resolvants you can invoke Bezouts theorem because you only consider two polynomials at a time. And when you are finished you have a bound for the total number of intersections (I'm guessing that it is only a bound because we are working with only the reals and we don't include the points at infinity?). Could you fill in the last step of your resolvant example. Specifically how do I take the single polynomial in Y and use it to get the roots in [X,Y] ? -- Michael J. Minardi, Georgia Tech School of EE Atlanta, GA 30332-0250 E-MAIL: minardi@eecom.gatech.edu PHONE: (404) 894-1295 ============================================================================== Date: Tue, 13 Dec 94 11:51:09 CST From: rusin (Dave Rusin) To: minardi@ee.gatech.edu, rusin@math.niu.edu Subject: Re: roots of a polynomial fn fron R^N to R^N I wrote: > > Yes, this is the content of Bezout's theorem: there are many variants with > sophisticated formulas but I think if you have a set of k equations in > k unknowns, then the number of solutions is either infinite (if the > set of equations is indeterminate) or bounded by the product of the > degrees of the polynomials. > > dave > You responded: >I'm looking at Bezout`s theorem right now (Elementary Algabraic Geometry by >Kendig). And it only applies to two polynomials of two variables defined on >P^2(C) (the 2-dimensional complex plane including the points at infinity). If I >read you right you are saying that every time you iterate a set of resolvants >you can invoke Bezouts theorem because you only consider two polynomials at a >time. And when you are finished you have a bound for the total number of >intersections (I'm guessing that it is only a bound because we are working with >only the reals and we don't include the points at infinity?). First off let me concede that algebraic geometry is _not_ my area of expertise and let me tell you why: the subject was developing great theorems about 90-100 years ago, except that the proofs were pretty bogus and kept referring to undefined "generic points"; by the middle of this century a solid foundation had been provided and complete proofs given, but the amount of machinery needed to understand them is so immense most of us have been scared off. Thus I'll content myself with the circa-1900 explanations. Bezout's theorem is only a bound, not an actual count, in part because of the limitations you've mentioned. It is also true that even when counting intersections in P^2(C) there can be a deficiency ; more accurate versions of Bezout's theorem include it. It accounts for singularities at the intersection points. While it's true that Bezout's theorem only works with pairs of complex curves, the generalization runs as follows: if, say, f(X,Y,Z) and g(X,Y,Z) are polynomials, then for each (complex) value z of Z, f(X,Y,z) and g(X,Y,z) are polynomials of two variables, which have at most a certain number of points of intersection. In fact, if you're willing to slip into complex analysis, each of the solutions depends analytically on z (locally, at most points). Then if you seek common zeros with a third polynomial h(X,Y,Z), you've got to find those values of z which are zeros of the analytic function h(X(z), Y(z), z)=0 Anyway, this theme is often used in higher-dimensional geometry: treat only 1 or 2 variables at a time, thinking of the other variables as holding still. >Could you fill in the last step of your resolvant example. Specifically how do >I take the single polynomial in Y and use it to get the roots in [X,Y] ? I assume you refer to this example I included: >For example, for the curves x^2+3xy-y^2=1 and x^2+5x+6y=7 to meet >at (x,y) requires that (1)x^2+(3y)x+(-y^2-1)=0 and (1)x^2+(5)x+(6y-7)=0 >have a common root. This requires >[1 3y -y^2-1 0 ] >[0 1 3y -y^2-1 ] >[1 5 6y-7 0 ] = 0 >[0 1 5 6y-7 ] >i.e., y^4+81y^3-154y^2+48y+11 = 0. (Had I known you'd press me for details I'd have made up more useful numbers...)