ResultantsDiscriminantsApplicationsPolynomial equationsImplicitization of rational curvesRandom matricesThe set of nonnegative polynomials� � 1 MIT 6.972 Algebraic techniques and semidefinite optimization February 28, 2006 Lecture 6 Lecturer: Pablo A. Parrilo Scribe: ??? Last week we learned about explicit conditions to determine the number of real roots of a univariate polynomial. Today we will e xpand on these themes, and study two mathematical objects of fundamental importance: the resultant of two polynomials, and the closely related discriminant. The resultant will be used to decide whether two univariate polynomials have common roots, while the discriminant will give information about the existence of multiple ro ots . Furthermore, we will see the intimate connections between discriminants and the boundary of the cone of nonnegative polynomials. Besides the properties described above, a direct consequence of their definitions, there are many other interesting applications of resultants and discriminant. We describe a few of them below, and we will encounter them again in later lectures, when studying elimination theory and the construction of cylindrical algebraic decompositions. For much more information about resultants and discriminants, particularly their generalizations to the sparse and multipolynomial case, we refer the reader to the very readable introductory article [Stu98] and the book [CLO97]. Resultants Consider two polynomials p(x) and q(x), of degree n, m, respectively. We want to obtain an easily checkable criterion to determine whether they have a common root, that is, there exists an x0 ∈ C for which p(x0) = q(x0) = 0. There are several approaches, seemingly different at first sight, for constructing such a criterion: • Sylvester matrix: If p(x0) = q(x0) = 0, then we can write the following (n + m) × (n + m) linear system: ⎤⎡⎡⎤pn pn−1 . . . p1 p0 m−1 0p(x0)x⎡ ⎤ n+m−1 0 ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ . . . x m−2 0 ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ p(x0)x . . .. . .pn+m−2 0 ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦ n x . . . qm qm−1 . . . q0 . . . p(x0)x0 p(x0) n−1 q(x0)x0 n−2 q(x0)x0 . . . q(x0)x0 . . . nx0 p1 p0 p2 p1 p0 n−1 0 = 0.=x . . .. .. .. .qm . . . x0 1q1 q0 q(x0)q2 q1 q0 This implies that the matrix on the left-hand side, called the Sylvester matrix Sylx(p, q) associated to p and q, is singular and thus its determinant must vanish. It is not too difficult to show that the converse is also true; if det Sylx(p, q) = 0, then there exists a vector in the kernel of Sylx(p, q) of the form shown in the matrix equation above, and thus a common root x0. • Root products and companion matrices: Let αj , βk be the roots of p(x) and q(x), respectively. By construction, the expression n m(αj − βk) j=1 k=1 vanishes if and only if there exists a root of p that is equal to a root of q. Although the computation of this product seems to require explicit access to the roots , this can be avoided. Multiplying by 6-1� � � � � � � 2 a convenient normalization factor, we have: n m nm n m m pn q (αj − βk ) = p q(αj ) = p det q(Cp)m n n j=1 k=1 j=1 (1)mn n= (−1)nm q p(βk ) = (−1)nm q det p(Cq )m m k=1 • Kronecker products: Using a well-known connection to Kronecker products, we can also write (1) as m n pn q det(Cp ⊗ Im − Im n ⊗ Cq ). B´ezout matrix • ToDoTo be completed If can be shown that all these constructions are equivalent. They define exactly the s ame polynomial, called the resultant of p and q, denoted as Resx(p, q): Resx(p, q) = det Sylx(p, q) = p m det q(Cp)n n= (−1)nm q det p(Cq )m m= pn q n det(Cp ⊗ Im − Im n ⊗ Cq ). The resultant is a homogeneous multivariate polynomial, with integer coefficients, and of degree n + m in the n + m + 2 variables pj , qk . It vanishes if and only if the polynomials p and q have a common root. Notice that the definition is not symmetric in its two arguments, Resx(p, q) = (−1)nmRes(q, p) (of course, this does not matter in checking whether it is zero). Remark 1. To compute the resultant of two polynomials p(x) and q(x) in Maple, you can use the command resultant(p,q,x). In Mathematica, use instead Resultant[p,q,x]. Discriminants As we have seen, the resultant allow us to write an easily checkable condition for the simultaneous vanishing of two univariate polynomials. Can we use the resultant to produce a condition for a polynomial to have a double root? Recall that if a polynomial p(x) as a double root at x0 (which can be real or complex), then its derivative p�(x) also vanishes at x0. Thus, we can check for the existence of a double root by computing the resultant betweeen a polynomial and its derivative. Definition 2. The discriminant of a univariate polynomial p(x) is defined as 1Disx(p) := (−1)n(n−1)/2 Resx p(x), dp(x) . pn dx Similar to what we did in the resultant case, the discriminant can also be obtained by writing a natural condition in terms of the roots αi of p(x): Disx(p) = p 2n−2 (αj − αk )2 .n j<k If p(x) has degree n, its discriminant is a homogeneous polynomial of degree 2n−2 in its n+1 coefficients pn, . . . , p0. 6-2Example 3. Consider the quadratic univariate polynomial p(x) = ax2 + bx + c. Its discriminant is: 1Disx(p) = − Resx(ax 2 + bx + c, 2ax + b) = b2 − 4ac. a For the cubic polynomial p(x) = ax3 + bx2 + cx + d we have 2 3Disx(p) = −27a 2d2 + 18adcb + b2 c − 4b3d − 4ac . 3 Applications 3.1 Polynomial equations One of the most natural applications of resultants is in the solution of polynomial equations in two variables. For this, consider a polynomial system p(x, y) = 0, q(x, y) = 0, (2) with only a finite number of solutions (which is generically the case). Consider a fixed value of y0, and the two univariate polynomials p(x, y0), q(x, y0). If y0 corresponds to the y-component of a root, then these two univariate polynomials clearly have a common root, hence their resultant vanishes. Therefore, to solve (2), we can compute Resx(p, q), which is a univariate polynomial in y. Solving this univariate polynomial, we