The resultant

For univariate polynomials $f, g$ over a field the following lemma says that it is possible to find polynomials $s, t$ such that $s f + t g = 0$ , ${\deg}(s) < {\deg}(g)$ , ${\deg}(t) < {\deg}(f)$ if and only if ${\gcd}(f,g) \neq 1$ .

Lemma 1   Let $f, g \in {\bf k}[x]$ be nonzero polynomials over the field k. Then the following statements are equivalent.

• ${\gcd}(f,g) \neq 1$
• There exist polynomials $s, t \in R[x] \setminus \{ 0 \}$ such that

  $$s f + t g \ = \ 0, \ \ \ \ {\deg}(s) < {\deg}(g) \ \ \ \ {\rm and} \ \ \ \ {\deg}(t) < {\deg}(f)$$ (24)

  
  

Proof. Let $h = {\gcd}(f,g)$ . If $h \neq 1$ then ${\deg}(h) \geq 1$ and a solution is

$$(s,t) \ = \ (g / h, -f /h)$$ (25)

Conversely, let $(s, t)$ be a solution. Assume that $f$ and $g$ are coprime. Then $s f = - t g$ would imply $f \mid t$ . This is impossible since $t \neq 0$ and ${\deg}(t) < {\deg}(f)$ . Hence $f$ and $g$ are not coprime and ${\gcd}(f,g) \neq 1$ holds. $\qedsymbol$

Remark 7   Given $f, g \in {\bf k}[x]$ nonzero polynomials of degrees $n, m$ respectively we consider the map

$${\phi}: \ \left. \begin{array}{lll} {\bf k}[x] \times {\bf k}[x] ... ...ightarrow & {\bf k}[x] \\ (s,t) & \longmapsto & s f + tg \\ \end{array} \right.$$ (26)

For $d \in {\mbox{${\mathbb{N}}$}} \setminus \{ 0 \}$ we define

$$P_d \ = \ \{ p \in {\bf k}[x] \ \mid \ {\deg}(p) < d \}$$ (27)

with the convention that

$$P_0 \ = \ \{ 0 \}$$ (28)

The restriction of ${\phi}$ to $\ P_m \times P_n \ \rightarrow \ P_{n+m}$ is a linear map ${\phi}_0$ between vector spaces of finite dimension.

Proposition 4   Let $f, g \in {\bf k}[x]$ nonzero polynomials of degrees $n, m$ such that $n + m > 0$ . Then we have:

• ${\gcd}(f,g) = 1 \ \ \iff \ \ {\phi}_0$ is an isomorphism.
• If ${\gcd}(f,g) = 1$ then the Bézout coefficients $(u,v)$ computed by the Extended Euclidean Algorithm form the unique solution in $P_m \times P_n$ of the equation

  $${\phi}_0(u,v) \ = \ 1$$ (29)

  
  

Proof. From Lemma 1 we deduce that the kernel of ${\phi}_0$ is reduced to $\{ 0 \}$ iff ${\gcd}(f,g) = 1$ . Since both $P_m \times P_n$ and $P_{n+m}$ have dimension $n + m$ this proves the first claim. The second claim is a consequence of the first one. $\qedsymbol$

Remark 8   Let's carry on with $f, g$ nonzero univariate polynomials in $x$ of degrees $n, m$ such that $n + m > 0$ . However let us relax the hypothesis on the coefficient ring by assuming that it is just a commutative ring $R$ with identity element. Let us write:

$$f \ = \ f_n x^n + \cdots + f_0 \ \ \ \ {\rm and} \ \ \ \ g \ = \ g_m x^m + \cdots + g_0$$ (30)

The natural basis for $P_m \times P_n$ consists of the $(x^i, 0)$ for $0 \leq i < m$ followed by the $(0, x^j)$ for $0 \leq j < m$ . On this basis ${\phi}_0$ is represented by the following matrix

$$\left( \begin{array}{cccccccc} f_0 & 0 &\cdots & 0 & g_0 & 0 &\cd... ...s & \ddots & \\ 0 &\cdots & 0 & f_n & 0 &\cdots &0 & g_m \\ \end{array} \right)$$ (31)

where all entries outside of the parallelograms are equal to zero.

Definition 4   The above square matrix of order $n + m$ is denoted ${\rm Sylv}(f,g)$ and called the Sylvester matrix of $f$ and $g$ . Its determinant is called the resultant of $f$ and $g$ denoted by ${\rm res}(f,g)$ . We make the following conventions.

• If $n = m = 0$ (and still nonzero polynomials) we define ${\rm res}(f,g) = 1$ .
• If $f = 0$ or $f \in R[x] \setminus R$ then ${\rm res}(f,0) = {\rm res}(0,f) = 0$ .
• If $f \in R \setminus \{ 0 \}$ then ${\rm res}(f,0) = {\rm res}(0,f) = 1$ .

Proposition 5   Let $f, g \in {\bf k}[x]$ be nonzero univariate polynomials over a field ${\bf k}$ . Then the following statements are equivalent

1. ${\gcd}(f,g) = 1$ .
2. ${\rm res}(f,g) \neq 0$ .
3. there do not exist any $s,t \in {\bf k}[x] \setminus \{ 0 \}$ such that

   $$s f + t g = 0, \ \ {\deg}(s) < {\deg}(g) \ \ \ \ {\rm and} \ \ \ \ {\deg}(t) < {\deg}(f).$$ (32)

   
   

Proof. This follows from Proposition 4 and the fact that ${\rm res}(f,g)$ is a determinant of the linear map ${\phi}_0$ . $\qedsymbol$

Proposition 6   Let $f,g \in R[x]$ be nonzero univariate polynomials over a UFD $R$ . Then we have

$${\gcd}(f,g) \in R \ \ \ \ \iff \ \ \ \ {\rm res}(f,g) \neq 0.$$ (33)

Proof. This follows from the adaptation of the results of Lemma 1 and Proposition 4 to the case where the ground ring is a UFD (and in particular an integral domain) instead of a field. $\qedsymbol$

Proposition 7   Let $f,g \in R[x]$ be nonzero univariate polynomials over an integral domain $R$ . Then there exist nonzero $s, t \in R[x]$ such that

$$s f + t g = {\rm res}(f,g), \ \ {\deg}(s) < {\deg}(g) \ \ \ \ {\rm and} \ \ \ \ {\deg}(t) < {\deg}(f).$$ (34)

Proof. Let ${\bf k}$ be the field of fractions of $R$ . If ${\rm res}(f,g) = 0$ then we know that there exist $s,t \in {\bf k}[x] \setminus \{ 0 \}$ such that

$$s f + t g = 0, \ \ {\deg}(s) < {\deg}(g) \ \ \ \ {\rm and} \ \ \ \ {\deg}(t) < {\deg}(f).$$ (35)

Then the claim follows by cleaning up the denominators.

If ${\rm res}(f,g) \neq 0$ then $f$ and $g$ are coprime in ${\bf k}[x]$ . Then there exists $u,v \in {\bf k}[x]$ with stated degree bounds such that $u f + v g = 1$ holds in ${\bf k}[x]$ . Observe that

• The coefficients of $u,v$ are in fact the unique solution of a linear system whose matrix is the Sylvester ${\rm Sylv}(f,g)$ matrix of $f$ and $g$ .
• These coefficients can be computed by the Cramer's rule.
• Hence each of these coefficients is the quotient of a determinant of a submatrix of ${\rm Sylv}(f,g)$ by ${\rm res}(f,g)$ .

Then the polynomials $s = {\rm res}(f,g) \ u$ and $t = {\rm res}(f,g) \ v$ have coefficients in $R$ and we have the desired relations. $\qedsymbol$