西爾維斯特矩陣、結式

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

Main idea

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:

1. \(\gcd(p,q) = 1\).
2. \(f\) is surjective.
3. \(f\) is injective.
4. \(S_{p,q}\) is invertible.
5. \(\operatorname{res}(p,q)\neq 0\).

Side stories

• gcd by row operations
• multiple root

Experiments

Exercise 1

執行以下程式碼。

Run the code below.

### 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))

Exercise 1(a)

寫出 \(\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\).

Exercise 1(b)

寫出 \(p\) 與 \(q\) 的西爾維斯特矩陣 \(A\)。

Find the Sylvester matrix \(A\) of \(p\) and \(q\).

Exercise 1©

判斷 \(p,q\) 是否互質。

Determine if \(\gcd(p,q) = 1\).

Exercises

Exercise 2

對以下的 \(p\) 和 \(q\)﹐利用西爾維斯特矩陣判斷它們是否互質。

For each pair of the following \(p\) and \(q\), find the Sylvester matrix of them and determine if \(\gcd(p,q) = 1\).

Exercise 2(a)

\[ \begin{aligned} p &= 1 + 2x + x^2, \\ q &= 2 + x. \end{aligned} \]

Exercise 2(b)

\[ \begin{aligned} p &= 1 + 2x + x^2, \\ q &= 2 + 3x + x^2. \end{aligned} \]

Exercise 2©

\[ \begin{aligned} p &= 1 + 2x + x^2, \\ q &= 6 + 11x + 6x^2 + x^3. \end{aligned} \]

Exercise 3

說明西爾維斯特矩陣 \(S_{p,q}\) 就是 \([f]_\alpha^\beta\)。

Show that the Sylvester matrix \(S_{p,q}\) is indeed \([f]_\alpha^\beta\).

Exercise 4

執行以下程式碼。
嘗試各種不同的 \(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)))

Exercise 5

令 \(p,q\) 為兩多項式且 \(g = \gcd(p,q)\)。
證明

\[ \{ap + bq: a,b\in \mathcal{P}\} = \{ag: a\in\mathcal{P}\}. \]

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}\}. \]