# 圖與特徵方程式

Graph and characteristic polynomial

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

執行以下程式碼。

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

### 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)$ 並標上每條邊的權重。

<!-- eng start -->
Draw $\Gamma(A)$ and mark the weight on each edge.
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
For each $k = 1,2,3$, find all elementary subgraphs of order $k$, their signs, and their weights.
<!-- eng end -->

##### Exercise 1(c)

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

<!-- eng start -->
Find the characteristic polynomial of $A$.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## 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$ 的特徵多項式。

<!-- eng start -->
Let

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

and $\Gamma$ its weighted directed graph. Show that $\mathfrak{E}_k(\Gamma)$ is empty for $k = 0,\ldots, 4$ and $\mathfrak{E}_5(\Gamma)$ contains only one elementary subgraph. Use these facts to find the characteristic polynomial of $A$.
<!-- eng end -->

##### 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$ 的特徵多項式。

<!-- eng start -->
Let

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

and $\Gamma$ its weighted directed graph. Show that $\mathfrak{E}_k(\Gamma)$ is empty for $k = 0,\ldots, 4$ and $\mathfrak{E}_5(\Gamma)$ contains only one elementary subgraph. Use these facts to find the characteristic polynomial of $A$.
<!-- eng end -->

##### 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$ 的特徵多項式。

<!-- eng start -->
Let

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

Find the characteristic polynomial of $A$.
<!-- eng end -->

##### 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$ 的特徵多項式。

<!-- eng start -->
Let

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

Find the characteristic polynomial of $A$.
<!-- eng end -->

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

<!-- eng start -->
Let $n_1$ and $n_2$ be positive integers. Let

$$
M = \begin{bmatrix}
O_{n_1,n_1} & B \\
A & O_{n_2,n_2}
\end{bmatrix}
$$

and $\Gamma$ its weighted directed graph. Show that $\mathfrak{E}_k(\Gamma)$ is empty whenever $k$ is not even, so $s_k(M) = 0$.
<!-- eng end -->

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

<!-- eng start -->
Let $n_1$, $n_2$, and $n_3$ be positive integers. Let

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

and $\Gamma$ its weighted directed graph. Show that $\mathfrak{E}_k(\Gamma)$ is empty whenever $k$ is not a multiple of $3$, so $s_k(M) = 0$.
<!-- eng end --