# 西爾維斯特矩陣、結式

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

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

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,
$$\operatorname{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

執行以下程式碼。

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

`set_random_seed(0)`

$p= 5x^2 + 3x - 4$

$q=3x^3 - 5x - 5$

$\alpha = \{(1,0), (x,0), (x^2,0), (0,1), (0,x)\}$

$\beta = \{1, x, x^2, x^3, x^4\}$

$$S_{p,q}=\begin{bmatrix}
-4&0&0&-5&0\\
3&-4&0&-5&-5\\
5&3&-4&0&-5\\
0&5&3&3&0\\
0&0&5&0&3
\end{bmatrix}
$$

##### Exercise 1(a)

寫出 $\mathcal{P}_2\times\mathcal{P}_1$ 的標準基底 $\alpha$、
以及 $\mathcal{P}_4$。

:::warning

- [x] 標點
:::

$Ans$

由 $\mathcal{P}_2$ 的標準基底 $\alpha_2=\{1, x, x^2\}$，

和 $\mathcal{P}_1$ 的標準基底 $\alpha_1=\{1,x\}$，

而 $\mathcal{P}_2\times\mathcal{P}_1$ 的標準基底 $\alpha = \{(a,0): a\in\alpha_2\} \cup \{(0,b) : b\in\alpha_1\}$。

得知 $\alpha= \{(1,0), (x,0), (x^2,0), (0,1), (0,x)\}$，

$\mathcal{P}_4$ 的標準基底為 $\{1,x,x^2,x^3,x^4\}$。

##### Exercise 1(b)

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

:::warning

- [x] 標點
- [x] 句子要完整
:::

$Ans$

西爾維斯特矩陣為
$$S_{p,q} = \begin{bmatrix}
| & ~ & | & | & ~ & | \\
[p]_\beta & \cdots & [x^{n-1}p]_\beta & [q]_\beta & \cdots & [x^{m-1}q]_\beta \\
| & ~ & | & | & ~ & | \\
\end{bmatrix}.
$$
將 $n=3$ , $m=2$ , $p= 3x^3 - 5x - 5$
, $q=5x^2 + 3x - 4$ 代入，

得到 $p,q$ 的西爾維斯特矩陣

$A=\begin{bmatrix}
-4&0&0&-5&0\\
3&-4&0&-5&-5\\
5&3&-4&0&-5\\
0&5&3&3&0\\
0&0&5&0&3
\end{bmatrix}$。

##### Exercise 1(c)

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

:::warning

- [x] 標點
:::

$Ans$

是，$S_{p,q}$ 經過列運算之後，發現沒有自由變數，表示此矩陣可逆，也就代表 $\gcd(p,q) = 1$

得 $p,q$ 互質。

## Exercises

##### Exercise 2

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

##### Exercise 2(a)

$p = 1 + 2x + x^2$、
$q = 2 + x$。

:::warning

- [x] 中英數間空格
- [x] $det$ --> $\det$
- [x] 後面幾小題一樣
:::

Ans
$$
S_{p,q}=\begin{bmatrix}
1&2&0\\
2&1&2\\
1&0&1
\end{bmatrix}
$$
由於 $\det(S_{p,q})=1\neq 0$，說明了 $S_{p,q}$ 為一可逆矩陣，也代表 $\gcd(p,q) = 1$，因此多項式 $p$ 跟 $q$ 互質。

##### Exercise 2(b)

$p = 1 + 2x + x^2$、
$q = 2 + 3x + x^2$。

ANS

$$
S_{p,q} = \begin{bmatrix}
1&0&2&0\\
2&1&3&2\\
1&2&1&3\\
0&1&0&1
\end{bmatrix}
$$

針對高階的矩陣，我們可以利用拉普拉斯展開法降階以獲取行列式值。 \
由於 $\det(S_{p,q})=0$，說明了 $S_{p,q}$ 為一不可逆矩陣，也代表 $\gcd(p,q)\neq 1$，因此多項式 $p$ 跟 $q$ 不是互質。

##### Exercise 2(c)

$p = 1 + 2x + x^2$、
$q = 6 + 11x + 6x^2 + x^3$。

ANS

$$
S_{p,q}=\begin{bmatrix}
1&0&0&6&0\\
2&1&0&11&6\\
1&2&1&6&11\\
0&1&2&1&6\\
0&0&1&0&1
\end{bmatrix}
$$
由於 $\det(S_{p,q})=0$，說明了 $S_{p,q}$ 為一不可逆矩陣，也代表 $\gcd(p,q)\neq 1$ ，因此多項式 $p$ 跟 $q$ 不是互質。

##### Exercise 3

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

:::success
good
:::

令
$$\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},
$$
又令 $\alpha$ 為 $\mathcal{P}_{n-1} \times \mathcal{P}_{m-1}$ 的基底，而 $\beta$ 為 $\mathcal{P}_{m+n-1}$ 的基底。
而 $\alpha = \{(1,0),(x,0),(x^2,0),...,(x^{n-1},0),(0,1),(0,x),(0,x^2),...,(0,x^{m-1})\}$ 。
接著觀察 $[f]_\alpha^\beta$ 。
依照定義， $[f]_\alpha^\beta$ 為將 $\alpha$ 內的向量一一代入 $f$ 並用 $\beta$ 表示出來的矩陣，即
$$
[f]_\alpha^\beta = \begin{bmatrix}
| & | & | & ~ & | & | & ~ & | \\
[f(1,0)]_\beta & [f(x,0)]_\beta & [f(x^2,0)]_\beta & ... & [f(x^{n-1},0)]_\beta & [f(0,1)]_\beta & ... & [f(0,x^{m-1})]_\beta \\
| & | & | & ~& | & | & ~ & |
\end{bmatrix}。
$$
而觀察將 $\alpha$ 內的向量代入 $f$ 的結果，會發現 $f(1,0) = p,f(x,0) = px,...,f(x^{n-1},0) = px^{n-1},f(0,1) = q,f(0,x^{m-1} = qx^{m-1})$ ，
則
$$
[f]_\alpha^\beta = \begin{bmatrix}
| & ~ & | & | & ~ & | \\
[p]_\beta & \cdots & [x^{n-1}p]_\beta & [q]_\beta & \cdots & [x^{m-1}q]_\beta \\
| & ~ & | & | & ~ & | \\
\end{bmatrix}$ 即 $S_{p,q}.
$$

##### Exercise 4

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

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

:::warning

- [x] $gcd$ --> $\gcd$
- [x] 中英數間空格
- [x] 填上係數後可以發現皆有 $p,q$ 的公因式存在 --> 填上係數後可以發現皆是 $\gcd(p,q)$ 的倍式
- [x] 且在矩陣$R$中，因為是由矩陣$B$所推倒而來，前幾列為 $p,q$ 被整理過後的一元二次式，因此也會有相同的公因式。 --> 且在矩陣 $R$ 中，任一列都是 $B$ 中列向量的線性組合，其所對應到的多項式皆為 $ap + bq$ 的形式，所以均是 $\gcd(p,q)$ 的倍式。而最後一個非零列的次方數最小，所以它就是 $\gcd(p,q)$。
:::

答：

當 $p = 1 + x$, $q = 1 + 2x + x^2$ 時
$$A=\begin{bmatrix}
1&0&1\\
1&1&2\\
0&1&1\\
\end{bmatrix},B=\begin{bmatrix}
1&2&1\\
1&1&0\\
0&1&1\\
\end{bmatrix},R=\begin{bmatrix}
1&0&-1\\
0&1&1\\
0&0&0\\
\end{bmatrix},\gcd(p,q) = x+1 .$$

當 $p = 1 + x^2$, $q = 1 + 2x$ 時
$$A=\begin{bmatrix}
1&1&0\\
0&2&1\\
1&0&2\\
\end{bmatrix},B=\begin{bmatrix}
2&1&0\\
0&2&1\\
1&0&1\\
\end{bmatrix},R=\begin{bmatrix}
1&0&0\\
0&1&0\\
0&0&1\\
\end{bmatrix},\gcd(p,q) = 1 .$$

當 $p = 2 + x$, $q = 4 + 8x + 3x^2$ 時
$$A=\begin{bmatrix}
2&0&4\\
1&2&8\\
0&1&3\\
\end{bmatrix},B=\begin{bmatrix}
3&8&4\\
1&2&0\\
0&1&2\\
\end{bmatrix},R=\begin{bmatrix}
1&0&-4\\
0&1&2\\
0&0&0\\
\end{bmatrix},\gcd(p,q) = x+2 .
$$

矩陣最下方不為零的列，按照順序從高次到低次排序，分別是 $x^2, x^1, x^0$，填上係數就是 $p,q$ 的公因式。其中在矩陣 $R$ 的第一列由上往下到不為零的前一列，填上係數後可以發現皆是 $\gcd(p,q)$ 的倍式，且在矩陣 $R$ 中，任一列都是 $B$ 中列向量的線性組合，其所對應到的多項式皆為 $ap + bq$ 的形式，所以均是 $\gcd(p,q)$ 的倍式。而最後一個非零列的次方數最小，所以它就是 $\gcd(p,q)$。
##### Exercise 5

令 $p,q$ 為兩多項式且 $g = \gcd(p,q)$。
證明
$$\{ap + bq: a,b\in \mathcal{P}\} = \{ag: a\in\mathcal{P}\}.
$$

:::warning

一邊是簡單的，$ap + bp$ 一定是 $cg$ 的形式。
另一邊要用到除法原理。
這題我直接掛懸賞。
:::

*ANS*
因為 $g$ 為 $p,q$ 公因式，因此我們可令 ${\{ap=g: a\in\mathcal{P}\}}$ ，${\{bq=g: d\in\mathcal{P}\}}$ ，不會了

:::info
目前分數 6.5
:::