# 等量分割

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

## Main idea

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.

- $(X_1, \ldots, X_k)$ is an equitable partition of $A$.
- $V = \vspan\{\phi_{X_1},\ldots,\phi_{X_k}\}$ is an $A$-invariant subspace.

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

## Side stories

- remaining eigenvalues

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = True

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)

##### Exercise 1(a)

找出一個 $A$ 的等量分割。

:::warning

- [x] for any --> such that for any
:::

**答 :**
當 `seed = 0` 時
$$
A = \begin{bmatrix}
0 & -1 & -1 & 2 & 2\\
-1 & 0 & -1 & 2 & 2\\
-1 & -1 & 0 & 2 & 2\\
2 & 2 & 2 & -1 & -1\\
2 & 2 & 2 & -1 & -1
\end{bmatrix}.
$$
Find a partition $\pi = (X_1,X_2)$ of $[5]$ such that for any $i,j\in [2]$, the submatrix $A[X_i, X_j]$ has a constant row sum $s_{ij}$.
We get $[X_1] = \{1,2,3\}$ and $[X_2] = \{4,5\}$

##### Exercise 1(b)

求出這個等量分割的商矩陣、及其所有特徵值。

:::warning

- [x] 標點
:::

**答 :**
根據觀察： $\nul(A) = 1$ ，且主對角線全部減掉 $1$ 後， $\nul(A-I) = 2$ ，故 $\spec(A) = \{0,1,1,?,?\}$ 。
根據觀察
The row sum of $A[X_1, X_1] = -2$，
The row sum of $A[X_1, X_2] = 4$，
The row sum of $A[X_2, X_1] = 6$，
The row sum of $A[X_2, X_2] = -2$，
可以得知商矩陣 $C = \begin{bmatrix}
-2 & 4 \\
6 & -2
\end{bmatrix}.$
找 $p_C(x) = \det(C-xI) = x^2+4x-20$ ， 若 $p_C(x) = 0$ ，即可得 $\spec(C) = \{-2+2\sqrt6,-2-2\sqrt6\}$
因為 $\spec(C)$ 都跟 $0,1$ 不同，可以知道 $\spec(A) = \{0,1,1\}\cup\spec(C)$
故 $\spec(A) = \{0,1,1,-2+2\sqrt6,-2-2\sqrt6\}$

:::info
一般來說沒辦法那麼確定 $\spec(A) = \{0,1,1\}\cup\spec(C)$；是因為後來找到的 $\spec(C)$ 都跟 $0,1$ 不同，所以知道這就是全部的特徵值。
:::

## Exercises

##### Exercise 2

求以下特定形態矩陣的特徵值。

##### Exercise 2(a)

已知

$$
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$。
利用等量分割的方法來找出最後兩個特徵值。

**Ans:**

令 $\pi = (X_1,X_2),\ X_1 = \{1,2\},X_2= \{3,4,5\}$ 為 $[5]$ 的分割。
同時對任意的 $i,j$ ， $A[X_i,X_j]$ 皆有固定的列和。
則 $\pi$ 為 $A$ 的等量分割。
則令 $C$ 為 $A$ 的商矩陣，且
$$
C = \begin{bmatrix}
0 & 3 \\
2 & 0
\end{bmatrix}.
$$
依據定理， $\spec(C)\subseteq\spec(A)$ 。
而 $\spec(C)=\{-\sqrt{6},\sqrt{6}\}$ ，且已知 $\spec(A)$ 共有 $5$ 個元素且其中三個為 $0$ 。
故 $\spec(A) = \{0,0,0,-\sqrt{6},\sqrt{6}\}$ 。

##### Exercise 2(b)

求

$$
A = \begin{bmatrix}
O_{m,m} & J_{m,n} \\
J_{n,m} & O_{n,n}
\end{bmatrix}
$$

的所有特徵值。
這裡 $O$ 和 $J$ 分別是相對應大小的全零和全一矩陣。

**Ans:**

首先觀察 $A$ 可以發現其實 $A$ 總共只有 $2$ 個不同的列。
換句話說 $\nul(A) = m+n-2$ ，即 $\spec(A)$ 中有 $m+n-2$ 個 $0$ 。
再用 $\pi = (X_1,X_2),\ X_1 = \{1,...,m\},X_2 = \{m+1,...,m+n\}$ 為 $[m+n]$ 的分割。
可發現 $\pi$ 會是 $A$ 的一個等量分割。
則可得到 $A$ 的商矩陣 $C$ ，
$$
C = \begin{bmatrix}
0 & n\\
m & 0
\end{bmatrix}.
$$
由於 $\spec(C)\subseteq\spec(A)$ 且 $\spec(C)=\{-\sqrt{mn},\sqrt{mn}\}$ 。
可知 $\spec(A)$ 中非零的兩個元素為 $\{-\sqrt{mn},\sqrt{mn}\}$ 。

##### Exercise 3

求

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

的所有特徵值。

**答 :**
根據觀察 $\nul(A) = 3$ ，故 $\spec(A) = \{0,0,0,?,?,?\}$ 。
我們對 $A$ 做等量分割, $\pi = (X_1,X_2,X_3)$ ，
其中 $X_1 = \{1,2\} , X_2 = \{3,4\} , X_3 = \{5,6\}$ 。
根據觀察
The row sum of $A[X_1, X_1] = 0.$
The row sum of $A[X_1, X_2] = 2.$
The row sum of $A[X_1, X_3] = 2.$
The row sum of $A[X_2, X_1] = 2.$
The row sum of $A[X_2, X_2] = 0.$
The row sum of $A[X_2, X_3] = 2.$
The row sum of $A[X_3, X_1] = 2.$
The row sum of $A[X_3, X_2] = 2.$
The row sum of $A[X_3, X_3] = 0.$
可以得知商矩陣 $C = \begin{bmatrix}
0 & 2 & 2 \\
2 & 0 & 2 \\
2 & 2 & 0
\end{bmatrix}$ ，
找 $p_C(x) = \det(C-xI) = -(x+2)^2(x-4)$ ，
若 $p_C(x) = 0$ ，即可得 $\spec(C) = \{-2,-2,4\}$ 。
因為 $\spec(C)$ 都跟 $0$ 不同，可以知道 $\spec(A) = \{0,0,0\}\cup\spec(C)$ ，
故 $\spec(A) = \{0,0,0,-2,-2,4\}$ 。

##### Exercise 4

令

$$
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$ 的一個等量分割。

以下練習說明可以利用商矩陣的特徵向量回推原矩陣的特徵向量。

##### Exercise 4(a)

將 $A\phi_{X_1}$ 和 $A\phi_{X_2}$ 分別寫成 $\beta = \{\phi_{X_1}, \phi_{X_2}\}$ 的線性組合。
令 $V = \vspan(\beta)$。
求出 $[f_A\big|_V]_\beta^\beta$。

***Ans:***
$A
\begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix} = \begin{bmatrix}
3 \\
-1 \\
-1 \\
-1
\end{bmatrix} = 3 \phi_{X_1} - \phi_{X_2}$ ，
$A
\begin{bmatrix}
0 \\
1 \\
1 \\
1
\end{bmatrix} = \begin{bmatrix}
-3 \\
1 \\
1 \\
1
\end{bmatrix} = -3 \phi_{X_1} + \phi_{X_2}$ 。
因此若將 $\begin{bmatrix}
1 \\
0
\end{bmatrix}$ 代入 $[f_A\big|_V]_\beta^\beta$ 會得 $\begin{bmatrix}
3 \\
-1
\end{bmatrix}$ ，
若將 $\begin{bmatrix}
0 \\
1
\end{bmatrix}$ 代入 $[f_A\big|_V]_\beta^\beta$ 會得 $\begin{bmatrix}
-3 \\
1
\end{bmatrix}$ ，
所以 $[f_A\big|_V]_\beta^\beta = \begin{bmatrix}
3 & -3 \\
-1 & 1
\end{bmatrix}$ 。

##### Exercise 4(b)

計算 $A/\pi$ 並和上一題的結果作比較。

***Ans:***
$A/\pi = \begin{bmatrix}
3 & -3 \\
-1 & 1
\end{bmatrix}$ ，
與上題結果相同。

##### Exercise 4(c)

計算 $A/\pi$ 的所有特徵值及特徵向量。

***Ans:***
$\det(\begin{bmatrix}
3 & -3 \\
-1 & 1
\end{bmatrix} - \lambda I) = \lambda ^2 - 4 \lambda = \lambda ( \lambda - 4)$ ，
因此 $\spec(A) = \{ 0 , 4 \}$ ，
其中 $\ker(\begin{bmatrix}
3 & -3 \\
-1 & 1
\end{bmatrix} - 0I) = \vspan(\begin{bmatrix}
1 \\
1
\end{bmatrix})$ ，
$\ker(\begin{bmatrix}
3 & -3 \\
-1 & 1
\end{bmatrix} - 4I) = \vspan(\begin{bmatrix}
3 \\
-1
\end{bmatrix})$ 。

##### Exercise 4(d)

若

$$
\bu = \begin{bmatrix} a \\ b \end{bmatrix}
$$

為 $A/\pi$ 的一特徵向量、且其特徵值為 $\lambda$。
驗證 $a\phi_{X_1} + b\phi_{X_2}$ 為 $A$ 的特徵向量、且其特徵值也是 $\lambda$。
說明為什麼。

***Ans:***
當 $\bu = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ 時，
則
$$
A (\phi_{X_1} + \phi_{X_2}) = A \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 0 \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}.
$$
當 $\bu = \begin{bmatrix} 3 \\ -1 \end{bmatrix}$ 時，
則
$$
A (3 \phi_{X_1} - \phi_{X_2}) = A \begin{bmatrix} 3 \\ -1 \\ -1 \\ -1 \end{bmatrix} = \begin{bmatrix} 12 \\ -4 \\ -4 \\ -4 \end{bmatrix} = 4 \begin{bmatrix} 3 \\ -1 \\ -1 \\ -1 \end{bmatrix}.
$$
可知，若 $\begin{bmatrix} a \\ b \end{bmatrix}$為 $A/\pi$ 的一特徵向量、且其特徵值為 $\lambda$ ，
則 $a\phi_{X_1} + b\phi_{X_2}$ 也是$A$ 的特徵向量、且其特徵值也是 $\lambda$ 。
因為 $A / \pi$ 即為 $[f_A\big|_V]_\beta^\beta$ ，
自然不會失去在 $V$ 上的特徵值與特徵向量。

:::info
根據矩陣表示法的性質，

$$
[f_A\big|_V]_\beta^\beta \begin{bmatrix} a \\ b \end{bmatrix} = \lambda \begin{bmatrix} a \\ b \end{bmatrix}
$$

等價於

$$
A(a\phi_{X_1} + b\phi_{X_2}) = \lambda (a\phi_{X_1} + b\phi_{X_2}).
$$
:::

##### Exercise 5

令
$$
A = \begin{bmatrix}
nI_m & -J_{m,n} \\
-J_{n,m} & mI_n
\end{bmatrix}.
$$

求 $A$ 的所有特徵值和特徵向量。

答：
我們對 $A$ 做等量分割, 可得 $\pi = (X_1,X_2)$ ，
$X_1 = \{1,2,3,...,m\}$ ， $X_2 = \{m+1,m+2,m+3,...,m+n\}$ 。

根據觀察可得
The row sum of $A[X_1, X_1] = n.$
The row sum of $A[X_1, X_2] = -m.$
The row sum of $A[X_2, X_1] = -n.$
The row sum of $A[X_2, X_2] = m.$
可得商矩陣
$C = \begin{bmatrix}
n & -n \\
-m & m \\
\end{bmatrix}$ ，
則 $\det(\begin{bmatrix}
n & -n \\
-m & m \\
\end{bmatrix} - \lambda I) =nm -(n+m)\lambda + \lambda^2 -nm = \lambda ( \lambda -n-m )$ ，
因此 $\spec(C) =\{0,m+n\}$ ，
因此 $\spec(A) = \{ 0,m+n, n ^ {(m-1)} , m ^ {(n-1)} \}$ 。
可得 $\ker(\begin{bmatrix}
n & -n \\
-m & m
\end{bmatrix} - 0I) = \vspan(\begin{bmatrix}
1 \\
1
\end{bmatrix})$ ，
所以
$$
\ker(A - 0I) = \phi_{X_1} + \phi_{X_2} = \vspan(\begin{bmatrix}
1 \\
1 \\
\vdots \\
1
\end{bmatrix}).
$$
同時
$$\ker(\begin{bmatrix}
n & -n \\
-m & m
\end{bmatrix} - (m+n)I) =
\ker(\begin{bmatrix}
-m & -n \\
-m & -n
\end{bmatrix}) = \vspan(\begin{bmatrix}
n \\
-m
\end{bmatrix}) ，
$$
所以
$$
\ker(A - (n+m)I) = n\phi_{X_1} - m\phi_{X_2} = \vspan (\begin{bmatrix}
n \\
\vdots \\
n \\
-m \\
\vdots \\
-m
\end{bmatrix}).
$$
另外
$$
\ker(A - nI) = \vspan (\begin{bmatrix}
1 \\
-1 \\
0 \\
0 \\
\vdots \\
0 \\
\vdots \\
0
\end{bmatrix},\begin{bmatrix}
1 \\
0 \\
-1 \\
0 \\
\vdots \\
0 \\
\vdots \\
0
\end{bmatrix}, \dots ,
\begin{bmatrix}
1 \\
0 \\
\vdots \\
0 \\
-1 \\
0 \\
\vdots \\
0
\end{bmatrix}).
$$
且
$$
\ker(A - mI) = \vspan (\begin{bmatrix}
0 \\
\vdots \\
0 \\
1 \\
-1 \\
0 \\
0 \\
\vdots \\
0
\end{bmatrix},\begin{bmatrix}
0 \\
\vdots \\
0 \\
1 \\
0 \\
-1 \\
0 \\
\vdots \\
0
\end{bmatrix}, \dots ,
\begin{bmatrix}
0 \\
\vdots \\
0 \\
1 \\
0 \\
0 \\
\vdots \\
0 \\
-1
\end{bmatrix}).
$$

:::success
Beautiful!
:::

##### Exercise 6

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

:::warning
題目有錯，$A$ 必須要**對稱**。
暫時忽略這題。
:::

\
ANS:
\
從題目敘述中得到 $\vspan(\beta)$ $\cong$ $\vspan(\pi)$ $\cong$ $\mathbb{R}^k$，且 $\vspan(\alpha)$ $\cong$ $\mathbb{R}^n$，其中 $k \leq n$。

\
因為 $\alpha$ 跟 $\beta$ 分別是 $\mathbb{R}^k$ 跟 $\mathbb{R}^n$ 的垂直標準基底，故 $A/\pi$ $\cong$ $A/\beta$ $\cong$ $\mathbb{R}^{n-k}$，
\
且 $\gamma$ 必為 $\mathbb{R}^{n-k}$ 的垂直標準基底。
\
因此 $[f_A]_\alpha^\alpha$ 可寫成
$$
\begin{bmatrix}
A_1 & O \\
O & A_2
\end{bmatrix}
$$
\
且 $A_2$ 必能得到 $(n-k)$ 個特徵值。

:::info
分數 = 6.5
:::