# 西爾維斯特矩陣、結式

Sylvester matrix and resultant

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\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

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### 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$。

<!-- eng start -->
Find the standard basis $\alpha$ of $\mathcal{P}_2\times\mathcal{P}_1$ and the standard basis $\beta$ of $\mathcal{P}_4$.
<!-- eng end -->

##### Exercise 1(b)

寫出 $p$ 與 $q$ 的西爾維斯特矩陣 $A$。

<!-- eng start -->
Find the Sylvester matrix $A$ of $p$ and $q$.
<!-- eng end -->

##### Exercise 1(c)

判斷 $p,q$ 是否互質。

<!-- eng start -->
Determine if $\gcd(p,q) = 1$.
<!-- eng end -->

## Exercises

##### Exercise 2

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

<!-- eng start -->
For each pair of the following $p$ and $q$, find the Sylvester matrix of them and determine if $\gcd(p,q) = 1$.
<!-- eng end -->

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

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

##### Exercise 3

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

<!-- eng start -->
Show that the Sylvester matrix $S_{p,q}$ is indeed $[f]_\alpha^\beta$.
<!-- eng end -->

##### Exercise 4

執行以下程式碼。
嘗試各種不同的 $p,q$。
令 $A$ 為它們的西爾維斯特矩陣﹐
將 $A$ 左上和右下翻轉後得到 $B$。
令 $R$ 為 $B$ 的最簡階梯形式矩陣。
觀察 $\gcd(p,q)$ 和 $R$ 的關係﹐並說明為什麼。

<!-- eng start -->
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.
<!-- eng end -->

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

<!-- eng start -->
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}\}.
$$
<!-- eng end -->