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
Let $A$ be an $n\times n$ matrix.
From 507, we know that
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
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
### 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())
對於所有 $k = 1,2,3$,求出所有 $k$ 點的基本子圖,計算其正負號以及權重。
For each $k = 1,2,3$, find all elementary subgraphs of order $k$, their signs, and their weights.
令
$$ 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$.
令
$$ 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$.
令
$$ 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$.
令
$$ 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$.
令 $n_1$ 和 $n_2$ 為兩正整數。
令
且 $\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$.
令 $n_1$、$n_2$、和 $n_3$ 為正整數。
令
且 $\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 --