---
title: 2021SMath207 Week15
tags: 2021S, Math207
---
## 15: 特徵多項式、二部圖、獨立集 (2021/05/30~2021/06/05)
### 這週要做的事
#### 影片（每週二上課前完成）
- [video 15](https://www.youtube.com/watch?v=JtzNEBRyFGQ&list=PLjjwN6s_CKYkKW_wqQFBNluqrUdWdvPMM&index=60): Characteristic polynomial
- reading assignment: Example 3.1 (Page 25--26) in [Graphs and matrices by R. B. Bapat](https://dec.lib.nsysu.edu.tw/search~S1*cht/?searchtype=t&searcharg=graphs%20and%20matrices)
- questions 15: 請到[網路大學](https://cu.nsysu.edu.tw/) > 1092_離散數學（二）> 作業評量區 > 測驗 / 考試。只能做答一次，限時 60 分鐘。（週二上課前 3:00 pm 截止）
```python
AL 分數 += Question 分數
```
[//]: # (
char poly Sk
)
#### HW15（下週二 5:00 pm 前交給助教）
請註明姓名學號以及第幾次作業
1. 令 $K_{m,n}$ 為完全二部圖（一邊 $m$ 個點、另一邊 $n$ 個點、中間 $mn$ 條邊相連）。求 $A(K_{m,n})$ 的特徵多項式。
2. 令 $A$ 為下圖的相鄰矩陣。已知 $(1,1,2,1,1,2)^\top$ 為 $A$ 對應到 $\lambda = 2$ 的特徵向量，求 $A$ 對應到 $\lambda = -2$ 的特徵向量。
---
### 特徵多項式
令 $A$ 是一個 $n\times n$ 的矩陣
若 $\alpha\subseteq [n]$
則 $A[\alpha]$ 代表 $A$ 在 $\alpha$ 中的 row 和 column 所導出的子矩陣
我們定義
$$S_k = \sum_{\substack{\alpha\subseteq [n] \\ |\alpha| = k}}\det(A[\alpha]).$$
因此 $S_1 = \operatorname{tr}(A)$ 且 $S_n = \det(A)$。
方便起見
定義 $S_0 = 1$。
一個方陣的特徵多項式是
$$p(x) = \det(A - xI)$$
##### Theorem (Characteristic polynomial)
令 $A$ 為一方陣
則其特徵多項式可以表示為
$$p(x) = S_0(-x)^n + S_1(-x)^{n-1} + \cdots + S_n(-x)^0.$$
:::success
試試看：
計算以下矩陣的特徵多項式
1. $A(P_3)$
2. $A(K_3)$
3. $A(K_n)$
:::
若 $G$ 的點集為 $[n]$
則 $\alpha$ 也可以視為是一些點
如果 $H$ 是 $G$ 的一個子圖
且 $V(H) = \alpha$
且每一個 $H$ 的連通區塊都是 $K_2$ 或一些 cycle
則我們說 $H$ 是 $G$ 的 **elementary subgraph on $\alpha$**
我們可以同樣
令 $c(H)$ 為 $H$ 中 cycle 的個數
而 $m(H)$ 為 $H$ 中 $K_2$ 的個數
同時定義 $\mathcal{E}(G,\alpha)$ 為 $G$ 中所有的 elementary subgraph on $\alpha$
並令
$$\mathcal{E}_k(G) = \bigcup_{\substack{\alpha\subseteq [n] \\ |\alpha| = k}} \mathcal{E}(G,\alpha).$$
##### Theorem (Characteristic polynomial and elementary subgraphs)
若 $A$ 為一個 $n$ 個點的圖 $G$ 的相鄰矩陣
則 $A$ 的特徵多項式為
$$p(x) = S_0(-x)^n + S_1(-x)^1 + \cdots + S_n(-x)^0$$
其中
$$S_k = \sum_{H\in\mathcal{E}_k(G)} (-1)^{k + m(H) + c(H)} 2^{c(H)}.$$
:::success
試試看：
計算以下矩陣的特徵多項式
1. $A(P_4)$
2. $A(C_4)$
3. $A(K_n)$
4. $A(K_{m,n})$
:::
:bookmark:
---
### 特徵多項式與圖上的圈
如果 $G$ 有奇數個點
那麼所有 $G$ 的 elementary subgraph 一定會用到一些奇圈
（因為每個 $K_2$ 一次用掉兩個點）
也就是說
如果 $G$ 有奇數個點而且沒有任何奇圈當作子圖
則 $\mathcal{E}(G)$ 裡面沒有任何 elementary subgraph
因此 $\det(A(G)) = 0$。
然而我們知道以下敘述等價：
1. $G$ 是一個二部圖
2. $G$ 中沒有任何奇圈當作子圖
所以我們知道奇點數的二部圖的相鄰矩陣行列式值為 $0$。
:::info
回顧一下
每個樹都是一個二部圖
但我們早就知道奇點數的樹
其相鄰矩陣行列式值為 $0$
為什麼？
:::
更進一步來說
若 $G$ 是一個二部圖
則當 $k$ 是奇數時 $\mathcal{E}_k(G)$ 中沒有任何圖
所以 $S_k = 0$
##### Theorem (Characteristic polynomial of a bipartite)
令 $A$ 為圖 $G$ 的相鄰矩陣
且 $G$ 的點數為 $n$
以下敘述等價：
1. $G$ 是一個二部圖
2. $A$ 的特徵多項式的 $n-k$ 次係數當 $k$ 是奇數時皆為 $0$
3. $A$ 的特徵根依照 $0$ 對稱
（意思是有 $\lambda$ 就有 $-\lambda$ 且重數一樣）
:::success
試試看：
算一下下列矩陣的特徵多項式及特徵根
1. $A(K_{1,4})$
2. $A(C_4)$
3. $A(P_4)$
:::
---
### 二部圖的特徵向量
令 $G = (X\cup Y, E)$ 是一個二部圖
則 $G$ 的相鄰矩陣可以寫成
$$A = \begin{bmatrix} O_{|X|} & B \\ B^\top & O_{|Y|} \end{bmatrix}.$$
如果
$${\bf v} = \begin{bmatrix} {\bf x} \\ {\bf y} \end{bmatrix}$$
是 $A$ 對應於特徵值 $\lambda$ 的特徵向量
則有
$$\begin{aligned}
B{\bf y} = \lambda {\bf x} \\
B^\top{\bf x} = \lambda {\bf y}
\end{aligned}$$
如此一來
$${\bf v}' = \begin{bmatrix} {\bf x} \\ -{\bf y} \end{bmatrix}$$
就會滿足
$$\begin{aligned}
B{\bf y} = -\lambda {\bf x} \\
B^\top{\bf x} = -\lambda {\bf y}
\end{aligned}$$
以及 $A{\bf v}' = \lambda {\bf v}'$
所以 ${\bf v}'$ 是 $A$ 對應到特徵值 $-\lambda$ 的特徵向量
如此一來
$\lambda$ 和 $-\lambda$ 不只是重數相同
兩者的特徵空間 $E_\lambda = \operatorname{ker}(A - \lambda I)$ 和 $E_{-\lambda} = \operatorname{ker}(A + \lambda I)$
也有一個對應關係
（實際上這是向量空間的 isomorphism）
:bookmark:
---
### 圖的獨立集
令 $G = (V,E)$ 為一個圖
如果 $S\subseteq V$ 是一些點的集合
且 $G$ 在 $S$ 中任兩點都沒有邊
則我們說 $S$ 是 $G$ 中的**獨立集（independence set）**
同時定義 $\alpha(G)$ 為 $G$ 中最大的獨立集的點數
稱作**獨立數（independence number）**
一般來說要計算圖的獨立數是一個困難的問題
（是一個 NP-hard 的問題）
:::success
試試看：
算出以下圖 $G$ 的 $\alpha(G)$
1. $G = K_{1,10}$
2. $G = K_n$
3. $G = C_n$
4. $G = P_n$
:::
:::success
試試看：
如果 $G = (X\cup Y, E)$ 是一個二部圖
則 $\alpha(G) \geq \max\{|X|, |Y|\}$
能不能找到一個圖 $G$ 讓這個不等式是真的大於的
:::
### 獨立集與相鄰矩陣
若 $A$ 是圖 $G$ 的相鄰矩陣
而 $\alpha$ 是 $G$ 的一個獨立集
則子矩陣 $A[\alpha]$ 就是一個零矩陣
##### Proposition (Inertia of principal submatrices)
若 $A$ 是一個 $n\times n$ 的對稱矩陣
而 $B$ 是一個 $A$ 的 $k\times k$ 的 principal submatrix
則有以下關係：
1. $n_+(B) \leq n_+(A)$
2. $n_-(B) \leq n_-(A)$
3. $n_+(B) + n_0(B) \leq n_+(A) + n_0(A)$
4. $n_-(B) + n_0(B) \leq n_-(A) + n_0(A)$
:::spoiler Proof
參考 [Interlacing theorem](https://hackmd.io/@jlch3554/r1Bvgg2DO#Interlacing)
:::
數學家 [Dragoš Cvetković](http://www.mi.sanu.ac.rs/cv/cvcvetkovic.htm) 利用這樣的關係
提出以下關於獨立集的估計
##### Theorem (Cvetković's inertia bound)
若 $A$ 為圖 $G$ 的相鄰矩陣
則
$$\alpha(G) \leq \min\{n_+(A) + n_0(A), n_-(A) + n_0(A)\}.$$
:::spoiler Proof
若 $\alpha$ 為一獨立集
取 $B = A[\alpha]$
則
$$n_+(B) + n_0(B) = n_-(B) + n_0(B) = |\alpha|$$
:::
:::success
試試看：
對以下的圖 $G$，算出 $\alpha(G)$ 以及 $A(G)$ 的 inertia
看看 Cvetković's inertia bound 是否正確
1. $G = C_4$
2. $G = P_3$
3. $G = K_n$
4. $G = K_{m,n}$
:::
:::success
試試看：
一個 tree $T$ 的
1. independence number $\alpha(T)$
2. matching number $\alpha'(T)$
3. vertex cover number $\beta(T)$
4. $A(T)$ 的 inertia
5. $A(T)$ 的 rank
彼此有什麼關係？
:::
Sign in with Wallet
Connect another wallet