SYNAPS (SYmbolic Numeric ApplicationS) » Univariate Polynomial

Sylvester and Bezout matrices

The compagnon matrix

compagnon Let $\mathbbm{K}$ be any field and suppose given a polynomial $f (x) : = f_d x^d + f_{d - 1} x^{d - 1} + \cdots + f_1 x + f_0$ in $\mathbbm{K}[x]$. Using the standard Euclidean polynomial division it is easy to see that the quotient algebra $\mathcal{A} = \mathbb{K} [x] / I$, where $I$ denotes the principal ideal of $\mathbbm{K}[x]$ generated by the polynomial $f (x)$, is a vector space over $\mathbbm{K}$ of dimension $d$ with canonical basis $\{1, x, \ldots, x^{d - 1} \}.$

Consider the multiplication by $x$ in $\mathcal{A,}$ $M_x : \mathcal{A} \to \mathcal{A}$ defined by $a \mapsto a \hspace{0.25em} x.$ It is straightforward to check that the matrix of $M_x$ in the basis $\{1, x, \ldots, x^{d - 1} \}$ is given by

\[ M_x = \left[ \begin{array}{cccc} 0 & \cdots & 0 & - f_0 / f_d\\ 1 & \ddots & & \vdots\\ \vdots & & 0 & \vdots\\ 0 & & 1 & - f_{d - 1} / f_d \end{array} \right] \]

(the column on the far right corresponds to the Euclidean division of $x^d$ by $f$). Therefore the characteristic polynomial of $M_x$ equals $\frac{(- 1)^d}{f_d} f (x)$ and the roots, with their corresponding multiplicities, of the polynomial $f$ can be recovered by computing the eigenvalues of the multiplication map $M_x$. See e.g. [Lang02].

See also:
synaps/upol/resultant.h

The sylvester matrix

Let $A$ be a commutative ring, which is assumed to be a domain, and suppose given two polynomials in $A [x]$ of respective degree $d_0$ and $d_1$

\[ \begin{array}{l} f_0 (x) : = c_{0, 0} + c_{0, 1} x + \cdots + c_{0, d_0} x^{d_0},\\ f_1 (x) : = c_{1, 0} + c_{1, 1} x + \cdots + c_{1, d_1} x^{d_1} . \end{array} \]

The Sylvester matrix of $f_0$ and $f_1$ (in degree $(d_0, d_1)$) is the matrix whose columns contain respectively the coefficients of the polynomials $f_0, xf_0, \ldots, x^{d_1 - 1} f_0 .$ $f_1, xf_1, \ldots, \hspace{0.25em} x^{d_0 - 1} f_1$ expanded in the monomial basis $\{1, x, \ldots, x^{d_0 + d_1 - 1} \}$. It is a square matrix of size $d_0 + d_1$ which has the following form:

\[ S = \begin{array}{ll} \left( \begin{array}{ccc|ccc} c_{0, 0} & & 0 & c_{1, 0} & & 0\\ \vdots & \ddots & & \vdots & \ddots & \\ & & c_{0, 0} & & & c_{1, 0}\\ c_{0, d_0} & & \vdots & c_{1, d_1} & & \vdots\\ & \ddots & \vdots & & \ddots & \vdots\\ 0 & & c_{0, d_0} & 0 & & c_{1, d_1} \end{array} \right) & \begin{array}{l} 1\\ x\\ \vdots\\ \vdots\\ \vdots\\ x^{d_0 + d_1 - 1} \end{array} \end{array} \]

More precisely, it is the matrix of the $A$-linear map

\begin{equation} \anchor UResultantphi \begin{array}{rrl} \sigma : A [x]_{< d_1} \oplus A [x]_{< d_0} & \rightarrow & A [x]_{< d_0 + d_1}\\ (q_0, q_1) & \mapsto & f_0 q_0 + f_1 q_1 \end{array} \end{equation}

in the monomial bases $\{1, \ldots, x^{d_1 - 1} \}, \{1, \ldots, x^{d_0 - 1} \}$ and $\{1, \ldots, x^{d_0 + d_1 - 1} \}$, where $A [x]_{< k}$ denotes the set of polynomials in $A [x]$ of degree lower or equal to $k - 1$.

Proposition: If $A$ is a field, then we have the equality $\dim \ker (S) = \deg (\gcd (f_0, f_1))$.

Definition: The resultant of the polynomials $f_0$ and $f_1$, denoted $Res (f_0, f_1)$, is the determinant of the Sylvester matrix of $f_0$ and $f_1$

The resultant $\tmop{Res} (f_0, f_1)$ is thus an element in $A$. It has been widely studied in the literature, since it provides a way to eliminate the variable $x$ from the polynomial system $f_0 (x) = f_1 (x) = 0$. Indeed, we have

Proposition: $\tmop{Res} (f_0, f_1) = 0$ if and only if either $c_{0, d_0} = c_{1, d_1} = 0$, or either $f_0 (x)$ and $f_1 (x)$ have a common root in the algebraic closure of the fraction field $F$ of $A$ (or equivalently $f_0$ and $f_1$ are not coprime in $F [x]$).

See also:
synaps/upol/resultant.h

The Bezout matrix

Another matrix, called the Bezoutian matrix, can be used to compute $\tmop{Res} (f_0, f_1)$. We now suppose w.l.o.g. that $d_1 \geq d_0$.

Definition: The Bezoutian of the polynomials $f_0$ and $f_1$ is the element in $A [x, y]$ defined by

\[ \Theta_{f_0, f_1} (x, y) : = \frac{f_0 (x) f_1 (y) - f_1 (x) f_0 (y)}{x - y} = \sum_{i, j = 0}^{d_1 - 1} \theta_{i, j} x^i y^j \]

and the Bezout matrix is $B_{f_0, f_1} : = \left( \theta_{i, j} \right)_{0 \leq i, j \leq d_1 - 1}$.

The matrix $B_{f_0, f_1}$ is a $d \times d_{}$-matrix which is symmetric:

\[ B_{f_0, f_1} = \left[ \begin{array}{ccc} \theta^{f_0, f_1}_{0, 0} & \cdots & \theta^{f_0, f_1}_{0, d - 1}\\ \vdots & & \vdots\\ \theta^{f_0, f_1}_{d_{} - 1, 0} & \cdots & \theta^{f_0, f_1}_{d - 1, d - 1} \end{array} \right] \]

where $d = \max (d_1, d_0)$ ($= d_1$here).

It is thus a smaller matrix than the Sylvester matrix, but has more complicated entries, and its determinant still equals the resultant of $f_0$ and $f_1$ (up to a power of $c_{1, d_1}$):

Proposition: [Kra95] We have:

\begin{eqnarray*} \det (B_{f_0, f_1}) & = & (- 1)^{\frac{1}{2} d_1 (d_1 - 1)} \hspace{0.25em} (c_{1, d_1})^{d_1 - d_0} \tmop{Res} (f_0, f_1) . \end{eqnarray*}

Moreover, if $A$ is a field $\mathrm{\dim} \hspace{0.25em} \ker (B_{f_0, f_1}) = \deg (\gcd (f_0, f_1)) .$

See also:
synaps/upol/resultant.h

Example

#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;

\[ p 0 = 3 x + 3, p 1 = x^3 - x^2 + 2 \] 

  matrix_t S = sylvester<matr_t>(p0,p1); cout <<S<<endl;

\[ \left[ \begin{array}{cccc} 3 & 0 & 0 & 2\\ 3 & 3 & 0 & 0\\ 0 & 3 & 3 & - 1\\ 0 & 0 & 3 & 1 \end{array} \right] \] 

  matrix_t B = bezout<matr_t>(p0,p1);    cout <<B<<endl;

\[ \left[ \begin{array}{ccc} - 6 & - 3 & 3\\ - 3 & 0 & 3\\ 3 & 3 & 0 \end{array} \right] \] 

  B = companion<matr_t>(p1);         cout <<B<<endl;

\[ \left[ \begin{array}{ccc} 0 & 0 & - 2\\ 1 & 0 & 0\\ 0 & 1 & 1 \end{array} \right] \] 

}

SYNAPS DOCUMENTATION
logo