The page is under reconstruction; repair works: 18.12.2015 — ??.??.????

§

To understand the stuff of the present page, it would be desirable to remind some prerequisites in polynomial theory and determinant formalism.

# Resultant

Denote by $\mathbb A_{}$ any of the sets $\mathbb Z, \mathbb Q, \mathbb R_{}$ or $\mathbb C_{}$.

## Resultant in the Sylvester form

For the polynomials $f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n$ and $g(x)=b_{0}x^m+b_1x^{m-1}+\dots+b_m$ при $a_{0}\ne 0, b_0\ne 0$ consider the square matrix of the order $m+n_{}$

$M=\left(\begin{array}{cccccccccc} a_0&a_1&a_2&\ldots&\ldots&a_n&0&\dots &0 &0\\ 0&a_0&a_1&\ldots&\ldots&a_{n-1}&a_n&\dots&0 &0\\ \vdots&&\ddots&&&&&&\ddots\\ 0&0&\ldots&a_0&\ldots&\ldots & & \ldots &a_{n-1} &a_n\\ 0&0&\ldots&&b_0&b_1&\ldots& \ldots &b_{m-1}&b_m\\ 0&0&\ldots&b_0&b_1&\ldots &&\ldots &b_m&0\\ \vdots&&&\ldots&&&& &&\vdots\\ 0&b_0&\ldots&\ldots&&b_m&\ldots&&\ldots&0\\ b_0&\ldots&\ldots&&b_m&0&\ldots&&&0 \end{array}\right) \begin{array}{l} \left.\begin{array}{l} \\ \\ \\ \\ \end{array}\right\} m \\ \left. \begin{array}{l} \\ \\ \\ \\ \\ \end{array}\right\} n \end{array}$

(the entries above $a_{n}$ and $b_{0}$, and below $a_{0}$ and $b_{m}$ equal to zero). The expression

${\mathcal R}(f,g)= (-1)^{n_{}(n-1)/2} \det M$

is called the resultant1) (in the Sylvester form) of the polynomials $f_{}$ and $g_{}$ .

§

In the majority of textbooks, the definition of the resultant is presented in a slightly different manner: the rows of the coefficients of the polynomial $g_{}(x)$ are reordered in such a way that form the staircase ri sing up from the lower rigt corner. Thus, for instance,

${\mathcal R}(a_0x^3+a_1x^{2}+a_2x+a_3,\ b_0x^3+b_1x^{2}+b_2x+b_3)=$
$= \left|\begin{array}{cccccc} a_0&a_1&a_2&a_3 & &\\ & a_0&a_1&a_2&a_3 & \\ & & a_0&a_1&a_2&a_3 \\ b_0&b_1&b_2&b_3 & &\\ & b_0&b_1&b_2&b_3 & \\ & & b_0&b_1&b_2&b_3 \end{array}\right| \ .$

Such a modification gives one an economy in the sign $(-1)^{n_{}(n-1)/2}$ involved into the definition. Nevertheless, due to some reasons soon to be explained BELOW, it is more convenient for me to utilize the above presented form of the matrix $M_{}$.

Ex

Example.

${\mathcal R}(a_0x^2+a_1x+a_2,\ b_0x^2+b_1x+b_2) =(a_0b_2-a_2b_0)^2-(a_0b_1-a_1b_0)(a_1b_2-a_2b_1)$

Th

Theorem. Denote the zeros of polynomial $f_{}(x)$ by $\lambda_{1},\dots,\lambda_n$ , and the zeros of polynomial $g_{}(x)$ by2) $\mu_{1},\dots,\mu_m$. One has

${\mathcal R}(f,g)= a_0^m b_0^n \prod_{k=1}^m \prod_{j=1}^n (\lambda_j - \mu_k) \ .$

=>

${\mathcal R}(f,g)= a_0^m \prod_{j=1}^n g(\lambda_j)= (-1)^{mn} b_0^n \prod_{k=1}^m f(\mu_k) \ .$

=>

${\mathcal R}(f,g)=0_{}$ if and only if the polynomials $f_{}(x)$ and $g_{}(x)$ possess a common zero.

Ex

Example. Find all the values for the parameter ${\color{RubineRed} \alpha }$ for which the polynomials $x^{3}+{\color{RubineRed} \alpha }\,x+1$ and $x^{2}+{\color{RubineRed} \alpha }\,x+1$ possess a common zero.

Solution. Compute the determinant with the aid of elementary transformation of its rows

${\mathcal R}(x^3+{\color{RubineRed} \alpha }\,x+1,\ x^2+{\color{RubineRed} \alpha }\,x+1)= (-1)^{3\cdot 2/2}\left| \begin{array}{ccccc} 1 & 0 & {\color{RubineRed} \alpha } & 1 & 0 \\ 0 & 1 & 0 & {\color{RubineRed} \alpha } & 1 \\ 0 & 0 & 1 & {\color{RubineRed} \alpha } & 1 \\ 0 & 1 & {\color{RubineRed} \alpha } & 1 & 0 \\ 1 & {\color{RubineRed} \alpha } & 1 & 0 & 0 \end{array} \right| =- \left| \begin{array}{ccccc} 1 & 0 & {\color{RubineRed} \alpha } & 1 & 0 \\ 0 & 1 & 0 & {\color{RubineRed} \alpha } & 1 \\ 0 & 0 & 1 & {\color{RubineRed} \alpha } & 1 \\ 0 & 0 & {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 \\ 0 & {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 & 0 \end{array} \right|=$

(the first row is subtracted from the last one, while the second row from the last-but-one), expand the resulting determinant by the last column:

$=-\left| \begin{array}{cccc} 1 & 0 & {\color{RubineRed} \alpha } & 1 \\ 0 & 1 & {\color{RubineRed} \alpha } & 1 \\ 0 & {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 \\ {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 & 0 \end{array} \right|=- \left| \begin{array}{cccc} 1 & 0 & {\color{RubineRed} \alpha } & 1 \\ 0 & 1 & {\color{RubineRed} \alpha } & 1 \\ 0 & {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 \\ 0 & 1-{\color{RubineRed} \alpha } & -1-{\color{RubineRed} \alpha }^2 & -{\color{RubineRed} \alpha } \end{array} \right|=$

(the first row multiplied by ${\color{RubineRed} \alpha }$ is subtracted from the last one), expand the determinant by the first column:

$=-\left| \begin{array}{ccc} 1 & {\color{RubineRed} \alpha } & 1 \\ {\color{RubineRed} \alpha } & 1-{\color{RubineRed} \alpha } & -1 \\ 1-{\color{RubineRed} \alpha } & -1-{\color{RubineRed} \alpha }^2 & -{\color{RubineRed} \alpha } \end{array} \right|= -\left| \begin{array}{ccc} 1 & {\color{RubineRed} \alpha } & 1 \\ {\color{RubineRed} \alpha }+1 & 1 & 0 \\ 1 & -1 & 0 \end{array} \right|=$

(the first row is added to the second one, the first row multiplied by ${\color{RubineRed} \alpha }$ is added to the third one), expand the determinant by the last column:

$=-\left| \begin{array}{cc} {\color{RubineRed} \alpha }+1 & 1 \\ 1 & -1 \end{array} \right|=-(-({\color{RubineRed} \alpha }+1)-1)={\color{RubineRed} \alpha }+2 \ .$

Answer. ${\color{RubineRed} \alpha }+=-2_{}$.

Check. $x^{3}-2\,x+1\equiv (x-1)(x^2+x-1),\ x^2-2\,x+1\equiv (x-1)(x+1)$.

?

Find all the values for the parameter ${\color{RubineRed} \alpha }+_{}$ for which the polynomials

$x^{3}+{\color{RubineRed} \alpha }+\,x^2-14 \quad and \quad x^{3}+{\color{RubineRed} \alpha }+\,x-14$

possess a multiple zero.

§

For the particular case $g_{}(x)\equiv f^{\prime}(x)$, the resultant is transformed into discriminant.

!

The main application of the resultant elimination of variables in a system of polynomial equations .

## Properties

1. If $\deg f(x) = n_{}$ and $\deg g(x)=m_{}$, then

${\mathcal R}(f,g)=(-1)^{nm}{\mathcal R}(g,f) \ .$

2.

${\mathcal R}\left(f_1\cdot f_2,\, g\right)={\mathcal R}(f_1,\,g)\cdot {\mathcal R}(f_2,\, g)$

3.

${\mathcal R}(Af(x)+Bg(x),Cf(x)+Dg(x))=(AD-BC)^n{\mathcal R}\left(f(x),g(x)\right)$

The last equality is valid under an additional assumption that

$\deg f= n\ge m =\deg g \ge 1 \quad and \quad \deg (Af(x)+Bg(x))=\deg (Cf(x)+Dg(x))= n \ .$

4. If $f(x)=a_{0}x^n + a_1x^{n-1} + \dots + a_n$ and $g(x)=b_{0}x^m+b_1x^{m-1}+\dots+b_m$, and $a_{0}\ne0,a_n\ne 0,b_0\ne 0,b_m\ne 0$ then

${\mathcal R}(f,g) = (-1)^{mn}{\mathcal R}(a_0+a_1x+\dots+a_nx^n,\ b_0+b_1x+\dots+b_mx^m) \ .$

## Resultant as a polynomial function of the coefficients

By definition, resultant is a polynomial over $\mathbb Z$ with respect to the coefficients of polynomials $f_{}(x)$ and $g_{}(x)$:

${\mathcal R}(a_0 x^n+ \ldots + a_{n}, b_0x^m + \ldots + b_m)\equiv R(a_0,\dots,a_n,b_0,\dots,b_m) \in {\mathbb Z}[a_0,\dots,a_n,b_0,\dots,b_m] \ .$

Its degree equals $mn_{}$. Treated with respect to $a_0,\dots,a_{n}$, the resultant is a homogeneous polynomial of the degree $m_{}$; treated with respect to $b_{0},\dots,b_m$ the resultant is a homogeneous polynomial of the degree $n_{}$.

Th

Theorem. If polynomials $f_{}(x)$ and $g_{}(x)$ possess a unique common root $\lambda_{}$ then

$\lambda^j : \lambda^k = \frac{\partial R}{\partial a_{n-j-\ell}} : \frac{\partial R}{\partial a_{n-k-\ell}} = \frac{\partial R}{\partial b_{m-j-q}} : \frac{\partial R}{\partial b_{m-k-q}}$

for any $\{j,k,\ell,q_{} \}\subset \{0,1,2,\dots \}$.

Proof. Consider the case $j=0, k=1$. Differentiate the equality for the resultant

${\mathcal R}(f,g)= a_0^m \prod_{j=1}^n g(\lambda_j)$

with respect to $b_{q}$. One gets:

$\frac{\partial R}{\partial b_{q}}= \sum_{j=1}^n \frac{\partial g(\lambda_j)}{\partial b_{q}} \cdot \prod_{j=1 \atop j\ne q}^n g(\lambda_j) = \sum_{j=1}^n \alpha_j^{m-q} \prod_{j=1 \atop j\ne q}^n g(\lambda_j) \ .$

If polynomials $f_{}(x)$ and $g_{}(x)$ possess a unique common root $\lambda_1$ then the last equality is transformed into

$\frac{\partial R}{\partial b_{q}}=\lambda_1^{m-q} \prod_{j=2}^n g(\lambda_j)$

and the product $\prod$ does not vanish. Since the equality is valid for any specializations of $q_{}$, one has

$\frac{\partial R}{\partial b_{q-1}} \Bigg/ \frac{\partial R}{\partial b_{q}}= \lambda_1 \ ,$

and the other equality from the theorem is proved similarly.

## Subresultants and the greatest common divisor

Consider the matrix $M_{}$ from the definition of the resultant and delete its first and last columns as well as the first and the last rows. We get a square matrix of the order $m_{}+n-2$. Its determinant

${\mathcal R}^{(1)}(f,g)= \left|\begin{array}{cccccccc} a_0&a_1&\ldots&\ldots&a_{n-1}&a_n&\dots&0 \\ \vdots&\ddots&&&&&\ddots\\ 0&\ldots&a_0&\ldots&\ldots & & \ldots &a_{n-1} \\ 0&\ldots&&b_0&b_1&\ldots& \ldots &b_{m-1}\\ 0&\ldots&b_0&b_1&\ldots &&\ldots &b_m\\ \vdots&&\ldots&&&& &\vdots\\ b_0&\ldots&\ldots&&b_m&\ldots&&0 \end{array}\right| \begin{array}{l} \left.\begin{array}{l} \\ \\ \\ \end{array}\right\} m-1 \\ \left. \begin{array}{l} \\ \\ \\ \\ \end{array}\right\} n-1 \end{array}$

is called the first subresultant of the resultant ${\mathcal R}(f_{},g)$.

Th

Theorem. For the polynomials $f_{}(x)$ and $g_{}(x)$ to possess a unique common zero it is necessary and sufficient that the following conditions be satisfied:

${\mathcal R}(f,g)=0,\ {\mathcal R}^{(1)}(f,g)\ne 0\ .$

=>

Under the conditions of the previous theorem, the single common zero of $f_{}(x)$ and $g_{}(x)$ can be expressed as a rational function of the coefficients of these polynomials:

$\lambda=-{\det M_1^{(1)}\over {\mathcal R}^{(1)}(f,g)} .$

Here the $M_1^{(1)}$ denotes the matrix obtained from $M_{}$ by deleting its first and last rows as well as its first and its last but one column.

Ex

Example. Under the conditions of the theorem, the single common zero of the polynomials

$f(x)=a_0x^5+a_1x^4+a_2x^3+a_3x^2+a_4x+a_5 \quad$ and $\quad g(x)=b_0x^3+b_1x^2+b_2x+b_3$

($a_{0} \ne 0, b_0 \ne 0$) can be expressed by the formula:

$\lambda =- \left| \begin{array}{cccccc} a_0&a_1&a_2&a_3&a_4&0\\ 0&a_0&a_1&a_2&a_3&a_5\\ 0&0&0&b_0&b_1&b_3\\ 0&0&b_0&b_1&b_2&0\\ 0&b_0&b_1&b_2&b_3&0\\ b_0&b_1&b_2&b_3&0&0 \end{array}\right| \Bigg/ \left|\begin{array}{cccccc} a_0&a_1&a_2&a_3&a_4&a_5\\ 0&a_0&a_1&a_2&a_3&a_4\\ 0&0&0&b_0&b_1&b_2\\ 0&0&b_0&b_1&b_2&b_3\\ 0&b_0&b_1&b_2&b_3&0\\ b_0&b_1&b_2&b_3&0&0 \end{array} \right| \ .$

The determinant of the matrix $M_{k}$ obtained from the matrix $M_{}$ by deleting its first $k_{}$ columns and its $k_{}$ last columns, its first $k_{}$ rows and its $k_{}$ last rows, is called the ${\mathbf k}$th subresultant of the resultant of the polynomials $f_{}$ and $g_{}$; we will denote it as ${\mathcal R}^{(k)}(f,g)$. For simplicity, we term by the zero subresultant the determinant of the matrix $M_{}$:

${\mathcal R}^{(0)}(f,g)= \det M =(-1)^{n(n-1)/2}{\mathcal R}(f,g) .$

Ex

Example. For the polynomials $f(x)=a_{0}x^5+a_1x^4+a_2x^3+a_3x^2+a_4x+a_5$ and $g(x)=b_{0}x^3+ b_1x^2+b_2x+b_3$ one has:

${\mathcal R}^{(2)}(f,\ g)= \left|\begin{array}{cccc} a_0&a_1&a_2&a_3\\ 0&0&b_0&b_1\\ 0&b_0&b_1&b_2\\ b_0&b_1&b_2&b_3 \end{array} \right| ;\ {\mathcal R}^{(3)}(f,\ g) =\left|\begin{array}{cc} 0&b_0\\ b_0&b_1 \end{array}\right| = -b_0^2 .$

Th

Theorem. Polynomials $f_{}(x)$ and $g_{}(x)$ possess the greatest common divisor of the degree $k>0$, it is necessary and sufficient the fulfillment of the following conditions

${\mathcal R}(f,g)=0,\ {\mathcal R}^{(1)}(f,g)= 0,\ \dots , {\mathcal R}^{(k-1)}(f,g)= 0, {\mathcal R}^{(k)}(f,g)\ne 0.$

=>

Under the conditions of the previous theorem, the greatest common divisor for the polynomials $f_{}(x)$ and $g_{}(x)$ can be represented in the form

$\operatorname{GCD} (f(x),g(x)) \equiv x^k{\mathcal R}^{(k)}(f,g) +x^{k-1} \det M_k^{(1)} +\ldots +\det M_k^{(k)} .$

Here $M_k^{(j)}$ stands for the matrix obtained from the subresultant ${\mathcal R}^{(k)}(f,g)$ by the replacement of its last column with

$[a_{m+n-2k+j-1}, a_{m+n-2k+j-2},\dots, a_{n-k+j},b_{m-k+j},b_{m-k+j+1},\dots,b_{m+n-2k+j-1}]^{\top}$

(we set here $a_{K}=0$ for $K>n_{}$ and $b_{L}=0$ for $L>m_{}$).

Ex

Example. Find the greatest common divisor for the polynomials

$f(x)= x^6-x^5+3\,x^{3}-2\,x^2+1 \quad and \quad g(x)=x^{5}+x^3+x^2+2\,x+1 \ .$

Solution. Omitting the intermediate computations, we present the final result:

${\mathcal R}(f,g)=0,\ {\mathcal R}^{(1)}(f,g)= 0,\ {\mathcal R}^{(2)}(f,g)= 0, \ {\mathcal R}^{(3)}(f,g)= \left| \begin{array}{rrrrr} 1 & -1 & 0 & 3 & -2 \\ 0 & 1 & -1 & 0 & 3 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 2 \end{array} \right| =-7 \ne 0$

Therefore, $\operatorname{GCD} (f(x),g(x))$ is of the degree $3_{}$. For its computation, compose the determinant by replacing the last column of the subresultant ${\mathcal R}^{(3)}$:

$\operatorname{GCD} (f(x),g(x)) =\left| \begin{array}{rrrrr} 1 & -1 & 0 & 3 & -2\,x^3+x \\ 0 & 1 & -1 & 0 & 3\,x^3-2\,x^2+1 \\ 0 & 0 & 1 & 0 & x^3+x^2+2\,x+1 \\ 0 & 1 & 0 & 1 & x^3+2\,x^2+x \\ 1 & 0 & 1 & 1 & 2\,x^3+x^2 \end{array} \right|=-7\,x^3 +7\,x^2-7\,x-7 \ .$

Answer. $x^3-x^{2}+x+1$.

§

For the particular case $g(x)\equiv f^{\prime}(x)$, the subresultants transform into subdiscriminants.

## Some other representations for the resultant

Th

Theorem. Let $g(x)=b_{0}x^m+\dots+b_m \in {\mathbb C}[x]$ be an arbitrary polynomial. Compute the polynomial from the square matrix $A_{}$:

$g(A)=b_{0}A^m+\dots+b_m I \ .$

Then

$\det g(A) = (-1)^{mn} {\mathcal R}(f,g_{}) ,$

where ${\mathcal R}(f,g_{})$ is the resultant of the polynomials $f(x) =\det (A-x_{} I)$ and $g_{}(x)$.

# Applications

## Tschirnhaus transformation

Problem. For the polynomials from ${\mathbb A}_{}[x]$:

$f(x)=a_0x^n+a_1x^{n-1}+\ldots+a_n,\ g(x)=b_0x^m+b_1x^{m-1}+\ldots+b_m$

($a_{0}\ne0,b_0\ne0$); denote $\lambda_{1},\dots,\lambda_n$ (a priori not known) roots of $f_{}(x)$. Construct the polynomial $F_{}(y)$ with the roots $g(\lambda_{1}),\dots,g(\lambda_n)$. Process of computation of such a polynomial is known as the Tschirnhaus transformation $y=g_{}(x)$ of the polynomial $f_{}(x)$.

Th

Theorem. There exists a unique normalized polynomial $F_{}(y)$ of the degree $n_{}$ solving the stated problem, namely

$F(y)\equiv {\mathcal R}_{x}(f(x),y-g(x))/a_0^m \ ;$

here the resultant is computed for polynomials treated in the variable $x_{}$. Coefficients of $F_{}(y)$ depend rationally on those of $f_{}(x)$ and $g_{}(x)$.

Ex

Example. Find the Tschirnhaus transformation $y=x^{2}+x-1$ for polynomial $f(x)=x^{3}-2\,x+3$.

Solution.

$F(y)={\mathcal R}(x^3-2\,x+3,\ -x^2-x+(1+y))=$
$=-\left| \begin{array}{rrccc} 1 & 0 & -2 & 3 & 0 \\ 0 & 1 & 0 & -2 & 3 \\ 0 & 0 & -1 & -1 & 1+y \\ 0 & -1 & -1 & 1+y & 0 \\ -1 & -1 & 1+y & 0 & 0 \end{array}\right| =y^3-y^2+6y-4 \ .$

Generalizations of the problem are as follows

Problem. For the polynomial $f_{}(x), \deg f=n$ possessing the roots $\lambda_{1},\dots,\lambda_n$, construct the polynomial $F_{}(y)$ with the roots
(a) $\lambda_{j} + \lambda_k$;
(b) $\lambda_{j} \lambda_k$;
(c ) $(\lambda_{j} - \lambda_k)^2$;

here $1\le j.

## Polynomial stability

The polynomial $f_{}(x)$ with complex coefficients is called stable, if all its zeros satisfy the condition $\mathfrak R\mathbf e (x_{})<0$.

The notion of stability is a crucial one in the Optimal Control Theory. The next result gives one of the most popular criterion for stability.

Th

Theorem [ Liénard, Chipart] [3]. The polynomial $f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n$ with real coefficients and $a_{0} > 0$ is stable if and only if the following conditions are satisfied:

(a) all the coefficients $a_{1},\dots, a_n$ are positive;

(b) all the subresultants of the resultant

${\mathcal R}\left(a_n+a_{n-2}Y+a_{n-4}Y^2+\dots,\ a_{n-1}+a_{n-3}Y+a_{n-5}Y^2+\dots \right)$

are positive.

Ex

Example. Condition (b) for $n_{}=7$:

${\mathcal R}=\left| \begin{array}{cccccc} a_1 & a_3 & a_5 & a_7 & & \\ & a_1 & a_3 & a_5 &a_7 & \\ &&a_1 & a_3 & a_5 & a_7 \\ &&a_0 & a_2 & a_4 & a_6 \\ &a_0 & a_2 & a_4 & a_6 & \\ a_0 & a_2 & a_4 & a_6 & & \end{array} \right|>0,\ {\mathcal R}^{(1)}=\left| \begin{array}{cccc} a_1 & a_3 & a_5 & a_7 \\ & a_1 & a_3 & a_5 \\ &a_0 & a_2 & a_4 \\ a_0 & a_2 & a_4 & a_6 \end{array} \right|>0,\ {\mathcal R}^{(2)}=\left| \begin{array}{cc} a_1 & a_3 \\ a_0 & a_2 \end{array} \right|>0;$

and for $n=8$:

${\mathcal R}^{(0)}=\left| \begin{array}{ccccccc} a_0 & a_2 & a_4 & a_6 &a_8 & &\\ &a_0 & a_2 & a_4 & a_6 &a_8 & \\ &&a_0 & a_2 & a_4 & a_6 &a_8 \\ && & a_1 & a_3 & a_5 &a_7 \\ &&a_1 & a_3 & a_5 & a_7 &\\ &a_1 & a_3 & a_5 & a_7 &&\\ a_1 & a_3 & a_5 & a_7 &&& \end{array} \right|>0,\ {\mathcal R}^{(1)}=\left| \begin{array}{ccccc} a_0 & a_2 & a_4 & a_6 &a_8 \\ &a_0 & a_2 & a_4 & a_6 \\ & & a_1 & a_3 & a_5 \\ &a_1 & a_3 & a_5 & a_7 \\ a_1 & a_3 & a_5 & a_7 & \end{array} \right|>0,\ {\mathcal R}^{(2)}=\left| \begin{array}{ccc} a_0 & a_2 & a_4 \\ & a_1 & a_3 \\ a_1 & a_3 & a_5 \end{array} \right|>0,$

and ${\mathcal R}^{(3)}=a_{1}>0$. The last inequality follows from (a).

## Elimination of variables in a system of algebraic equations

Problem. Let $f_{}(x,y)$ and $g_{}(x,y)$ be polynomials in $x_{}$ and $y_{}$ with complex coefficients. Solve the system of equations

$f(x,y)=0,\ g(x,y)=0 \ ,$

i.e. find all the pairs $x_{}= \alpha, y_{}= \beta$ with $\{ \alpha, \beta\} \subset \mathbb C$, such that their substitution in every equation yield the true equalities.

§

For the case of linear polynomials $f_{}$ and $g_{}$ the solution to the problem leads to the idea of Gaussian elimination.

§

If the coefficients of the considered polynomials are real then the geometric interpretation of the stated problem is as follows. Every equation $f_{}(x,y)=0$ or $g_{}(x,y)=0$ defines in the $(x_{},y)$-plane some algebraic curve. Then the problem of finding the real solutions for the system is that of detecting the intersection points for these curves. A particular case of the intersection might be tangency of the curves.

Expand the polynomials $f(x_{},y)$ and $g_{}(x,y)$ in decreasing powers of the variables and represent the result as sums of homogeneous polynomials (forms):

$\begin{array}{l} f(x,y)=f_n(x,y)+f_{n-1}(x,y)+\ldots+f_0(x,y) \ ,\\ g(x,y)=g_m(x,y)+g_{m-1}(x,y)+\ldots+g_0(x,y) \ . \end{array}$

Set the following assumption concerning the leading coefficients of the forms of the highest orders:

$\begin{array}{l} f_n(x,y)=a_{n0}x^n+a_{n-1,1}x^{n-1}y+\dots+a_{0n}y^n ,\\ g_m(x,y)=b_{m0}x^m+b_{m-1,1}x^{m-1}y+\dots+b_{0m}y^m . \end{array}$

Assumption. Let $a_{n0}\ne 0,a_{0n}\ne 0,b_{m0}\ne 0,b_{0m}\ne 0 \ .$

The pair $x_{}= \alpha, y= \beta$ with $\{ \alpha, \beta\} \subset \mathbb C_{}$ is a solution to the sustem if and only if the polynomials $f(\alpha,y)$ and $g(\alpha,y)$ possess a common zero $y_{}=\beta$, and, therefore, due to the main feature of the resultant:

${\mathcal R}(f(\alpha,y),g(\alpha,y))=0 \ .$

Expand $f(\alpha,y)$ and $g(\alpha,y)$ in decreasing powers of $y_{}$

$\begin{array}{l} f(\alpha,y)=A_0y^n+A_1(\alpha)y^{n-1}+\dots+A_n(\alpha) ,\\ g(\alpha,y)=B_0y^m+B_1(\alpha)y^{m-1}+\dots+B_m(\alpha) \end{array}$

(here $A_0=a_{0n}\ne0,B_0=b_{0m}\ne 0$ due to Assumpion ; and $\deg A_j(\alpha)\le j$, $\deg B_j(\alpha)\le j$) and compute the Sylvester determinant:

$\begin{array}{r} m\left\{\begin{array}{c} \\ \\ \\ \\ \end{array}\right. \\ n\left\{\begin{array}{c} \\ \\ \\ \\ \\ \end{array}\right. \end{array} \left|\begin{array}{cccccccc} A_0&A_1(\alpha)&\dots&&A_n(\alpha)&&\mathbb O &\\ &A_0&\dots&&&A_n(\alpha)& & \\ &&\ddots&&&\dots&\ddots\\ &&&&A_0&A_1(\alpha)&\dots&A_n(\alpha)\\ &\mathbb O &&&&B_0&\dots&B_m(\alpha)\\ &&&&B_0&B_1(\alpha)&\dots&\\ &&&&&\dots&&\\ &B_0&B_1(\alpha)&\dots&&B_m(\alpha)&\\ B_0&B_1(\alpha)&\dots&&B_m(\alpha)&&\mathbb O \end{array}\right| ={\mathcal X}(\alpha) \ .$

The expression ${\mathcal X}(\alpha)$ is a polynomial in $\alpha_{}$ and, by construction, it has the coefficients from the same set as those of $f_{}$ and $g_{}$. For the pair $x_{}= \alpha, y= \beta$ to be a solution for the system, it is necessary that $\alpha_{}$ be the zero of ${\mathcal X}(x)=0$.

Polynomial ${\mathcal X}(x)$, i.e. the resultant of $f_{}(x,y)$ and $g_{}(x,y)$ treated as polynomials in $y_{}$

${\mathcal X}(x)= {\mathcal R}_y \left(f(x,y),g(x,y) \right) \ ,$

is known as the eliminant3) of the system of equations with respect to the variable $x_{}$. In a similar manner, the second eliminant for the system is defined:

${\mathcal Y}(y) = {\mathcal R}_x(f(x,y),g(x,y)) \ .$

With the aid of eliminant, one can reduce the solution of the system in two variables to the solution a univariate equation : ${\mathcal X}(x)=0$ (or ${\mathcal Y}(y)=0$). It is said that the other variable is eliminated. The corresponding branch of classical algebra is known as Elimination Theory.

§

For simplicity, I did not care in the above example (and will not care in the foregoing ones) about the sign $(-1)^{n(n-1)/2}$ in the expressions of the both eliminants.

Ex

Example. Solve the system of equations

$\left\{\begin{array}{l} f(x,y)=4\,x^2-7\,xy+y^2+13\,x-2\,y-3=0 \ ,\\ g(x,y)=9\,x^2-14\,xy+y^2+28\,x-4\,y-5=0 \ . \end{array}\right.$

Solution. Expand polynomials of the system into powers of $y_{}$:

$\begin{array}{l} f(x,y)=y^2+(-7\,x-2)y+(4\,x^2+13\,x-3) \ ,\\ g(x,y)=y^2+(-14\,x-4)y+(9\,x^2+28\,x-5) \ , \end{array}$

and compute the eliminant:

${\mathcal X}(x)=\left|\begin{array}{cccc} 1&-7x-2&4x^2+13x-3&0\\ 0&1&-7x-2&4x^2+13x-3\\ 0&1&-14x-4&9x^2+28x-5\\ 1&-14x-4&9x^2+28x-5&0 \end{array}\right| =24(x^4-x^3-4\,x^2+4\,x) \ .$

Find its zeros: $\alpha_1=0,\alpha_2=1,\alpha_3=2,\alpha_4=-2$.

Thus, the $x_{}$-components (coordinates) of solutions are found. How to find the $y_{}$-components? One might construct the other eliminant ${\mathcal Y}(y)$, find then its zeros, compose all the possible pairs of the zeros ${\mathcal X}(x)$ and ${\mathcal Y}(y)$, substitute them into $f_{}(x,y)$ and $g_{}(x,y)$ in order to establish whether we get zeros or not. Or, alternatively, substitute the found value $x_{}=\alpha$ into any of the initial equations: $f(\alpha,y)=0$, solve the obtained with respect to $y_{}$, and substitute the resulting pairs into $g(x,y)$. At least one of them has to satisfy the relation $g(x,y)=0$. In the present example, any of the suggested approaches leads one to the correct

Answer. $(0,-1_{}); (1,2) ; (2,3) ; (-2,1)$.

However, it is well known that generically zeros of a polynomial cannot be expressed — not even in the integers — but also in «good» functions of polynomial coefficients (say, for instance, in radicals). Therefore, one might expect that the zeros of the eliminant can be evaluated only approximately. Then the outlined in the previous example algorithm for selecting an appropriate pair for the variable values becomes inadequate: the eqaulity $f(\alpha,\beta)=0$ should be treated as an approximate one and the roundoff error might cause the wrong conclusion.

Ex

Example. Solve the system of equations

$\left\{\begin{array}{l} f(x,y)=3\,x^2+3\,xy+3\,y^2-3\,x-12\,y+10=0 \ ,\\ g(x,y)=x^3+y^3-x^2+xy-5\,y^2-5\,x+7\,y-3=0 \ . \end{array}\right.$

Solution. The eliminant

${\mathcal X}(x)=\left|\begin{array}{ccccc} 3 & 3\,x-12 & 3\,x^2-3\,x+10 & 0 & 0 \\ 0 & 3 & 3\,x-12 & 3\,x^2-3\,x+10 & 0 \\ 0 & 0 & 3 & 3\,x-12 & 3\,x^2-3\,x+10 \\ 0 & 1 &-5 & x+7 & x^3-x^2-5\,x-3 \\ 1 &-5 & x+7 & x^3-x^2-5\,x-3 & 0 \end{array}\right| =$
$=-(108\,x^6-54\,x^5-459\,x^4+126\,x^3+558\,x^2+72\,x+1)$

has zeros

$-1.4357404546,\ -1.2204153656,\ -0.1184043714,\ -0.0158215507,\ 1.6451908712 \pm 0.3378906924 {\mathbf i},$

some of which are close enough. Note that for any zero $x= \alpha_{}$ of the eliminant ${\mathcal X}(x)$, the polynomials $f(\alpha, y)$ and $g(\alpha, y)$ treated as polynomials in $y_{}$ must have a common zero. This common zero, in case of its uniqueness, can be expressed as a rational function in the coefficients of these polynomials with the aid of subresultants. Formula

$y=-\left| \begin{array}{ccc} 3 & 3\,x-12 & 0 \\ 0 & 3 & 3\,x^2 -3\,x + 10 \\ 1 & -5 & x^3-x^2-5\,x-3 \end{array} \right| \Bigg/ \left| \begin{array}{ccc} 3 & 3\,x-12 & 3\,x^2 -3\,x + 10 \\ 0 & 3 & 3\,x-12 \\ 1 & -5 & x + 7 \end{array} \right|=$
$=-(18\,x^3-9\,x^2-24\,x+3)/(-9\,x-3)$

for any zero of the eliminant $\mathcal X(x)$ yields the value for $y_{}$ such that the obtained pair happens to be a solution to the given system of equations.

$(-1.4357404546, 3.4637885415) ,\ (-1.2204153656, 1.7326988317),\ (-0.1184043714, 2.9392910117),$
$(-0.0158215507, 1.1818959593) ,$
$(1.6451908712 \pm 0.3378906924 \, {\mathbf i},\ 0.8411628278 \pm 1.5734509554 \, {\mathbf i} ) \ .$

Resume. Generically, the system of polynomial equations can be reduced to an equivalent one (i.e. possessing the same set of solutions) in the form:

${\mathcal X}(x)=0,\ p_0(x)y+p_1(x)=0 \ .$

Here $\{ {\mathcal X}, p_0, p_1 \}$ are polynomials in $x_{}$.

### Bézout theorem

How many solutions has the system of equations $f(x,y)=0,\ g(x_{},y)=0$ ? — It is evident that this number coincide with the degree of the eliminant:

Th

Theorem [Bézout]. Under the assumption from the previous section, one has, generically,

$\deg{\mathcal X}(x)=\deg f(x,y)\cdot\deg g(x,y)=nm \ .$

Proof (taken from [5]) will be illuminated by the case $n=3_{}$ and $m=2_{}$.

$\begin{array}{l} f(x,y)=A_0y^3+A_1(x)y^2+A_2(x)y+A_3(x) ,\\ g(x,y)=B_0y^2+B_1(x)y+B_2(x) , \end{array}$
${\mathcal X}(x)=\left|\begin{array}{ccccc} A_0&A_1(x)&A_2(x)&A_3(x)&\\ &A_0&A_1(x)&A_2(x)&A_3(x)\\ &&B_0&B_1(x)&B_2(x)\\ &B_0&B_1(x)&B_2(x)&\\ B_0&B_1(x)&B_2(x)&& \end{array}\right|\ .$

Here

$A_0=a_{03},B_0=b_{02};\deg A_j(x) \le j;\ \deg B_j(x) \le j \quad$ for $\quad j \in \{1,2,3\} \ .$

The leading term of ${\mathcal X}(x_{})$ is formed from the leading terms of the determinant entries. Extract them:

$\begin{array}{ll} A_0=a_{03};&B_0=b_{02}\ ;\\ A_1(x)=a_{12}x+\ldots;&B_1(x)=b_{11}x+\ldots\ ;\\ A_2(x)=a_{21}x^2+\ldots;&B_2(x)=b_{20}x^2+\ldots\ ;\\ A_3(x)=a_{30}x^3+\ldots& \end{array} \ .$

Hence,

${\mathcal X}(x)=\left|\begin{array}{ccccc} a_{03}&a_{12}x&a_{21}x^2&a_{30}x^3&\\ &a_{03}&a_{12}x&a_{21}x^2&a_{30}x^3\\ &&b_{02}&b_{11}x&b_{20}x^2\\ &b_{02}&b_{11}x&b_{20}x^2&\\ b_{02}&b_{11}x&b_{20}x^2&& \end{array}\right|+\ldots\ ,$

and we need to extract the power of $x_{}$ from the first determinant. Let us carry out this with the aid of procedure which can be easily extended to the case of arbitray polynomials $f(x,y)$ and $g(x,y)$. Multiply the second and the fourth rows by $x_{}$, while the third one by $x^{2}$:

$=\frac{1}{x^4}\left|\begin{array}{ccccc} a_{03}&a_{12}x&a_{21}x^2&a_{30}x^3&\\ &a_{03}x&a_{12}x^2&a_{21}x^3&a_{30}x^4\\ &&b_{02}x^2&b_{11}x^3&b_{20}x^4\\ &b_{02}x&b_{11}x^2&b_{20}x^3&\\ b_{02}&b_{11}x&b_{20}x^2&& \end{array}\right|+\ldots =$

Extract from the second column the common divisor $x_{}$ of its entries, from the third column — $x^2$, from the fourth — $x^3$, from the fifth — $x^4$:

$=\frac{x^{1+2+3+4}}{x^4}\left|\begin{array}{ccccc} a_{03}&a_{12}&a_{21}&a_{30}&\\ &a_{03}&a_{12}&a_{21}&a_{30}\\ &&b_{02}&b_{11}&b_{20}\\ &b_{02}&b_{11}&b_{20}&\\ b_{02}&b_{11}&b_{20}&& \end{array}\right|+\ldots=$
!

and pay attention that the obtained determinant has the form of the resultant in the Sylvester form for some univariate polynomials:

$=x^6{\mathcal R}(a_{03}y^3+a_{12}y^2+a_{21}y+a_{30},b_{02}y^2+b_{11}y+b_{20})+ \ldots$

As for arbitrary $m_{}$ and $n_{}$, one gets

${\mathcal X}(x)={\mathcal A}_0x^{nm}+{\mathcal A}_1x^{nm-1}+\dots+{\mathcal A}_{nm}$

and similarly

${\mathcal Y}(y)={\mathcal B}_0y^{nm}+{\mathcal B}_1y^{nm-1}+\ldots+{\mathcal B}_{nm}$

for

${\mathcal A}_0= {\mathcal R}(f_n(1,y),g_m(1,y)) \quad$ and $\quad {\mathcal B}_0= {\mathcal R}(f_n(x,1),g_m(x,1)) \ .$

?

Prove that the leading coefficients of ${\mathcal X}(x)$ and ${\mathcal Y}(y)$ coincide up to a sign.

Hint. V. the property 4 HERE.

§

Thus, we have just clarified the sence of the word «generically» from the theorem statement: it has the meaning that the number ${\mathcal A}_{0}$ differs from zero. it is necessary to emphasize that this number depends only on the coefficients of the leading forms in the expansions of $f(x,y)_{}$ and $g(x,y)_{}$.

# References

[1]. Bôcher M. Introduction to Higher Algebra. NY. Macmillan, 1907

[2]. Jury E.I. Inners and Stability of Dynamic Systems. J.Wiley & Sons, New York, NY, 1974.

[3]. Kronecker L. Zur Theorie der Elimination einer Variabeln aus zwei algebraischen Gleichungen. Werke. Bd. 2. 1897. 113-192, Teubner, Leipzig

[4]. Gantmacher F.R. The Theory of Matrices. Chelsea, New York, 1959

[5]. Brill A. Vorlesungen über ebene algebraischen Kurven und algebraische Funktionen. Braunschweig. Vieweg. 1925

[6]. Kalinina E.A., Uteshev A.Yu. Elimination Theory (in Russian) SPb, Nii khimii, 2002

[7]. Утешев А.Ю., Калинина Е.А. Лекции по высшей алгебре. Часть II. Учеб. пособие. СПб. «СОЛО». 2007.

[8]. Kalinina E.A., Uteshev A.Yu. Determination of the Number of Roots of a Polynominal Lying in a Given Algebraic Domain. Linear Algebra Appl. 1993. V.185, P.61-81.

1) Resultant (Lat.) — reflective; the notion was introduced by Laplace in 1776.
2) For the both cases, in accordance with their multiplicities.
3) The notion was common for the old textbooks in algebra; but nearly never used in the modern publications.

2018/06/19 09:55 редактировал au