西爾維斯特矩陣、結式

Creative Commons License
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,
\[\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:

$\gcd(p,q) = 1$.
$f$ is surjective.
$f$ is injective.
$S_{p,q}$ is invertible.
$\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$。

標點

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

標點
句子要完整

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

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

標點

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

中英數間空格
$det$ –> $\det$
後面幾小題一樣

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©

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

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

$gcd$ –> $\gcd$
中英數間空格
填上係數後可以發現皆有 $p,q$ 的公因式存在 –> 填上係數後可以發現皆是 $\gcd(p,q)$ 的倍式
且在矩陣$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}\}. \]

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

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

目前分數 6.5

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.