Author Русская версия


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.

Resultant in the Kronecker form

Resultant in the Bézout form

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<k\le n_{}.

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.

Answer.

(-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)_{}.

Finding an imaginary zero for a polynomial

Differential resultant

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