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 eliminant.
Contents
- Notation
- Definition
- Properties
- Characterizing properties
- Zeros
- Invariance by ring homomorphisms
- Invariance under change of variable
- Invariance under change of polynomials
- Generic properties
- Homogeneity
- Elimination properties
- Computation
- Application to polynomial systems
- Case of two equations in two unknowns
- General case
- Number theory
- Algebraic geometry
- Symbolic integration
- Computer algebra
- Homogeneous resultant
- Macaulays resultant
- Resultant of generic homogeneous polynomials
- Properties of the generic Macaulay resultant
- Resultant of polynomials over a field
- Computability
- U resultant
- Extension to more polynomials and computation
- References
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 or multivariate resultant, sometimes called Macaulay's 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 A and B is commonly denoted
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:
The degree of the polynomials are used in the definition of the resultant. However, a polynomial of degree d may also be considered as a polynomial of higher degree such 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
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 respective degrees d and e. Let us denote by
such that
is a linear map between two spaces of the same dimension. Over the basis of the powers of x, this map is represented by a square matrix of dimension d + e, which called the Sylvester matrix of A and B (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 A and B is thus the determinant
which has e columns of ai and d columns of bj (for simplification, d = e in the displayed determinant).
In the case of monic polynomials over an integral domain the resultant is equal to the product
where x and y run over the roots of the polynomials over an algebraically closed field containing the coefficients. For non-monic polynomials with leading coefficients a0 and b0 , respectively, the above product is multiplied by
Properties
In this section and its subsections, A and B are two polynomials in x of respective degrees d and e, and their resultant is denoted
Characterizing properties
The preceding properties characterize the resultant. In other words, the resultant is the unique function of the coefficients of polynomials that has these properties.
Some mathematics software, including Mathematica and Maple, use the alternate convention
Zeros
Invariance by ring homomorphisms
Let A and B be two polynomials of respective degrees d and e with coefficients in a commutative ring R, and
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 R is a polynomial ring in other indeterminates, and S is the ring obtained by specializing to numerical values some or all indeterminates of R, 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 Euclidean algorithm for polynomials, the resultant of two successive remainders differs from the resultant of the initial polynomials by a factor, which is easy to compute. Moreover, the constant a in above second formula may be chosen in order that the successive remainders have their coefficients in the ring of coefficients of input polynomials. This is the starting idea of the subresultant-pseudo-remainder-sequence algorithm for computing the greatest common divisor and the resultant of two polynomials. This algorithms works for polynomials over the integers or, more generally, over an integral domain, without any other division than exact divisions (that is without involving fractions). It involves
Generic properties
In this section, we consider two polynomials
and
whose d + e + 2 coefficients are distinct indeterminates. Let
be the polynomial ring over the integers defined by these indeterminates. The resultant
Homogeneity
The generic resultant for the degrees d and e is homogeneous in various ways. More precisely:
Elimination properties
Let
An example where k > 1 in the latter property is
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
It follows from § Invariance under change of polynomials that the computation of a resultant is strongly related with Euclidean algorithm for polynomials. This shows that the computation of the resultant of two polynomials of degrees d and e may be done in
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 (
Application to polynomial systems
Resultants were introduced for solving systems of polynomial equations and provides the oldest proof that there exist algorithms for solving such systems. There are primarily intended for systems of two equations in two unknown, but allow also solving general systems.
Case of two equations in two unknowns
Let us consider two polynomials the system of equations
where P and Q are polynomials of respective total degrees d and e. Then
Therefore, solving the system amounts computing the roots of R, and for each root
It is worth to remark that Bézout's theorem results of the value of
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
A method, introduced at the end of 19th century, works as follows: introduce k − 1 new indeterminates
This is a polynomial in
For getting 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, were 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.
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 x and y are algebraic numbers such that
Let
Algebraic geometry
Given two plane algebraic curves defined as the zeros of the polynomials P(x, y) and Q(x, y), the resultant allows the computation of their intersection. More precisely, the roots of
A rational plane curve may be defined by a parametric equation
where P, Q and R are polynomials. An implicit equation of the curve is given by
The degree of this curve is the highest degree of P, Q and R, 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 Q is a square-free polynomial and P is a polynomial of lower degree than Q. The antiderivative of such a function involves necessarily logarithms, and generally algebraic numbers (the roots of Q). In fact, the antiderivative is
where the sum runs over all complex roots of Q.
The number of algebraic numbers involved by this expression is generally equal to the degree of Q, 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
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 P(x, y) and Q(x, y) of respective total degrees p and q, their homogeneous resultant is the determinant of the matrix over the monomial basis of the linear map
where A runs over the bivariate homogeneous polynomials of degree q − 1, and B runs over the homogeneous polynomials of degree p − 1. In other words, the homogeneous resultant of P and Q is the resultant of P(x, 1) and Q(x, 1 when they are considered as polynomials of degree p and q (their degree in x 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 n homogeneous polynomials in n indeterminates. Macaulay's resultant is a polynomial in the coefficients of these n 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 n hyper surfaces defined by the polynomials have a common zero in the n –1 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 d in n variables may have up to
coefficients; it is said to be generic, if these coefficients are distinct indeterminates.
Let
indeterminate coefficients. Let C be the polynomial ring over the integers, in all these indeterminate coefficients. The polynomials
The Macaulay degree is the integer
in which each
If n = 2, the Macaulay matrix is the Sylvester matrix, and is a square matrix, but this is no longer true for n > 2. 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 C-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 1, when, for each i, zero is substituted for all coefficients of
Properties of the generic Macaulay resultant
Resultant of polynomials over a field
From now on, we consider that the homogeneous polynomials
The main property of the resultant is that it is zero if only if
The "only if" part of this theorem results on the last property of the preceding paragraph, and is an effective version of Projective Nullstellensatz: If the resultant is nonzerozero, then
where
Computability
As the computation of a resultant may 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 n) depending on a huge number of indeterminates. It follows that, except for very small n 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 n 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
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
U-resultant
Macaulay's resultant provides a method, called "U-resultant" by Macaulay, for solving systems of polynomial equations.
Given n − 1 homogeneous polynomials
is the generic linear form whose coefficients are new indeterminates
The U-resultant is a homogeneous polynomial in
Extension to more polynomials and computation
The U-resultant, as defined by Macaulay was defined only for a number of homogeneous polynomials, which is one less than the number of indeterminates. In 1981, Daniel Lazard provided the following generalization to any number of polynomials, which may be computed by a single Gaussian elimination.
Let
Let
where, for each i,
Reducing the Macaulay matrix by a variant of Gaussian elimination, one gets a square matrix of linear forms in
The number of rows of the Macaulay matrix is less than
Although large, this bound is almost optimal. In fact, if all input degrees are equal, this implies that the time complexity is polynomial in the expected number of solutions (Bézout's theorem).