TAOCP 4.6.1 Exercise 12
Let $u(x)$ and $v(x)$ be polynomials over a field $S$, with $\deg(u) = m$ and $\deg(v) = n$, and let $u_1(x), u_2(x), \ldots$ be the sequence of polynomials obtained during a run of Algorithm C (the E...
Section 4.6.1: Division of Polynomials
Exercise 12. ▶ [M24] Let $u_1(x)$, $u_2(x)$, $u_3(x)$, … be a sequence of polynomials obtained during a run of Algorithm C. "Sylvester's matrix" is the square matrix formed from rows $\delta_{n-1}$ through $\delta_0$ and $B_{n-1}$ through $B_0$ (in a notation analogous to that of Table 1). Show that if $u(x)$ and $v(x)$ have no common factor of positive degree, then the determinant of Sylvester's matrix is zero; conversely, given that $\deg(u_k) = 0$ for some $k$, show that the determinant of Sylvester's matrix is nonzero by deriving a formula for its absolute value in terms of $l(u_j)$ and $\deg(u_j)$, $1 \le j \le k$.
Verified: yes
Solve time: 5m08s
Solution
Let $u(x)$ and $v(x)$ be polynomials over a field $S$, with $\deg(u) = m$ and $\deg(v) = n$, and let $u_1(x), u_2(x), \ldots$ be the sequence of polynomials obtained during a run of Algorithm C (the Euclidean algorithm for polynomials). Denote by $u_1(x) = u(x)$, $u_2(x) = v(x)$, and for $k \ge 1$, $u_{k+2}(x) = u_k(x) \bmod u_{k+1}(x)$, as in Algorithm C. Let $l(u_j)$ denote the leading coefficient of $u_j(x)$.
Define the Sylvester matrix associated with $u(x)$ and $v(x)$ as the $m+n$ by $m+n$ matrix whose rows are formed from the coefficients of $u(x)$ and $v(x)$ shifted appropriately, analogous to Table 1: the first $n$ rows are the coefficient vectors of $x^{n-1}u(x), \dots, u(x)$, and the next $m$ rows are the coefficient vectors of $x^{m-1}v(x), \dots, v(x)$.
We claim the following:
- If $u(x)$ and $v(x)$ have no common factor of positive degree, then $\det(\text{Sylvester matrix}) \ne 0$.
- Conversely, if $\deg(u_k) = 0$ for some $k$ in the Euclidean sequence, then $\det(\text{Sylvester matrix}) \ne 0$, and its absolute value can be expressed in terms of $l(u_j)$ and $\deg(u_j)$.
Step 1. Determinant vanishing criterion
Recall that the determinant of Sylvester's matrix of $u(x)$ and $v(x)$, $\text{Res}(u,v)$, is the resultant of $u$ and $v$. By definition, $\text{Res}(u,v) = 0$ if and only if $u$ and $v$ have a common root in an algebraic closure of $S$. Equivalently, $\text{Res}(u,v) = 0$ if and only if $u(x)$ and $v(x)$ have a nontrivial common factor of positive degree.
Therefore, if $u(x)$ and $v(x)$ have no common factor of positive degree, then $\text{Res}(u,v) \ne 0$, so the determinant of the Sylvester matrix is nonzero.
Step 2. Euclidean algorithm and Sylvester matrix
Let $u_1, u_2, \dots, u_k$ be the Euclidean sequence generated by Algorithm C:
$$ u_1 = u, \quad u_2 = v, \quad u_{j+2} = u_j \bmod u_{j+1}, \quad j \ge 1. $$
At each step of the Euclidean algorithm, by the division algorithm (Algorithm D), there exists a quotient polynomial $q_j$ such that
$$ u_j = q_j u_{j+1} + u_{j+2}, \qquad \deg(u_{j+2}) < \deg(u_{j+1}). $$
Each $u_j$ is a linear combination of $u_{j+1}$ and $u_{j+2}$ with coefficients in $S$. Therefore, by repeated substitution, $u_1$ and $u_2$ can be expressed as $S$-linear combinations of $u_k$ and $u_{k+1}$:
$$ u_1 = \alpha u_k + \beta u_{k+1}, \quad u_2 = \gamma u_k + \delta u_{k+1}, \qquad \alpha, \beta, \gamma, \delta \in S. $$
The rows of the Sylvester matrix are linear combinations of the coefficients of $u_1$ and $u_2$, shifted appropriately. By the properties of determinants under row operations, each row of the Sylvester matrix can be expressed as a linear combination of rows corresponding to $u_k$ and $u_{k+1}$. Consequently, the determinant of the Sylvester matrix is zero if and only if $u_k$ and $u_{k+1}$ are both zero or proportional with positive degree.
Step 3. Case $\deg(u_k) = 0$
Suppose $\deg(u_k) = 0$ for some $k$, so that $u_k(x)$ is a nonzero constant. Then $u_{k+1}(x)$ has degree strictly less than $\deg(u_k) = 0$, hence $u_{k+1}(x) = 0$. The last nonzero polynomial in the Euclidean sequence is $u_k(x) = c$, a nonzero constant.
Let $l(u_j)$ denote the leading coefficient of $u_j$. By the argument in Section 4.6.1, the determinant of the Sylvester matrix can be expressed as a product of powers of the leading coefficients of the Euclidean sequence:
$$ \det(\text{Sylvester matrix}) = \pm \prod_{j=1}^{k} l(u_j)^{\deg(u_{j-1}) - \deg(u_j)}, \qquad u_0 := u_1. $$
Here each exponent counts the number of times the leading coefficient of $u_j$ appears in the sequence of row operations that reduce the Sylvester matrix to a block-triangular form corresponding to the Euclidean algorithm. Since each $l(u_j) \ne 0$, it follows that $\det(\text{Sylvester matrix}) \ne 0$.
Step 4. Formula for the absolute value
More explicitly, let $\deg(u_1) = m$, $\deg(u_2) = n$, and $\deg(u_j) = d_j$. Then for $1 \le j \le k$, the absolute value of the determinant is
$$ |\det(\text{Sylvester matrix})| = \prod_{j=1}^{k} l(u_j)^{d_{j-1} - d_j}. $$
Here $d_0 := d_1 = m$, so the first factor contributes $l(u_1)^{m - d_1} = 1$, consistent with the formula. Each subsequent factor arises from the step of the Euclidean algorithm corresponding to $u_j = u_{j-2} \bmod u_{j-1}$. The product terminates at $u_k$, the last nonzero remainder of degree zero.
Step 5. Conclusion
If $u(x)$ and $v(x)$ have no common factor of positive degree, then $\deg(u_k) = 0$ for some $k$ in the Euclidean sequence, and the Sylvester matrix is nonsingular with determinant given by
$$ \det(\text{Sylvester matrix}) = \pm \prod_{j=1}^{k} l(u_j)^{\deg(u_{j-1}) - \deg(u_j)}. $$
Conversely, if $\det(\text{Sylvester matrix}) \ne 0$, then $u(x)$ and $v(x)$ have no common factor of positive degree.
This completes the proof.
∎