☞ **((users:au:index_e Author))** ☞ **((:dets:resultant Русская версия))** !!⊗!! 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== ~~TOC~~ 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 resultant**[[Resultant (//Lat.//) --- reflective; the notion was introduced by Laplace in 1776.]] (**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 ☟ ((#subresultants_and_the_greatest_common_divisor 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) $ //by[[For the both cases, in accordance with their multiplicities.]] //$ \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{Red} \alpha } $ for which the polynomials $$ x^{3}+{\color{Red} \alpha }\,x+1 \ \mbox{ and } \ x^{2}+{\color{Red} \alpha }\,x+1 $$ possess a common zero. **Solution.** Compute the determinant with the aid of elementary row operations $$ {\mathcal R}(x^3+{\color{Red} \alpha }\,x+1,\ x^2+{\color{Red} \alpha }\,x+1)= (-1)^{3\cdot 2/2}\left| \begin{array}{ccccc} 1 & 0 & {\color{Red} \alpha } & 1 & 0 \\ 0 & 1 & 0 & {\color{Red} \alpha } & 1 \\ 0 & 0 & 1 & {\color{Red} \alpha } & 1 \\ 0 & 1 & {\color{Red} \alpha } & 1 & 0 \\ 1 & {\color{Red} \alpha } & 1 & 0 & 0 \end{array} \right| =- \left| \begin{array}{ccccc} 1 & 0 & {\color{Red} \alpha } & 1 & 0 \\ 0 & 1 & 0 & {\color{Red} \alpha } & 1 \\ 0 & 0 & 1 & {\color{Red} \alpha } & 1 \\ 0 & 0 & {\color{Red} \alpha } & 1-{\color{Red} \alpha } & -1 \\ 0 & {\color{Red} \alpha } & 1-{\color{Red} \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{Red} \alpha } & 1 \\ 0 & 1 & {\color{Red} \alpha } & 1 \\ 0 & {\color{Red} \alpha } & 1-{\color{Red} \alpha } & -1 \\ {\color{Red} \alpha } & 1-{\color{Red} \alpha } & -1 & 0 \end{array} \right|=- \left| \begin{array}{cccc} 1 & 0 & {\color{Red} \alpha } & 1 \\ 0 & 1 & {\color{Red} \alpha } & 1 \\ 0 & {\color{Red} \alpha } & 1-{\color{Red} \alpha } & -1 \\ 0 & 1-{\color{Red} \alpha } & -1-{\color{Red} \alpha }^2 & -{\color{Red} \alpha } \end{array} \right|= $$ (the first row multiplied by $ {\color{Red} \alpha } $ is subtracted from the last one), expand the determinant by the first column: $$ =-\left| \begin{array}{ccc} 1 & {\color{Red} \alpha } & 1 \\ {\color{Red} \alpha } & 1-{\color{Red} \alpha } & -1 \\ 1-{\color{Red} \alpha } & -1-{\color{Red} \alpha }^2 & -{\color{Red} \alpha } \end{array} \right|= -\left| \begin{array}{ccc} 1 & {\color{Red} \alpha } & 1 \\ {\color{Red} \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{Red} \alpha } $ is added to the third one), expand the determinant by the last column: $$ =-\left| \begin{array}{cc} {\color{Red} \alpha }+1 & 1 \\ 1 & -1 \end{array} \right|=-(-({\color{Red} \alpha }+1)-1)={\color{Red} \alpha }+2 \ . $$ **Answer.** $ {\color{Red} \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{Red} \alpha } $ for which the polynomials $$ x^{3}+{\color{Red} \alpha }+\,x^2-14 \quad and \quad x^{3}+{\color{Red} \alpha }+\,x-14 $$ possess a multiple zero. !!§!! For the particular case $ g_{}(x)\equiv f^{\prime}(x) $, the resultant is transformed into ((detse:discrime#discriminant discriminant)). !!!!! The main application of the resultant ☞ ((:detse:resultante#elmination_of_variables_in_a_system_of_polynomial_equations 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 \lambda_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 ((#resultant_in_the_sylvester_form 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 root, 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 root 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 root of the polynomials $$ f(x)=a_0x^5+a_1x^4+a_2x^3+a_3x^2+a_4x+a_5 \quad \mbox{ 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 ((detse:discrime#subdiscriminants subdiscriminants)). ===Resultant in the Kronecker form== For the polynomials $$ f(x)=a_0x^n+a_1x^{n-1}+\ldots+a_n\quad and \quad g(x)=b_0x^m+b_1x^{m-1}+\ldots+b_m $$ ($ a_{0}\ne 0 $) find first the expansion of the fraction $ g_{}(x)/f(x) $ in Laurent series in negative powers of $ x_{} $. For the case $ \deg g < \deg f $, represent this expansion with undetermined coefficients $$ \frac{g(x)}{f(x)}=\frac{c_0}{x}+\frac{c_1}{x^2}+\dots+\frac{c_j}{x^{j+1}}+\dots \ , $$ multiply then this by $ f_{}(x) $, and equate the coefficients of equal powers of $ x_{} $ in both sides. For the case $ m=n-1 $ these formulas take the form $$ \begin{array}{ll} c_0&=b_{0}/a_0,\\ c_1& =(-c_{0}a_1+b_1)/a_0,\\ c_2& =(-c_{0}a_2-c_1a_1+b_2)/a_0, \\ \dots & \dots \\ c_{n-1}&=(-c_0a_{n-1}-c_1a_{n-2}-\dots-c_{n-2}a_1+b_{n-1})/a_0,\\ c_{K+n}&=(-c_{K}a_{n}-c_{K+1}a_{n-1}-\dots-c_{K+n-1}a_1)/a_0 \quad if \quad K \in \{0,1,2,\dots \} \ . \end{array} $$ If $ m ☞ ((#subresultants_and_the_greatest_common_divisor SECTION)), one has $ \operatorname{GCD}(f,g) $ is of the degree $ 2_{} $. **Answer.** Two common roots. The next result yields the explicit representation of subresultants via the roots of $ f_{}(x) $. !!Th!! **Theorem**. //If all the roots of// $ f_{}(x) $ //are simple then the following equality holds:// $$ C_p=\sum v(\lambda_{j_1},\dots,\lambda_{j_p})^2\ \frac{g(\lambda_{j_1})}{f'(\lambda_{j_1})}\times \dots \times \frac{g(\lambda_{j_p})}{f'(\lambda_{j_p})} \ ; $$ //here the sum is extended to all the possible systems of indices// $$ (j_1,\dots, j_p),\ 1\le j_1 < j_2 < \dots < j_p \le n, $$ //while// $$ v(\lambda_{j_1},\dots, \lambda_{j_p})= \prod_{1\leq K ♦ 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 * $ \lambda_{j} + \lambda_k $; * $ \lambda_{j} \lambda_k $; * $ (\lambda_{j} - \lambda_k)^2 $; here $ 1\le j 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_and_the_greatest_common_divisor 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 ((#resultant_in_the_Sylvester_form 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 ((#resultant_in_the_Sylvester_form 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 **eliminant**[[The notion was common for the old textbooks in algebra; but nearly never used in the modern publications.]] 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_and_the_greatest_common_divisor 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} ) \ . $$ {{ dets:intersect1.gif |}} **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 ((#references [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 \mbox{ 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 ((#resultant_in_the_sylvester_form 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 \mbox{ 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 ☞ ((#properties 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.** ((http://www.apmath.spbu.ru/ru/staff/uteshev/elimination/ 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. Text ☞ ((https://www.sciencedirect.com/science/article/pii/0024379593902064 HERE)) (pdf)