Sylvester matrix and resultant
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\newcommand{\trans}{^\top} \newcommand{\adj}{^{\rm adj}} \newcommand{\cof}{^{\rm cof}} \newcommand{\inp}[2]{\left\langle#1,#2\right\rangle} \newcommand{\dunion}{\mathbin{\dot\cup}} \newcommand{\bzero}{\mathbf{0}} \newcommand{\bone}{\mathbf{1}} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\nul}{\operatorname{null}} \newcommand{\rank}{\operatorname{rank}} %\newcommand{\ker}{\operatorname{ker}} \newcommand{\range}{\operatorname{range}} \newcommand{\Col}{\operatorname{Col}} \newcommand{\Row}{\operatorname{Row}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\vspan}{\operatorname{span}} \newcommand{\Vol}{\operatorname{Vol}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\idmap}{\operatorname{id}} \newcommand{\am}{\operatorname{am}} \newcommand{\gm}{\operatorname{gm}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\iner}{\operatorname{iner}}$
from lingeo import random_int_list
from linspace import vtop, ptov, syl
Let $p$ and $q$ be two polynomials.
The greatest common divisor of $p$ and $q$ is the polynomial $g$ of largest degree such that $g \mid p$ and $g\mid q$.
This polynomial is unique up to scalar multiplication, so usually we let $\gcd(p,q)$ be the one with leading coefficeint $1$.
By the Euclidean algorithm, it is known that the following two sets are equal.
$$\{ap + bq: a,b\in \mathcal{P}\} = \{ag: a\in\mathcal{P}\},$$
where $\mathcal{P}$ is the set of all polynomials.
A refined version is as follows.
Let $p$ and $q$ be two polynomials of degree $m$ and $n$, respectively.
Then
$$\{ap + bq \in\mathcal{P}_{m+n}: a\in\mathcal{P}_{n-1},b\in\mathcal{P}_{m-1}\} = \{ag \in\mathcal{P}_{m+n}: a\in\mathcal{P}\}.$$
Given two polynomials $p, q$ of degrees $m,n$, consider the function
$$\begin{array}{rccc}
f : & \mathcal{P}_{n-1} \times \mathcal{P}_{m-1} & \rightarrow & \mathcal{P}_{m+n-1} \\
& (a,b) & \mapsto & ap + bq \\
\end{array},$$
which is linear.
Thus,
$$\range(f) = \{ap + bq \in\mathcal{P}_{m+n-1}: a\in\mathcal{P}_{n-1},b\in\mathcal{P}_{m-1}\} = \{ag \in\mathcal{P}_{m+n-1}: a\in\mathcal{P}\},$$
where $g = \gcd(p,q)$.
Therefore, $f$ is surjective if and only if $\gcd(p,q) = 1$.
Let $\alpha_q = \{1,\ldots, x^{n-1}\}$ and $\alpha_q = \{1,\ldots, x^{m-1}\}$ be the standard bases of $\mathcal{P}_{n-1}$ and $\mathcal{P}_{m-1}$.
Let
$$\alpha = \{(a,0): a\in\alpha_p\} \cup \{(0,b) : b\in\alpha_q\}.$$
Then $\alpha$ is a basis of $\mathcal{P}_{n-1}\times\mathcal{P}_{m-1}$.
On the other hand, let $\beta$ be the standard basis of $\mathcal{P}_{m+n-1}$.
Construct the $(m + n)\times (m + n)$ matrix
$$S_{p,q} = \begin{bmatrix}
| & ~ & | & | & ~ & | \\
[p]_\beta & \cdots & [x^{n-1}p]_\beta & [q]_\beta & \cdots & [x^{m-1}q]_\beta \\
| & ~ & | & | & ~ & | \\
\end{bmatrix}.$$
Then $S_{p,q} = [f]_\alpha^\beta$ and is called the Sylvester matrix of $p$ and $q$.
The determinant of $S_{p,q}$ is called the resultant of $p$ and $q$, denoted as $\operatorname{res}(p,q)$.
(We have not learnt the properties of the determinant, but at least it make senses when $S_{p,q}$ is a small matrix.)
Let $p,q$ be two polynomials.
Let $S_{p,q}$ their Sylvester matrix and $\operatorname{res}(p,q)$ the resultant.
Then the following are equivalent:
### code
set_random_seed(0)
print_ans = False
m,n = 2,3
p = vtop(vector(random_int_list(m+1)))
q = vtop(vector(random_int_list(n+1)))
print("p =", p)
print("q =", q)
A = syl(p,q)
if print_ans:
print("alpha = {(1,0), (x,0), (x^2,0), (0,1), (0,x)}")
print("beta = {1, x, x^2, x^3, x^4}")
print("Spq =")
show(A)
print("gcd(p,q) = 1?", (A.determinant() != 0))
寫出 $\mathcal{P}_2\times\mathcal{P}_1$ 的標準基底 $\alpha$、
以及 $\mathcal{P}_4$ 的標準基底 $\beta$。
Find the standard basis $\alpha$ of $\mathcal{P}_2\times\mathcal{P}_1$ and the standard basis $\beta$ of $\mathcal{P}_4$.
對以下的 $p$ 和 $q$﹐利用西爾維斯特矩陣判斷它們是否互質。
For each pair of the following $p$ and $q$, find the Sylvester matrix of them and determine if $\gcd(p,q) = 1$.
說明西爾維斯特矩陣 $S_{p,q}$ 就是 $[f]_\alpha^\beta$。
Show that the Sylvester matrix $S_{p,q}$ is indeed $[f]_\alpha^\beta$.
執行以下程式碼。
嘗試各種不同的 $p,q$。
令 $A$ 為它們的西爾維斯特矩陣﹐
將 $A$ 左上和右下翻轉後得到 $B$。
令 $R$ 為 $B$ 的最簡階梯形式矩陣。
觀察 $\gcd(p,q)$ 和 $R$ 的關係﹐並說明為什麼。
Run the code below. Try different choices of $p$ and $q$. Let $A$ be their Sylvester matrix and $B$ the matrix obtained from $A$ by flipping along the skew diagonal (the one from bottom-left to top-right). Let $R$ be the reduced echelon form of $B$. Find a relation between $\gcd(p,q)$ and $R$ and provide your reasons.
p = 1 + x
q = 1 + 2*x + x**2
A = syl(p,q)
B = A.antitranspose()
R = B.rref()
print("A =")
show(A)
print("B =")
show(B)
print("R =")
show(R)
print("gcd =", p.polynomial(QQ).gcd(q.polynomial(QQ)))
令 $p,q$ 為兩多項式且 $g = \gcd(p,q)$。
證明
Let $p$ and $q$ be polynomials and $g = \gcd(p,q)$. Show that
$$ \{ap + bq: a,b\in \mathcal{P}\} = \{ag: a\in\mathcal{P}\}. $$