Resultant

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root (possibly in a field extension), or, equivalently, a common factor (over their field of coefficients). In some older texts, the resultant is also called the eliminant.
The resultant is widely used in number theory, either directly or through the discriminant, which is essentially the resultant of a polynomial and its derivative. The resultant of two polynomials with rational or polynomial coefficients may be computed efficiently on a computer. It is a basic tool of computer algebra, and is a built-in function of most computer algebra systems. It is used, among others, for cylindrical algebraic decomposition, integration of rational functions and drawing of curves defined by a bivariate polynomial equation.
The resultant of "n" homogeneous polynomials in "n" variables (also called multivariate resultant, or Macaulay's resultant for distinguishing it from the usual resultant) is a generalization, introduced by Macaulay, of the usual resultant. It is, with Gröbner bases, one of the main tools of effective elimination theory (elimination theory on computers).
Notation.
The resultant of two univariate polynomials and is commonly denoted formula_1 or formula_2
In many applications of the resultant, the polynomials depend on several indeterminates and may be considered as univariate polynomials in one of their indeterminates, with polynomials in the other indeterminates as coefficients. In this case, the indeterminate that is selected for defining and computing the resultant is indicated as a subscript: formula_3 or formula_4
The degrees of the polynomials are used in the definition of the resultant. However, a polynomial of degree may also be considered as a polynomial of higher degree where the leading coefficients are zero. If such a higher degree is used for the resultant, it is usually indicated as a subscript or a superscript, such as formula_5 or formula_6
Definition.
The resultant of two univariate polynomials over a field or over a commutative ring is commonly defined as the determinant of their Sylvester matrix. More precisely, let 
and
be nonzero polynomials of degrees and respectively. Let us denote by formula_9 the vector space (or free module if the coefficients belong to a commutative ring) of dimension whose elements are the polynomials of degree strictly less than . The map
such that 
is a linear map between two spaces of the same dimension. Over the basis of the powers of (listed in descending order), this map is represented by a square matrix of dimension , which is called the "Sylvester matrix" of and (for many authors and in the article Sylvester matrix, the Sylvester matrix is defined as the transpose of this matrix; this convention is not used here, as it breaks the usual convention for writing the matrix of a linear map).
The resultant of and is thus the determinant
which has columns of and columns of (the fact that the first column of 's and the first column of 's have the same length, that is , is here only for simplifying the display of the determinant).
For instance, taking and we get
If the coefficients of the polynomials belong to an integral domain, then 
where formula_15 and formula_16 are respectively the roots, counted with their multiplicities, of and in any algebraically closed field containing the integral domain.
This is a straightforward consequence of the characterizing properties of the resultant that appear below. In the common case of integer coefficients, the algebraically closed field is generally chosen as the field of complex numbers.
Properties.
In this section and its subsections, and are two polynomials in of respective degrees and , and their resultant is denoted 
formula_17
Characterizing properties.
The resultant of two polynomials and of respective degrees and , with coefficients in 
a commutative ring , has the following properties that characterize the resultant, if is a field or, more generally, an integral domain
In other words, the resultant is the unique function of the coefficients of two polynomials that has these properties.
Invariance by ring homomorphisms.
Let and be two polynomials of respective degrees and with coefficients in a commutative ring , and formula_26 a ring homomorphism of into another commutative ring . Applying formula_27 to the coefficients of a polynomial extends formula_27 to a homomorphism of polynomial rings formula_29, which is also denoted formula_30 With this notation, we have:
These properties are easily deduced from the definition of the resultant as a determinant. They are mainly used in two situations. For computing a resultant of polynomials with integer coefficients, it is generally faster to compute it modulo several primes and to retrieve the desired resultant with Chinese remainder theorem. When is a polynomial ring in other indeterminates, and is the ring obtained by specializing to numerical values some or all indeterminates of , these properties may be restated as "if the degrees are preserved by the specialization, the resultant of the specialization of two polynomials is the specialization of the resultant". This property is fundamental, for example, for cylindrical algebraic decomposition.
Invariance under change of variable.
This means that the property of the resultant being zero is invariant under linear and projective changes of the variable.
Invariance under change of polynomials.
These properties imply that in the Euclidean algorithm for polynomials, and all its variants (pseudo-remainder sequences), the resultant of two successive remainders (or pseudo-remainders) differs from the resultant of the initial polynomials by a factor which is easy to compute. Conversely, this allows one to deduce the resultant of the initial polynomials from the value of the last remainder or pseudo-remainder. This is the starting idea of the subresultant-pseudo-remainder-sequence algorithm, which uses the above formulae for getting subresultant polynomials as pseudo-remainders, and the resultant as the last nonzero pseudo-remainder (provided that the resultant is not zero). This algorithm works for polynomials over the integers or, more generally, over an integral domain, without any division other than exact divisions (that is, without involving fractions). It involves formula_55 arithmetic operations, while the computation of the determinant of the Sylvester matrix with standard algorithms requires formula_56 arithmetic operations.
Generic properties.
In this section, we consider two polynomials
and
whose coefficients are distinct indeterminates. Let
be the polynomial ring over the integers defined by these indeterminates.
The resultant formula_1 is often called the generic resultant for the degrees and . It has the following properties.
Homogeneity.
The generic resultant for the degrees and is homogeneous in various ways. More precisely:
Elimination property.
∗Let formula_73 be the ideal generated by two polynomials and in a polynomial ring formula_74 where formula_75 is itself a polynomial ring over a field. If at least one of and is monic in , then:
The first assertion is a basic property of the resultant. The other assertions are immediate corollaries of the second one, which can be proved as follows.
As at least one of and is monic, a tuple formula_87 is a zero of formula_3 if and only if there exists formula_89 such that formula_90 is a common zero of and . Such a common zero is also a zero of all elements of formula_86 Conversely, if formula_90 is a common zero of the elements of formula_93 it is a zero of the resultant, and there exists formula_89 such that formula_90 is a common zero of and . So formula_64 and formula_78 have exactly the same zeros.
Computation.
Theoretically, the resultant could be computed by using the formula expressing it as a product of roots differences. However, as the roots may generally not be computed exactly, such an algorithm would be inefficient and numerically unstable. As the resultant is a symmetric function of the roots of each polynomial, it could also be computed by using the fundamental theorem of symmetric polynomials, but this would be highly inefficient.
As the resultant is the determinant of the Sylvester matrix (and of the Bézout matrix), it may be computed by using any algorithm for computing determinants. This needs formula_98 arithmetic operations. As algorithms are known with a better complexity (see below), this method is not used in practice.
It follows from that the computation of a resultant is strongly related to the Euclidean algorithm for polynomials. This shows that the computation of the resultant of two polynomials of degrees and may be done in formula_55 arithmetic operations in the field of coefficients.
However, when the coefficients are integers, rational numbers or polynomials, these arithmetic operations imply a number of GCD computations of coefficients which is of the same order and make the algorithm inefficient.
The subresultant pseudo-remainder sequences were introduced to solve this problem and avoid any fraction and any GCD computation of coefficients. A more efficient algorithm is obtained by using the good behavior of the resultant under a ring homomorphism on the coefficients: to compute a resultant of two polynomials with integer coefficients, one computes their resultants modulo sufficiently many prime numbers and then reconstructs the result with the Chinese remainder theorem.
The use of fast multiplication of integers and polynomials allows algorithms for resultants and greatest common divisors that have a better time complexity, which is of the order of the complexity of the multiplication, multiplied by the logarithm of the size of the input (formula_100 where is an upper bound of the number of digits of the input polynomials).
Application to polynomial systems.
Resultants were introduced for solving systems of polynomial equations and provide the oldest proof that there exist algorithms for solving such systems. These are primarily intended for systems of two equations in two unknowns, but also allow solving general systems.
Case of two equations in two unknowns.
Consider the system of two polynomial equations
where and are polynomials of respective total degrees and . Then formula_102 is a polynomial in , which is generically of degree (by properties of ). A value formula_89 of is a root of if and only if either there exist formula_104 in an algebraically closed field containing the coefficients, such that formula_105, or formula_106 and formula_107 (in this case, one says that and have a common root at infinity for formula_108).
Therefore, solutions to the system are obtained by computing the roots of , and for each root formula_109 computing the common root(s) of formula_110 formula_111 and formula_112
Bézout's theorem results from the value of formula_113, the product of the degrees of and . In fact, after a linear change of variables, one may suppose that, for each root of the resultant, there is exactly one value of such that is a common zero of and . This shows that the number of common zeros is at most the degree of the resultant, that is at most the product of the degrees of and . With some technicalities, this proof may be extended to show that, counting multiplicities and zeros at infinity, the number of zeros is exactly the product of the degrees.
General case.
At first glance, it seems that resultants may be applied to a general polynomial system of equations
by computing the resultants of every pair formula_117 with respect to formula_118 for eliminating one unknown, and repeating the process until getting univariate polynomials. Unfortunately, this introduces many spurious solutions, which are difficult to remove.
A method, introduced at the end of the 19th century, works as follows: introduce new indeterminates formula_119 and compute
This is a polynomial in formula_119 whose coefficients are polynomials in formula_122 which have the property that formula_123 is a common zero of these polynomial coefficients, if and only if the univariate polynomials formula_124 have a common zero, possibly at infinity. This process may be iterated until finding univariate polynomials.
To get a correct algorithm two complements have to be added to the method. Firstly, at each step, a linear change of variable may be needed in order that the degrees of the polynomials in the last variable are the same as their total degree. Secondly, if, at any step, the resultant is zero, this means that the polynomials have a common factor and that the solutions split in two components: one where the common factor is zero, and the other which is obtained by factoring out this common factor before continuing.
This algorithm is very complicated and has a huge time complexity. Therefore, its interest is mainly historical.
Other applications.
Number theory.
The discriminant of a polynomial, which is a fundamental tool in number theory is the quotient by its leading coefficient of the resultant of the polynomial and its derivative.
If formula_89 and formula_104 are algebraic numbers such that formula_127, then formula_128 is a root of the resultant formula_129 and formula_130 is a root of formula_131, where formula_132 is the degree of formula_133. Combined with the fact that formula_134 is a root of formula_135, this shows that the set of algebraic numbers is a field.
Let formula_136 be an algebraic field extension generated by an element formula_109 which has formula_138 as minimal polynomial. Every element of formula_139 may be written as formula_140 where formula_141 is a polynomial. Then formula_104 is a root of formula_143 and this resultant is a power of the minimal polynomial of formula_144
Algebraic geometry.
Given two plane algebraic curves defined as the zeros of the polynomials and , the resultant allows the computation of their intersection. More precisely, the roots of formula_145 are the "x"-coordinates of the intersection points and of the common vertical asymptotes, and the roots of formula_146 are the "y"-coordinates of the intersection points and of the common horizontal asymptotes.
A rational plane curve may be defined by a parametric equation
where , and are polynomials. An implicit equation of the curve is given by
The "degree" of this curve is the highest degree of , and , which is equal to the total degree of the resultant.
Symbolic integration.
In symbolic integration, for computing the antiderivative of a rational fraction, one uses partial fraction decomposition for decomposing the integral into a "rational part", which is a sum of rational fractions whose antiprimitives are rational fractions, and a "logarithmic part" which is a sum of rational fractions of the form
where is a square-free polynomial and is a polynomial of lower degree than . The antiderivative of such a function involves necessarily logarithms, and generally algebraic numbers (the roots of ). In fact, the antiderivative is 
where the sum runs over all complex roots of .
The number of algebraic numbers involved by this expression is generally equal to the degree of , but it occurs frequently that an expression with less algebraic numbers may be computed. The Lazard–Rioboo–Trager method produced an expression, where the number of algebraic numbers is minimal, without any computation with algebraic numbers.
Let 
be the square-free factorization of the resultant which appears on the right. Trager proved that the antiderivative is 
where the internal sums run over the roots of the formula_153 (if formula_154 the sum is zero, as being the empty sum), and formula_155 is a polynomial of degree in . The Lazard-Rioboo contribution is the proof that formula_155 is the subresultant of degree of formula_157 and formula_158 It is thus obtained for free if the resultant is computed by the subresultant pseudo-remainder sequence.
Computer algebra.
All preceding applications, and many others, show that the resultant is a fundamental tool in computer algebra. In fact most computer algebra systems include an efficient implementation of the computation of resultants.
Homogeneous resultant.
The resultant is also defined for two homogeneous polynomial in two indeterminates. Given two homogeneous polynomials and of respective total degrees and , their homogeneous resultant is the determinant of the matrix over the monomial basis of the linear map
where runs over the bivariate homogeneous polynomials of degree , and runs over the homogeneous polynomials of degree . In other words, the homogeneous resultant of and is the resultant of 
 and when they are considered as polynomials of degree and (their degree in may be lower than their total degree):
(The capitalization of "Res" is used here for distinguishing the two resultants, although there is no standard rule for the capitalization of the abbreviation).
The homogeneous resultant has essentially the same properties as the usual resultant, with essentially two differences: instead of polynomial roots, one considers zeros in the projective line, and the degree of a polynomial may not change under a ring homomorphism.
That is:
Any property of the usual resultant may similarly extended to the homogeneous resultant, and the resulting property is either very similar or simpler than the corresponding property of the usual resultant.
Macaulay's resultant.
Macaulay's resultant, named after Francis Sowerby Macaulay, also called the multivariate resultant, or the multipolynomial resultant, is a generalization of the homogeneous resultant to homogeneous polynomials in indeterminates. Macaulay's resultant is a polynomial in the coefficients of these homogeneous polynomials that vanishes if and only if the polynomials have a common non-zero solution in an algebraically closed field containing the coefficients, or, equivalently, if the hyper surfaces defined by the polynomials have a common zero in the dimensional projective space. The multivariate resultant is, with Gröbner bases, one of the main tools of effective elimination theory (elimination theory on computers).
Like the homogeneous resultant, Macaulay's may be defined with determinants, and thus behaves well under ring homomorphisms. However, it cannot be defined by a single determinant. It follows that it is easier to define it first on generic polynomials.
Resultant of generic homogeneous polynomials.
A homogeneous polynomial of degree in variables may have up to 
coefficients; it is said to be "generic", if these coefficients are distinct indeterminates.
Let formula_165 be generic homogeneous polynomials in indeterminates, of respective degrees formula_166 Together, they involve
indeterminate coefficients.
Let be the polynomial ring over the integers, in all these 
indeterminate coefficients. The polynomials formula_165 belong thus to formula_169 and their resultant (still to be defined) belongs to .
The Macaulay degree is the integer formula_170 which is fundamental in Macaulay's theory. For defining the resultant, one considers the Macaulay matrix, which is the matrix over the monomial basis of the -linear map
in which each formula_172 runs over the homogeneous polynomials of degree formula_173 and the codomain is the -module of the homogeneous polynomials of degree .
If , the Macaulay matrix is the Sylvester matrix, and is a square matrix, but this is no longer true for . Thus, instead of considering the determinant, one considers all the maximal minors, that is the determinants of the square submatrices that have as many rows as the Macaulay matrix. Macaulay proved that the -ideal generated by these principal minors is a principal ideal, which is generated by the greatest common divisor of these minors. As one is working with polynomials with integer coefficients, this greatest common divisor is defined up its sign. The generic Macaulay resultant is the greatest common divisor which becomes , when, for each , zero is substituted for all coefficients of formula_174 except the coefficient of formula_175 for which one is substituted.
Resultant of polynomials over a field.
From now on, we consider that the homogeneous polynomials formula_182 of degrees formula_183 have their coefficients in a field , that is that they belong to formula_184 Their resultant is defined as the element of obtained by replacing in the generic resultant the indeterminate coefficients by the actual coefficients of the formula_185
The main property of the resultant is that it is zero if and only if formula_182 have a nonzero common zero in an algebraically closed extension of .
The "only if" part of this theorem results from the last property of the preceding paragraph, and is an effective version of Projective Nullstellensatz: If the resultant is nonzero, then
where formula_188 is the Macaulay degree, and formula_189 is the maximal homogeneous ideal. This implies that formula_182 have no other common zero than the unique common zero, , of formula_191
Computability.
As the computation of a resultant may be reduced to computing determinants and polynomial greatest common divisors, there are algorithms for computing resultants in a finite number of steps.
However, the generic resultant is a polynomial of very high degree (exponential in ) depending on a huge number of indeterminates. It follows that, except for very small and very small degrees of input polynomials, the generic resultant is, in practice, impossible to compute, even with modern computers. Moreover, the number of monomials of the generic resultant is so high, that, if it would be computable, the result could not be stored on available memory devices, even for rather small values of and of the degrees of the input polynomials.
Therefore, computing the resultant makes sense only for polynomials whose coefficients belong to a field or are polynomials in few indeterminates over a field.
In the case of input polynomials with coefficients in a field, the exact value of the resultant is rarely important, only its equality (or not) to zero matters. As the resultant is zero if and only if the rank of the Macaulay matrix is lower than its number of its rows, this equality to zero may by tested by applying Gaussian elimination to the Macaulay matrix. This provides a computational complexity formula_192 where is the maximum degree of input polynomials.
Another case where the computation of the resultant may provide useful information is when the coefficients of the input polynomials are polynomials in a small number of indeterminates, often called parameters. In this case, the resultant, if not zero, defines a hypersurface in the parameter space. A point belongs to this hyper surface, if and only if there are values of formula_193 which, together with the coordinates of the point are a zero of the input polynomials. In other words, the resultant is the result of the "elimination" of formula_193 from the input polynomials.
"U"-resultant.
Macaulay's resultant provides a method, called ""U"-resultant" by Macaulay, for solving systems of polynomial equations.
Given homogeneous polynomials formula_195 of degrees formula_196 in indeterminates formula_197 over a field , their "U"-resultant is the resultant of the polynomials formula_198 where
is the generic linear form whose coefficients are new indeterminates formula_200 Notation formula_201 or formula_202 for these generic coefficients is traditional, and is the origin of the term "U"-resultant.
The "U"-resultant is a homogeneous polynomial in formula_203 It is zero if and only if the common zeros of formula_204 form a projective algebraic set of positive dimension (that is, there are infinitely many projective zeros over an algebraically closed extension of ). If the "U"-resultant is not zero, its degree is the Bézout bound formula_205
The "U"-resultant factorizes over an algebraically closed extension of into a product of linear forms. If formula_206 is such a linear factor, then formula_207 are the homogeneous coordinates of a common zero of formula_208 Moreover, every common zero may be obtained from one of these linear factors, and the multiplicity as a factor is equal to the intersection multiplicity of the formula_209 at this zero. In other words, the "U"-resultant provides a completely explicit version of Bézout's theorem.
Extension to more polynomials and computation.
The "U"-resultant as defined by Macaulay requires the number of homogeneous polynomials in the system of equations to be formula_210, where formula_132 is the number of indeterminates. In 1981, Daniel Lazard extended the notion to the case where the number of polynomials may differ from formula_210, and the resulting computation can be performed via a specialized Gaussian elimination procedure followed by symbolic determinant computation.
Let formula_213 be homogeneous polynomials in formula_197 of degrees formula_215 over a field . Without loss of generality, one may suppose that formula_216 Setting formula_217 for , the Macaulay bound is formula_218
Let formula_219 be new indeterninates and define formula_220 In this case, the Macaulay matrix is defined to be the matrix, over the basis of the monomials in formula_197 of the linear map
where, for each , formula_172 runs over the linear space consisting of zero and the homogeneous polynomials of degree formula_224.
Reducing the Macaulay matrix by a variant of Gaussian elimination, one obtains a square matrix of linear forms in formula_200 The determinant of this matrix is the "U"-resultant. As with the original "U"-resultant, it is zero if and only if formula_213 have infinitely many common projective zeros (that is if the projective algebraic set defined by formula_213 has infinitely many points over an algebraic closure of ). Again as with the original "U"-resultant, when this "U"-resultant is not zero, it factorizes into linear factors over any algebraically closed extension of . The coefficients of these linear factors are the homogeneous coordinates of the common zeros of formula_228 and the multiplicity of a common zero equals the multiplicity of the corresponding linear factor.
The number of rows of the Macaulay matrix is less than formula_229 where is the usual mathematical constant, and is the arithmetic mean of the degrees of the formula_185 It follows that all solutions of a system of polynomial equations with a finite number of projective zeros can be determined in time formula_231 Although this bound is large, it is nearly optimal in the following sense: if all input degrees are equal, then the time complexity of the procedure is polynomial in the expected number of solutions (Bézout's theorem). This computation may be practically viable when , and are not large.