# 柯西交錯定理

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
from sym import sym_from_list

## Main idea

##### Cauchy interlacing theorem

Let $A$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.
Let $B$ be an $(n-1)\times (n-1)$ principal submatrix of $A$ and $\mu_1 \leq \cdots \leq \mu_{n-1}$ its eigenvalues.
Then

$$
\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n.
$$

In general, if $B$ is an $k\times k$ principal submatrix of $A$ and $\mu_1 \leq \cdots \leq \mu_k$ its eigenvalues, then

$$
\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}
$$

for any $i = 1, \ldots, k$.

If two sets of real numbers $\lambda_1 \leq \cdots \leq \lambda_n$ and $\mu_1 \leq \cdots \leq \mu_k$ satisfies $\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}$ for all $i = 1, \ldots, k$,
then we say they have the **interlacing property**.

## Side stories

- Poincaré separation theorem
- eigenvector-eigenvalue identity revisited

## Experiments

##### Exercise 1

執行以下程式碼。

### code
set_random_seed(0)
print_ans = False

n = 3
entries = random_int_list(binomial(n+1,2))
A = sym_from_list(n, entries)
B = A[1:,1:]
eigs_A = A.eigenvalues()
eigs_A.sort()

print("n =", n)
pretty_print(LatexExpr("A ="), A)
print("eigenvalues of A from small to large:", eigs_A)
pretty_print(LatexExpr("B ="), B)

if print_ans:
    eigs_B = B.eigenvalues()
    eigs_B.sort()
    print("eigenvalues of B from small to large:", eigs_B)

藉由 `seed = 11` 得到
$$A=\begin{bmatrix}
-5 & 3 & -2\\
3 & -1 & 0\\
-2 & 0 & -2
\end{bmatrix}.
$$

$$B=\begin{bmatrix}
-1 & 0\\
0 & -2
\end{bmatrix}.
$$

##### Exercise 1(a)

計算 $B$ 的特徵值 $\mu_1 \leq \cdots \leq \mu_{n-1}$。

:::warning

- [x] 中英數之間空格
- [x] 計算 $B$ 的特徵多項式
$$
p_B(x) = (-1 - x) (-2 - x)
$$
- [x] 標點
:::

$Ans:$
計算 $B$ 的特徵多項式
$$p_B(x)
= (-1 - x) (-2 - x)
$$
故 $B$ 的特徵值為 $\mu_1 = -2$ 與 $\mu_2 = -1$。

##### Exercise 1(b)

驗證是否 $\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$。

:::warning

- [x] 中英數之間空格
- [x] 計算 $A$ 的特徵多項式
$$
p_A(x) = -x^3 - 8x^2 -4x +12
$$
- [x] 標點
:::

$Ans:$
計算 $A$ 的特徵多項式
$$p_A(x)
= -x^3 - 8x^2 -4x +12
$$
故 $A$ 的特徵值為 $\lambda_1 \simeq -7.2$ 、 $\lambda_2 \simeq -1.7$ 與 $\lambda_3 \simeq 0.95$。其滿足

$$
\begin{align}
& \lambda_1 && \leq \mu_1 && \leq \lambda_2 && \leq \mu_2 && \leq \lambda_3 \\
& -7.2 && \leq -2 && \leq -1.7 && \leq -1 && \leq 0.95
\end{align}
$$

## Exercises

##### Exercise 2

令 $A$ 為一 $n\times n$ 實對稱矩陣、$B$ 為其一 $(n-1)\times(n-1)$ 主子矩陣。
若 $\lambda$ 為 $A$ 的一特徵向量。
利用柯西交錯定理說明 $|\mult_A(\lambda) - \mult_B(\lambda)| \leq 1$。

這裡 $\mult_A(\lambda)$ 指的是 $\lambda$ 為 $A$ 的特徵向量的重數。

:::warning

- [x] 當 $\lambda$ 中有 $k$ 項為重根，則必有 $k-1$、$k$、或 $k+1$ 項 $\mu$ 亦為重根。
:::

$Ans:$
設 $A$ 的特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$，
設 $B$ 的特徵值為 $\mu_1 \leq \cdots \leq \mu_{n-1}$。
根據柯西交錯定理可知
$$
\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n.
$$
當 $\lambda$ 中有 $k$ 項為重根，則必有 $k-1$、$k$、或 $k+1$ 項 $\mu$ 亦為重根。
由此可知， $|\mult_A(\lambda) - \mult_B(\lambda)| \leq 1$。

##### Exercise 3

令 $A$ 為一 $n\times n$ 實對稱矩陣。
令 $Q$ 為一 $n\times n$ 實垂直矩陣、而 $S$ 為由 $Q$ 的前 $k$ 行所構成的 $n\times k$ 矩陣。
證明 $A$ 和 $B = S\trans AS$ 的特徵值具有交錯性質。

這個定理稱作**龐加萊分割定理（Poincaré separation theorem）**。

:::warning

- [ ] 標點
- [x] 中英數之間空格
- [x] $^T$ --> $\trans$
- [x] 所以
\begin{align}
\det(Q Q^T)
= \det(I)
= 1
\end{align}
因為
\begin{align}
\det(A - \lambda I)
= \det(Q^T A Q - \lambda Q^T Q)
\end{align} <-- 這段可以不用
:::

$Ans:$

方法一：
令一矩陣
$$
P = \begin{bmatrix} I_{k,k} & O_{k,n-k} \\
O_{n-k,k}&O_{n-k,n-k}
\end{bmatrix}.
$$
則
$$
QP= \begin{bmatrix}
Q_{n,k}& Q_{n,n-k} \\
\end{bmatrix}
\begin{bmatrix}
I_{k,k} & O_{k,n-k} \\
O_{n-k,k} & O_{n-k,n-k}
\end{bmatrix}
= \begin{bmatrix}
S_{n,k}& O_{n,n-k} \\
\end{bmatrix}
$$
且
$$
\begin{bmatrix}
S_{n,k}\trans \\
O_{n-k,n} \\
\end{bmatrix}
\begin{bmatrix}
A_{k,k} & A_{k,n-k} \\
A_{n-k,k} & A_{n-k,n-k}
\end{bmatrix}
\begin{bmatrix}
S_{n,k}& O_{n,n-k} \\
\end{bmatrix} \\
=\begin{bmatrix}
(S\trans\ AS)_{k,k} & O_{k,n-k} \\
O_{n-k,k} & O_{n-k,n-k}
\end{bmatrix}
=P\trans\ Q\trans\ AQP
$$
即 $B$ 為 $Q\trans\ AQ$ 的子矩陣，且 $Q\trans\ AQ$ 和 $A$ 相似。
故 $Q\trans\ AQ$ 和 $A$ 相似有相同的特徵值。
所以 $B$ 和 $A$ 的特徵值有交錯性質。

方法二：
令 $Q = \left[ S_{n \times k} | ? \right]$，故 $\displaystyle Q\trans = \left[ \frac{S_{k \times n}}{?} \right]$。
因
\begin{align}
Q\trans A Q
= \left[ \begin{array}{c|c}
S\trans A S & ? \\
\hline
? & ?
\end{array} \right]
\end{align}
故 $Q\trans A Q \simeq A$ 有相同的特徵值，因此 $B = S\trans A S$ 和 $A \simeq Q\trans A Q$ 有交錯性質。

##### Exercise 4

令 $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
證明對所有 $i = 1,\ldots,n$ 都有 $\lambda_1 \leq a_{ii} \leq \lambda_n$。

提示：對任意 $i$ 而言，$\begin{bmatrix} a_{ii} \end{bmatrix}$ 也是 $A$ 的一個 $1\times 1$ 主子矩陣。

:::warning

- [x] 當小矩陣大小是 $k\times k$ 時，交錯定理不是 $\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$，而是 $\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}$
:::

$Ans:$
對任意 $i$ 而言，$\begin{bmatrix} a_{ii} \end{bmatrix}$ 為 $A$ 的一個 $1\times 1$ 主子矩陣，且 $\begin{bmatrix} a_{ii} \end{bmatrix}$ 只有一個特徵值 $\mu_1 = a_{ii}$。
根據柯西交錯定理可知
$$
\lambda_1 \leq \mu_1 \leq \lambda_{n - (1 - 1)}.
$$

由此可知，對所有 $i = 1,\ldots,n$ 都有 $\lambda_1 \leq a_{ii} \leq \lambda_n$。

##### Exercise 5

令 $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
證明 $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$。

提示：取 $S$ 為 $n\times 1$ 的矩陣且其第一行為 $\frac{1}{\sqrt{n}}\bone$。

:::warning

- [ ] $S$ 不是方陣怎麼可以將 $A$ 對角化？
- [ ] 這題要用 Exercise 3
:::

$Ans:$
取 $S$ 為 $n\times 1$ 的矩陣且其每一行皆為 $\frac{1}{\sqrt{n}}\bone$ ，因為 $A$ 為對稱矩陣，所以我們可用可逆矩陣 $S$ 將 $A$ 矩陣對角化，得到由 $A$ 矩陣 $\frac{1}{n}$ 倍的特徵值所組成的矩陣 $D$。
$$
D = S\trans AS =
\begin{bmatrix}
\frac{1}{\sqrt{n}}\bone &
\cdots &
\frac{1}{\sqrt{n}}\bone \\
\end{bmatrix}
\begin{bmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots \\
a_{n1} & \cdots & a_{nn} \\
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{n}}\bone \\
\vdots \\
\frac{1}{\sqrt{n}}\bone \\
\end{bmatrix} = \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij}
$$
我們有 $D = \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} = \frac{1}{n} (\lambda_1 + \cdots + \lambda_n)$ ，又有 $\lambda_1 \leq \cdots \leq \lambda_n$ ，
因此可以推得 $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$。

##### Exercise 6

令 $A$ 為一 $n\times n$ 實對稱矩陣，且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$，而 $\bv_1,\ldots,\bv_n$ 為其對應的垂直標準特徵基底。
令 $B$ 為 $A$ 的一個 $k\times k$ 主子矩陣，而其特徵值為 $\mu_1 \leq \cdots \leq \mu_k$而 $\bu_1,\ldots,\bu_{k}$ 為其對應的垂直標準特徵基底。
我們可以假設 $B$ 取的是 $A$ 的最後 $k$ 個行和最後 $k$ 個列。
令

$$
P = \begin{bmatrix} O_{k,n-k} & I_k \end{bmatrix}.
$$

則 $B$ 也可以寫成 $B = PAP\trans$。

固定一個 $i$，依照以下步驟證明柯西交錯定理 $\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}$。

##### Exercise 6(a)

令 $V = \vspan\{\bv_1, \ldots, \bv_{i-1}\} \subseteq \mathbb{R}^n$，
說明 $PV = \{P\bv: \bv\in V\}$ 的維度至多是 $i-1$。
因此 $(PV)^\perp$ 的維度至少是 $k - i + 1$。

:::warning
綜合你的論述，重點在於 $PV = \vspan\{P\bv_1,\ldots,P\bv_{i-1}\}$。因為這個空間可以被 $i-1$ 個向量生成，所以維度一定至多 $i-1$。
:::

Ans:
已知 $0 = a_1P\bv_1 + a_2P\bv_2 + \cdots + a_{i-1}P\bv_{i-1}$
若 $\{P \bv_1, \ldots, P\bv_{i-1}\}$ 為線性獨立，則
$$
a_1=a_2=, \ldots,=a_{i-1}=0
$$
此時 $PV = \vspan\{P\bv_1, \ldots, P\bv_{i-1}\}$ 維度為 $i-1$。
若 $\{P\bv_1, \ldots, P\bv_{i-1}\}$ 為線性相依。
則可以找到一個集合使 $\{P v_1, \ldots, Pv_{(i-1)-t}\}$ 為線性獨立
(把能被取代的向量從後面放)。
且 $PV = \vspan\{Pv_1, \ldots, \ Pv_{(i-1)-t} \}$ 則維度為 $i-1-t < i-1$。
因此 $(PV)^\perp$ 的維度至少是 $k - i + 1$。

##### Exercise 6(b)

令 $W = \vspan\{\bu_1, \ldots, \bu_{i}\} \subseteq \mathbb{R}^k$。
說明 $W\cap (PV)^\perp$ 必存在非零向量。

:::warning

- [x] $dim$ --> $\dim$
:::

$Ans:$若 $W\cap (PV)^\perp$ 只有零向量，則 $W$ 和 $(PV)^\perp$ 獨立。
且因為 $W \subseteq \mathbb{R}^k$ 和 $(PV)^\perp \subseteq \mathbb{R}^k$ 則有 $W + (PV)^\perp \subseteq \mathbb{R}^k$ 。
故
$$
\begin{aligned}
\dim(W + (PV)^\perp) &= \dim(W)+\dim((PV)^\perp) \\
& \geq i + k -i + 1 \\
& =k+1 > k =\dim(\mathbb{R}^k).
\end{aligned}
$$
矛盾。
即 $W\cap (PV)^\perp$ 必存在非零向量。

##### Exercise 6(c)

任取一非零向量 $\bw\in W\cap (PV)^\perp$，
並令 $\bv$ 為在 $\bw$ 前面補 $n-k$ 個零的向量
（因此 $P\bv = \bw$）。
說明

:::warning

- [x] 若 $A_{nn}=I$ --> 取 $A_{kk} = I$ 時，則有
:::

$$
\lambda_i \leq R_A(\bv) = \frac{\bw\trans B\bw}{\bw\trans\bw} \leq \mu_i.
$$

（之後只要把 $A$ 取代成 $-A$ 就可以證明另一側的不等式 $\mu_i \leq \lambda_{n - (k - i)}$。）
$Ans:$令$(\bx=a_1\bv_1+...+a_{i-1}\bv_{i-1})$
$$
\begin{align}
\bw\trans\ P\bx & =0\ \\
&=(P\bv)\trans\ P\trans\ P\bx \\
&=\bv\trans\ P\trans\ P\bx \\
&=\bv\trans\bx
\end{align}
$$
故 $\bv$ 為 $\{ \bv_i, \ldots, \bv_n\}$ 的線性組合。
則
$$
\lambda_i =\frac{\bv_i\trans A\bv_i}{\bv\trans\bv}\leq \frac{\bv\trans A\bv}{\bv\trans\bv} = \frac{\bw\trans B\bw}{\bw\trans\bw} \leq \frac{\bu_i\trans B\bu_i}{\bu_i\trans\bu_i} \ =\mu_i.
$$

**Claim a**: 兩非零向量正交它們彼此一定獨立。
$proof:$
設 $\bv$ 和 $\bu$ 正交。
若 $\bv$ 和 $\bu$ 線性相依，則 $\bv$ = $a\bu$。
$\bv\trans\bu=0=a\bu\trans\bu=a$ 矛盾。
故兩向量正交它們彼此一定獨立。

**Claim b**: $\bv\trans A\bv = \bw\trans B\bw$
$proof:$
$$
\bv = \begin{bmatrix}
0 \\
\vdots \\
0 \\
w_{1} \\
\vdots \\
w_{i}
\end{bmatrix}
\text{ and }
\bw = \begin{bmatrix}
w_{1} \\
\vdots \\
w_{i}
\end{bmatrix}
$$

$$
\begin{align}
\bv\trans\ A \bv & =
\begin{bmatrix}
0& \cdots & 0 & w_{1} & \cdots & w_{i} \\
\end{bmatrix}
\begin{bmatrix}
A_{(n-k)(n-k)} & A_{(n-k)k} \\
A_{k(n-k)} & A_{kk}
\end{bmatrix}
\begin{bmatrix}
0 \\
\vdots \\
0 \\
w_{1} \\
\vdots \\
w_{i}
\end{bmatrix} \\
& = \begin{bmatrix}
0& \cdots & 0 & w_{1} & \cdots & w_{i} \\
\end{bmatrix}
\begin{bmatrix}
O_{(n-k)(n-k)} & A_{(n-k)k}\bw \\
O_{k(n-k)} & A_{kk}\bw
\end{bmatrix}\\
&=
\begin{bmatrix}
O_{(n-k)(n-k)} & O_{(n-k)k} \\
O_{k(n-k)} & \bw\trans\ A_{kk}\bw
\end{bmatrix}\\
&=\bw\trans\ A_{kk} \bw\\
&=\bw\trans\ B \bw
\end{align}
$$
取 $A_{kk} = I$ 時，則有
$\bv\trans\bv=\bw\trans\bw$ 。

##### Exercise 7

回顧 604-7 提到的特徵向量-特徵值等式。

##### Eigenvector-eigenvalue identity

若 $A$ 為一 $n\times n$ 實對稱矩陣。
其特徵值為 $\lambda_1,\ldots,\lambda_n$ 且某一個 $\lambda_i$ 只出現一次沒有重覆。
令 $\bv_1,\ldots, \bv_n$ 為其相對應的特徵向量，且其形成一垂直標準基。

$$
(A - \lambda_i I)\adj = \left(\prod_{j\neq i}(\lambda_j - \lambda_i)\right)\bv_i\bv_i\trans.
$$

說明儘管在 $\mult_A(\lambda_i) \geq 2$ 的時候，
左式和右式都會等於零矩陣，
因此該等式仍然成立。

:::warning

- [x] $N(A - \lambda_i I)\geq 2$ --> $\nul(A - \lambda_i I)\geq 2$
- [x] 說明為什麼 $\nul(A - \lambda_i I)\geq 2$ 可推得 $(A - \lambda_i I)\adj = O$
- [x] 標點
:::

$Ans:$
左式:
由於 $\mult_A(\lambda_i)\geq 2$。
$\nul(A - \lambda_i I) \geq 2$。
設 $\bv_i$ 為 $(A - \lambda_i I)$ 的列向量。
由任意性假設 $\bv_{n-1}= b_1\bv_1+\cdots\ +\ b_{n-2}\bv_{n-2}$。
且$\bv_{n}= a_1\bv_1+\cdots\ +\ a_{n-2}\bv_{n-2}$。
再由任意性去掉 $\bv_{n-2}$ ，則可透過高斯消去使 $n-1$ 列為 $\ b_{n-2}\bv_{n-2}$。
再用高斯消去使 $n$ 列為零向量。
若是去掉 $\bv_n$ 則可直接用高斯消去使 $n-1$ 列為零向量。
由於每行彼此獨立，故去掉一行不影響最終會有一列為零向量的結果。
故 $(A - \lambda_i I)\adj = O$

右式:
因為 $\mult_A(\lambda_i) \geq 2$ 故存在一個 $\lambda_k$ 使
$\lambda_i=\lambda_k$。
則
$$
\left(\prod_{j\neq i}(\lambda_j -\lambda_i)\right)\bv_i\bv_i\trans=
\left(\prod_{j\neq i\\j\neq k}\ (\lambda_j -\lambda_i)\right)\ (\lambda_k -\lambda_i)\bv_i\bv_i\trans=O
$$

:::info
分數 = 6.5
:::