Barnett's theorems about the greatest common divisor of several univariate polynomials through Bezout-like matrices
The authors gives a new approach of Barnett's theorem on the computation of the degree of the gcd of several univariate polynomials over an integral domain. Definition. If \(P(x)\) and \(Q(x)\) are polynomials such that \(d= \max\{\deg(P), \deg(Q)\}\) then the Bezout matrix associated to \(P(x)\) and \(Q(x)\) is: \[ \text{Bez}(P,Q)= \begin{pmatrix} c_{0,0} &\cdots &c_{0,d-1}\\ \vdots &&\vdots\\ c_{d-1,0} &\cdots &c_{d-1,d-1} \end{pmatrix} \] where \(c_{i,j}\) are defined by the formula: \[ \frac {P(x)Q(y)- P(y)Q(x)} {x-y}= \sum_{i,j=0}^{d-1} c_{i,j} x^i y^j. \] In the authors' main result the degree of the polynomials \(P\), \(Q_1, \dots, Q_t\) is given by \(n-\text{rank} {\mathcal B}_P(Q_1, \dots,Q_t)\), where \[ {\mathcal B}_P= \begin{pmatrix} \text{Bez}(P,Q_1) \\ \vdots \\ \text{Bez}(P,Q_t)\end{pmatrix} . \] The authors deduce an algorithm for computing the coefficients of the greatest common divisor of \(P\), \(Q_1\), \dots, \(Q_t\). There are also obtained other approaches of Barnett's theorem through Hankel, respectively hybrid Bézout matrices. A final section includes a complexity analysis for the computation of the gcd of several univariate polynomials.
computation of the greatest common divisor
scientific article; zbMATH DE number 1886742