Consider the multiplication by in defined by It is straightforward to check that the matrix of in the basis is given by
(the column on the far right corresponds to the Euclidean division of by ). Therefore the characteristic polynomial of equals and the roots, with their corresponding multiplicities, of the polynomial can be recovered by computing the eigenvalues of the multiplication map . See e.g. [Lang02].
synaps/upol/resultant.h
The Sylvester matrix of and (in degree ) is the matrix whose columns contain respectively the coefficients of the polynomials expanded in the monomial basis . It is a square matrix of size which has the following form:
More precisely, it is the matrix of the -linear map
in the monomial bases and , where denotes the set of polynomials in of degree lower or equal to .
Proposition: If is a field, then we have the equality . |
Definition: The resultant of the polynomials and , denoted , is the determinant of the Sylvester matrix of and |
The resultant is thus an element in . It has been widely studied in the literature, since it provides a way to eliminate the variable from the polynomial system . Indeed, we have
Proposition: if and only if either , or either and have a common root in the algebraic closure of the fraction field of (or equivalently and are not coprime in ). |
synaps/upol/resultant.h
Definition: The Bezoutian of the polynomials and is the element in defined by
and the Bezout matrix is . |
The matrix is a -matrix which is symmetric:
where (here).
It is thus a smaller matrix than the Sylvester matrix, but has more complicated entries, and its determinant still equals the resultant of and (up to a power of ):
Proposition: [Kra95] We have:
Moreover, if is a field |
synaps/upol/resultant.h
#include <synaps/upol.h> #include <synaps/linalg/MatrDse.h> #include <synaps/upol/resultant.h> typedef UPolDse<double> upol_t typedef MatrDse<double> matr_t; using std::cout; using std::endl; int main (int argc, char **argv) { using std::cout; using std::endl; upol_t p0("3*x0+3;"); double u1[]={2,0,-1,1};upol_t p1(u1,u1+4); cout <<"p0 ="<<p0<<endl<<"p1 ="<<p1<<endl;
matrix_t S = sylvester<matr_t>(p0,p1); cout <<S<<endl;
matrix_t B = bezout<matr_t>(p0,p1); cout <<B<<endl;
B = companion<matr_t>(p1); cout <<B<<endl;
}