圖與特徵方程式

Graph and characteristic polynomial

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

執行以下程式碼。

Run the code below.

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

Draw $\Gamma(A)$ and mark the weight on each edge.

Exercise 1(b)

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

For each $k = 1,2,3$, find all elementary subgraphs of order $k$, their signs, and their weights.

Exercise 1(c)

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

Find the characteristic polynomial of $A$.

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

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

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

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

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

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

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

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

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

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

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

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