# 等量分割

Equitable partition

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

執行以下程式碼。

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

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

##### Exercise 1(a)

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

<!-- eng start -->
Find an equitable partition of $A$.
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
Find the quotient matrix and its spectrum.
<!-- eng end -->

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

...
:::

## Exercises

##### Exercise 2

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

<!-- eng start -->
Find the spectra of the following special matrices.
<!-- eng end -->

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

<!-- eng start -->
It is known that $0$ is an eigenvalue of

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

with multiplicity $3$. Use the equitable partition technique to find the remaining two eigenvalues.
<!-- eng end -->

##### Exercise 2(b)

求

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

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

<!-- eng start -->
Find the spectrum of

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

Here $O$ and $J$ are the zero matrix and the all-ones matrix of the corresponding sizes.
<!-- eng end -->

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

的所有特徵值。

<!-- eng start -->
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}.
$$
<!-- eng end -->

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

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

<!-- eng start -->
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.
<!-- eng end -->

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

<!-- eng start -->
For each of $A\phi_{X_1}$ and $A\phi_{X_2}$, write it as a linear combination of $\beta = \{\phi_{X_1}, \phi_{X_2}\}$. Let $V = \vspan(\beta)$. Then find $[f_A\big|_V]_\beta^\beta$.
<!-- eng end -->

##### Exercise 4(b)

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

<!-- eng start -->
Find $A/\pi$ and compare it with your result of the previous exercise.
<!-- eng end -->

##### Exercise 4(c)

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

<!-- eng start -->
Find the spectrum of $A/\pi$ and the corresponding eigenvectors.
<!-- eng end -->

##### Exercise 4(d)

若

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

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

<!-- eng start -->
Suppose

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

is an eigenvector of $A/\pi$ with respect to the eigenvalue $\lambda$. Verify that $a\phi_{X_1} + b\phi_{X_2}$ is an eigenvector of $A$ with respect to the same eigenvalue $\lambda$. Why?
<!-- eng end -->

##### Exercise 5

令

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

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

<!-- eng start -->
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.
<!-- eng end -->

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

<!-- eng start -->
Let $A$ be an $n\times n$ matrix and $\pi = (X_1,\ldots,X_k)$ an equitable partition of $A$. Let $\beta = \left\{\frac{1}{\|\phi_{X_1}\|}\phi_{X_1}, \ldots, \frac{1}{\|\phi_{X_k}\|}\phi_{X_k}\right\}$ be an orthonormal basis of $\vspan(\beta)$. Expand $\beta$ into an orthonormal basis $\alpha = \beta\cup\gamma$ of $\mathbb{R}^n$.

Show that $[f_A]_\alpha^\alpha$ can be written as the form

$$
\begin{bmatrix}
A_1 & O \\
O & A_2
\end{bmatrix},
$$

where $A_1 = A/\pi$. Therefore, the spectrum of $A_2$ is exactly the eigenvalues not in the quotient matrix.
<!-- eng end -->