# 圖與特徵方程式

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

from lingeo import random_int_list
from gnm import matrix_digraph, illustrate_sk

## Main idea

Let $A$ be an $n\times n$ matrix.
From 507, we know that
$$
\det(A - xI) = s_0(-x)^n + s_1(-x)^{n-1} + \cdots + s_n.
$$
with
$$
s_k = \sum_{\substack{\alpha\subseteq[n] \\ |\alpha| = k}} \det A[\alpha].
$$

We also know that the determinants can be calculated through graph theory in 414.
In this section, we will see how $s_k$ can be found through the digraph of $A$.

Let $\Gamma$ be the weighted digraph of $A$ and $\alpha\subseteq [n]$ a subset of vertices.
An **elementary subgraph on $\alpha$** of $\Gamma$ is a subgraph $H$ of $\Gamma$ such that

- $V(H) = \alpha$,
- $E(H) \subseteq E(\Gamma)$, and
- every vertex of $H$ has exactly one directed edge leaving it and exactly one directed edge arriving it.

The set of all elementary subgraphs on $\alpha$ of $\Gamma$ is denoted by $\mathfrak{E}_\alpha(\Gamma)$.

Every elementary subgraph on $\alpha$ must be composed of some cycles.
Let $c(H)$ be the number of cycles, including loops, doubly directed edges, and cycles of length at least $3$.
The **sign** of $H$ is defined as $\sgn(H) = (-1)^{|\alpha| + c(H)}$.
The **weight** of $H$ is defined as the product of the weights of every edges of $H$.

We vacuously define the graph $H$ with no edge and no vertex as the only elementary subgraph on $\emptyset$.
Its sign is $1$ and its weight is $1$.

Thus, we have
$$
\det A[\alpha] = \sum_{H\in\mathfrak{E}_\alpha(\Gamma)} \sgn(H) w(H).
$$

Moreover, let $\mathfrak{E}_k(\Gamma)$ be the set of all elementary subgraphs on $\alpha$ of $\Gamma$ with $|\alpha| = k$.
Then
$$
s_k = \sum_{\substack{\alpha\subseteq[n] \\ |\alpha| = k}} \det A[\alpha] = \sum_{H\in\mathfrak{E}_k(\Gamma)} \sgn(H) w(H).
$$

## Side stories

- companion matrix

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

n = 3
b = 3
l = random_int_list(n^2 - b, 3) + [0]*b
shuffle(l)
A = matrix(n, l)

pretty_print(LatexExpr("A ="), A)

if print_ans:
    Gamma = matrix_digraph(A)
    Gamma.show(edge_labels=True)
    for k in range(1,n+1):
        print("k =", k)
        illustrate_sk(A, k)
    print("characteristic polynomial =", (-1)^n * A.charpoly())

##### Exercise 1(a)

畫出 $\Gamma(A)$ 並標上每條邊的權重。

**[答案由汪駿佑同學提供]**
當 `seed = 100` 時，

$$
A = \begin{bmatrix}
2 & 1 & 0 \\
-2 & 1 & 0 \\
0 & 2 & 1
\end{bmatrix}.
$$


##### Exercise 1(b)

對於所有 $k = 1,2,3$，求出所有 $k$ 點的基本子圖，計算其正負號以及權重。

**[答案由汪駿佑同學提供]**

##### Exercise 1(c)

計算 $A$ 的特徵多項式。

**[答案由汪駿佑同學提供]**
藉由公式我們可以知道
$$
s_0 = 1 , s_1 = 2 , s_2 = 1 , s_3 = -4.
$$

因此特徵多項式為
$$
p_A(x) = s_0(-x)^3+s_1(-x)^2+s_2(-x)+s_3 = -x^3+2x^2-x-4.
$$

## Exercises

##### Exercise 2

令
$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0
\end{bmatrix}
$$
且 $\Gamma$ 為其賦權有向圖。
說明 $\mathfrak{E}_k(\Gamma)$ 在 $k = 0,\ldots, 4$ 的時候都是空集合，
而 $\mathfrak{E}_5(\Gamma)$ 只有一個基本子圖。
計算 $A$ 的特徵多項式。

**[答案由汪駿佑同學提供]**
根據圖形，當 $k=1,\ldots,4$ 時，並不滿足每個點一進一出的形式，故未完成循環，因此為空集合。也就是
$$
s_1 = s_2 = s_3 = s_4 = 0.
$$

而 $k = 5$ 的時候能夠滿足每個點一進一出的形式，並且我們能經由圖形看出 $s_5 = 1$。
所以 $A$ 的特徵多項式
$$
p_A(x) = s_0(-x)^5 + s_1(-x)^4 + s_2(-x)^3 + s_3(-x)^2 + s_4(-x) + s_5 = -x^5+1.
$$

##### Exercise 3

令
$$
A = \begin{bmatrix}
0 & 0 & 0 & 0 & -a_5 \\
1 & 0 & 0 & 0 & -a_4 \\
0 & 1 & 0 & 0 & -a_3 \\
0 & 0 & 1 & 0 & -a_2 \\
0 & 0 & 0 & 1 & -a_1
\end{bmatrix}
$$
且 $\Gamma$ 為其賦權有向圖。
說明 $\mathfrak{E}_k(\Gamma)$ 在 $k = 0,\ldots, 5$ 的時候都恰只有一個基本子圖。
計算 $A$ 的特徵多項式。

**[答案由汪駿佑同學提供]**

根據 $\Gamma$，我們可以看出當 $k = 1,\ldots,5$ 的情形，如下


根據圖形我們可以知道
$$
s_1=-a_1 , s_2=a_2 , s_3=-a_3 , s_4=a_4 , s_5=-a_5.
$$

故 $A$ 的特徵多項式：
$$
\begin{aligned}
p_A(x) &= s_0(-x)^5 + s_1(-x)^4 + s_2(-x)^3 + s_3(-x)^2 + s_4(-x) + s_5 \\
&= -x^5 - a_1x^4 - a_2x^3 - a_3x^2 - a_4x - a_5.
\end{aligned}
$$

##### Exercise 4

令
$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}
$$
計算 $A$ 的特徵多項式。

**[答案由汪駿佑同學提供]**
$A$ 的賦權有向圖 $\Gamma$：

$($ 箭頭所帶之權重皆為 $1$ $)$
我們觀察到 $\Gamma$ 所有的圈長度都是偶數，所以當 $k$ 為奇數時找不到使用 $k$ 個點的基本子圖，故當 $k$ 為奇數時，$s_k = 0$。也就是
$$
s_1 = s_3 = s_5 = s_7 = 0.
$$
偶數的部分：

$k = 2$ 時，可能的組合為
$$
{\{(1,2)}\},{\{(2,3)}\},{\{(3,4)}\},{\{(4,5)}\},{\{(5,6)}\},{\{(6,7)}\},{\{(7,8)}\}.
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $-1$。
所以根據公式，$s_2 = -7$。

\
$k = 4$ 時，可能的組合為
$$
\begin{array}{c}
\{{(1,2),(3,4)}\},\{{(2,3),(4,5)}\},\{{(3,4),(5,6)}\},\{{(4,5),(6,7)}\},\{{(5,6),(7,8)}\},\\
\{{(1,2),(4,5)}\},\{{(1,2),(5,6)}\},\{{(1,2),(6,7)}\},\{{(1,2),(7,8)}\},\{{(2,3),(5,6)}\},\\
\{{(2,3),(6,7)}\},\{{(2,3),(7,8)}\},\{{(3,4),(6,7)}\},\{{(3,4),(7,8)}\},\{{(4,5),(7,8)}\}.
\end{array}
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $1$。
所以根據公式，$s_4 = 15$。

\
$k = 6$ 時，可能的組合為
$$
\begin{array}{c}
\{{(1,2),(3,4),(5,6)}\},\{{(2,3),(4,5),(6,7)}\},\{{(3,4),(5,6),(7,8)}\},
\{{(1,2),(4,5),(6,7)}\},\{{(1,2),(3,4),(6,7)}\},\\
\{{(1,2),(3,4),(7,8)}\},\{{(2,3),(4,5),(7,8)}\},\{{(1,2),(3,5),(6,7)}\},\{{(1,2),(3,5),(6,8)}\},\{{(2,3),(4,6),(7,8)}\}.
\end{array}
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $-1$。
所以根據公式，$s_6 = -10$。

而當 $k = 8$ 時，可能的組合僅有
$$
{\{(1,2),(3,4),(5,6),(7,8)}\}
$$
一種，並且此組合的權重為 $1$，$\sgn(H)$ 為 $1$。所以 $s_8 = 1$。

故可知 $A$ 的特徵多項式：
$$
\begin{aligned}
p_A(x) &= s_0(-x)^8 + s_1(-x)^7 + s_2(-x)^6 + s_3(-x)^5 + s_4(-x)^4 + s_5(-x)^3 + s_6(-x)^2 + s_7(-x) + s_8 \\
&= x^8 - 7x^6 + 15x^4 - 10x^2 + 1.
\end{aligned}
$$

##### Exercise 5

令
$$
A = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}
$$
計算 $A$ 的特徵多項式。

**[答案由汪駿佑同學提供]**
$A$ 的賦權有向圖 $\Gamma$：

$($ 箭頭所帶之權重皆為 $1$ $)$
我們觀察到 $\Gamma$ 所有的圈長度都是偶數，所以當 $k$ 為奇數時找不到使用 $k$ 個點的基本子圖，故當 $k$ 為奇數時，$s_k = 0$。也就是
$$
s_1 = s_3 = s_5 = s_7 = 0.
$$

偶數的部分：

$k = 2$ 時，可能的組合為
$$
\{{(1,2)}\}，\{{(2,3)}\}，\{{(3,4)}\}，\{{(4,5)}\}，\{{(5,6)}\}，\{{(6,7)}\}，\{{(7,8)}\}，\{{(8,1)}\}.
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $-1$。
所以根據公式，$s_2 = -8$。

\
$k = 4$ 時，可能的組合為
$$
\begin{array}{c}
\{{(1,2),(3,4)}\},\{{(2,3),(4,5)}\},\{{(3,4),(5,6)}\},\{{(4,5),(6,7)}\},\{{(5,6),(7,8)}\},\\
\{{(6,7),(8,1)}\},\{{(1,2),(4,5)}\},\{{(1,2),(5,6)}\},\{{(1,2),(6,7)}\},\{{(1,2),(7,8)}\},\\
\{{(2,3),(8,1)}\},\{{(2,3),(5,6)}\},\{{(2,3),(6,7)}\},\{{(2,3),(7,8)}\},\{{(3,4),(6,7)}\},\\
\{{(3,4),(7,8)}\},\{{(3,4),(8,1)}\},\{{(4,5),(7,8)}\},\{{(4,5),(8,1)}\},\{{(5,6),(8,1)}\}.
\end{array}
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $1$。
所以根據公式，$s_4 = 20$。

\
$k = 6$ 時，可能的組合為
$$
\begin{array}{c}
\{{(1,2),(3,4),(5,6)}\},\{{(2,3),(4,5),(6,7)}\},\{{(3,4),(5,6),(7,8)}\},\{{(4,5),(6,7),(8,1)}\},\\
\{{(5,6),(7,8),(1,2)}\},\{{(6,7),(8,1),(2,3)}\},\{{(7,8),(1,2),(3,4)}\},\{{(8,1),(2,3),(4,5)}\},\\
\{{(1,2),(3,4),(6,7)}\},\{{(2,3),(4,5),(7,8)}\},\{{(3,4),(5,6),(8,1)}\},\{{(4,5),(6,7),(1,2)}\},\\
\{{(5,6),(7,8),(2,3)}\},\{{(6,7),(8,1),(3,4)}\},\{{(7,8),(1,2),(4,5)}\},\{{(8,1),(2,3),(5,6)}\}.
\end{array}
$$
這些組合的權重皆為 $1$，$\sgn(H)$ 皆為 $-1$。
所以根據公式，$s_6 = -16$。

\
$k = 8$ 時，可能的組合為
$$
{\{(1,2,3,4,5,6,7,8)}\},{\{(8,7,6,5,4,3,2,1)}\}, \\
{\{(1,2),(3,4),(5,6),(7,8)}\},{\{(2,3),(4,5),(6,7),(8,1)}\}.
$$
其中上排的權重為 $1$，$\sgn(H)$ 為 $-1$；下排的權重為 $1$，$\sgn(H)$ 為 $1$。
互相抵銷以後得到 $s_8 = 0$。

故可知 $A$ 的特徵多項式：
$$
\begin{aligned}
p_A(x) &= s_0(-x)^8 + s_1(-x)^7 + s_2(-x)^6 + s_3(-x)^5 + s_4(-x)^4 + s_5(-x)^3 + s_6(-x)^2 + s_7(-x) + s_8 \\
&= x^8 - 8x^6 +20x^4 - 16x^2.
\end{aligned}
$$

##### Exercise 6

令 $n_1$ 和 $n_2$ 為兩正整數。
令
$$
M = \begin{bmatrix}
O_{n_1,n_1} & B \\
A & O_{n_2,n_2}
\end{bmatrix}
$$
且 $\Gamma$ 為其賦權有向圖。
說明 $\mathfrak{E}_k(\Gamma)$ 在 $k$ 不是偶數時都是空集合，
因此 $s_k(M) = 0$。

**[答案由汪駿佑同學提供]**
令 $n_1$ 中數字形成的集合為 $R$，$n_2$ 中數字形成的集合為 $P$。
那麼我們能夠從 $M$ 的賦權有向圖 $\Gamma$ 中看出所有在 $B$ 中的元素都表現為 $\Gamma$ 中從 $R$ 指向 $P$ 的一邊；所有在 $A$ 中的元素都表現為 $\Gamma$ 中從 $P$ 指向 $R$ 的一邊。
以下為 $\Gamma$ 的示意圖：

通過此圖我們可以發現：
基於 $\Gamma$ 的結構，所有圈的長度都是偶數。所以 $\mathfrak{E}_k(\Gamma)$ 在 $k$ 不是偶數時都是空集合，因此 $s_k(M) = 0$。

##### Exercise 7

令 $n_1$、$n_2$、和 $n_3$ 為正整數。
令
$$
M = \begin{bmatrix}
O_{n_1,n_1} & B & O \\
O & O_{n_2,n_2} & C \\
A & O & O_{n_3,n_3}
\end{bmatrix}
$$
且 $\Gamma$ 為其賦權有向圖。
說明 $\mathfrak{E}_k(\Gamma)$ 在 $k$ 不是 $3$ 的倍數時都是空集合，
因此 $s_k(M) = 0$。

**[答案由汪駿佑同學提供]**
令 $n_1$ 中數字形成的集合為 $R$，$n_2$ 中數字形成的集合為 $P$，$n_2$ 中數字形成的集合為 $Q$。

那麼我們能夠從 $M$ 的賦權有向圖 $\Gamma$ 中看出所有在 $C$ 中的元素都表現為 $\Gamma$ 中從 $R$ 指向 $P$ 的一邊；所有在 $B$ 中的元素都表現為 $\Gamma$ 中從 $Q$ 指向 $R$ 的一邊；所有 $A$ 中的元素都表現為 $\Gamma$ 中從 $P$ 指向 $Q$ 的一邊。
以下為 $\Gamma$ 的示意圖：


通過此圖我們可以發現：
基於 $\Gamma$ 的結構，所有圈的長度都是 $3$ 的倍數。所以 $\mathfrak{E}_k(\Gamma)$ 在 $k$ 不是 $3$ 的倍數時都是空集合，因此 $s_k(M) = 0$。

:::info
分數 = 5
:::