This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
Equitable partition
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
Recall that $[n] = \{1,\ldots,n\}$.
We say $(X_1, \ldots, X_k)$ is a partition of $[n]$ if $X_1\cup \cdots \cup X_k = [n]$ and they are mutually disjoint.
Let $A$ be an $n\times n$ (not necessarily symmetric) matrix.
For subsets $X_1,X_2\subseteq [n]$, we define $A[X_i,X_j]$ as the submatrix of $A$ induced on the rows in $X_i$ and the columns in $X_j$.
A partition $\pi = (X_1,\ldots,X_k)$ of $[n]$ is called an equitable partition if
for any $i,j\in [n]$, the submatrix $A[X_i, X_j]$ has a constant row sum $s_{ij}$.
The quotient matrix of $A$ with respect to a equitable partition is an $k\times k$ matrix $\begin{bmatrix} s_{ij} \end{bmatrix}$, denoted by $A / \pi$.
Let $X$ be a subset of $[n]$.
The characteristic vector of $X$ is the vector $\phi_X$ in $\mathbb{R}^n$ such that
its entries corresponding to $X$ are $1$ while others are $0$.
Let $A$ be an $n\times n$ matrix and $\pi = (X_1, \ldots, X_k)$ a partition of $[n]$.
The following two statements are equivalent.
Consider the function $f_A\big|_V : V \rightarrow V$ defined by $\bv \mapsto A\bv$.
Note that $\beta = \{\phi_{X_1},\ldots,\phi_{X_k}\}$ is an orthogonal basis of $V$.
Then $[f_A\big|_V]_\beta^\beta$ is the quotient matrix $A/\pi$.
執行以下程式碼。
Run the code below.### code
set_random_seed(0)
print_ans = None
A = zero_matrix(5,5)
quo = random_int_list(3,2)
A[:3,:3] = graphs.CompleteGraph(3).laplacian_matrix() + quo[0] * identity_matrix(3)
A[3:,3:] = graphs.CompleteGraph(2).laplacian_matrix() + quo[2] * identity_matrix(2)
A[:3,3:] = quo[1] * ones_matrix(3,2)
A[3:,:3] = A[:3,3:].transpose()
pretty_print(LatexExpr("A ="), A)
if print_ans:
par = [[0,1,2],[3,4]]
print("an equitable partition can be", par)
k = len(par)
C = zero_matrix(k,k)
for i in range(k):
for j in range(k):
C[i,j] = sum(A[par[i], par[j]][0])
print("quotient matrix =")
show(C)
找出一個 $A$ 的等量分割。
Find an equitable partition of $A$.求出這個等量分割的商矩陣、及其所有特徵值。
Find the quotient matrix and its spectrum.求以下特定形態矩陣的特徵值。
Find the spectra of the following special matrices.已知
$$ A = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ \end{bmatrix} $$有特徵值 $0$ 且其重數為 $3$。
利用等量分割的方法來找出最後兩個特徵值。
求
$$ A = \begin{bmatrix} O_{m,m} & J_{m,n} \\ J_{n,m} & O_{n,n} \end{bmatrix} $$的所有特徵值。
這裡 $O$ 和 $J$ 分別是相對應大小的全零和全一矩陣。
求
$$ A = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \end{bmatrix} $$的所有特徵值。
Find the spectrum of $$ A = \begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \end{bmatrix}. $$令
$$ A = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ \end{bmatrix}. $$當 $X_1 = \{1\}$、$X_2 = \{2,3,4\}$ 時，$\pi = (X_1,X_2)$ 為 $A$ 的一個等量分割。
以下練習說明可以利用商矩陣的特徵向量回推原矩陣的特徵向量。
Let $$ A = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ \end{bmatrix}. $$ Then $\pi = (X_1,X_2)$ with $X_1 = \{1\}$ and $X_2 = \{2,3,4\}$ is an equitable partition of $A$. The following exercises shows how to find the eigenvectors of $A$ from the eigenvectors of the quotient matrix.將 $A\phi_{X_1}$ 和 $A\phi_{X_2}$ 分別寫成 $\beta = \{\phi_{X_1}, \phi_{X_2}\}$ 的線性組合。
令 $V = \vspan(\beta)$。
求出 $[f_A\big|_V]_\beta^\beta$。
計算 $A/\pi$ 並和上一題的結果作比較。
Find $A/\pi$ and compare it with your result of the previous exercise.計算 $A/\pi$ 的所有特徵值及特徵向量。
Find the spectrum of $A/\pi$ and the corresponding eigenvectors.若
$$ \bu = \begin{bmatrix} a \\ b \end{bmatrix} $$為 $A/\pi$ 的一特徵向量、且其特徵值為 $\lambda$。
驗證 $a\phi_{X_1} + b\phi_{X_2}$ 為 $A$ 的特徵向量、且其特徵值也是 $\lambda$。
說明為什麼。
令
$$ A = \begin{bmatrix} nI_m & -J_{m,n} \\ -J_{n,m} & mI_n \end{bmatrix}. $$求 $A$ 的所有特徵值和特徵向量。
Let $$ A = \begin{bmatrix} nI_m & -J_{m,n} \\ -J_{n,m} & mI_n \end{bmatrix}. $$ Find the spectrum of $A$ and the corresponding eigenvectors.令 $A$ 為一 $n\times n$ 矩陣、而 $\pi = (X_1,\ldots,X_k)$ 為一等量分割。
令 $\beta = \left\{\frac{1}{\|\phi_{X_1}\|}\phi_{X_1}, \ldots, \frac{1}{\|\phi_{X_k}\|}\phi_{X_k}\right\}$ 為 $\vspan(\beta)$ 的垂直標準基底。
將 $\beta$ 擴充成一組 $\mathbb{R}^n$ 的垂直標準基底 $\alpha = \beta\cup\gamma$。
說明 $[f_A]_\alpha^\alpha$ 可寫成
$$ \begin{bmatrix} A_1 & O \\ O & A_2 \end{bmatrix} $$的形式，其中 $A_1 = A/\pi$。
因此所有等量分割沒找出來的特徵值都落在 $A_2$ 裡。