# 柯西交錯定理

Cauchy interlacing theorem

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

執行以下程式碼。

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

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

##### Exercise 1(a)

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

<!-- eng start -->
Find the eigenvalues $\mu_1 \leq \cdots \leq \mu_{n-1}$ of $B$.
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
Verify that $\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$.
<!-- eng end -->

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

...
:::

## 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$ 的特徵向量的重數。

<!-- eng start -->
Let $A$ be an $n\times n$ real symmetric matrix, $B$ an $(n-1)\times(n-1)$ principal submatrix of $A$. Suppose $\lambda$ is an eigenvalue of $A$. Use the Cauchy interlacing theorem to show that $|\mult_A(\lambda) - \mult_B(\lambda)| \leq 1$.

Here $\mult_A(\lambda)$ is the multiplicity of $\lambda$ as an eigenvalue of $A$.
<!-- eng end -->

##### Exercise 3

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

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

<!-- eng start -->
Let $A$ be an $n\times n$ real symmetric matrix. Let $Q$ be an $n\times n$ real orthogonal matrix and $S$ the $n\times k$ matrix whose columns are the first $k$ columns of $Q$. Show that the spectrum of $B = S\trans AS$ interlace the spectrum of $A$.

This theorem is known as the **Poincaré separation theorem** .
<!-- eng end -->

##### 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$ 主子矩陣。

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$. Show that $\lambda_1 \leq a_{ii} \leq \lambda_n$ for all $i = 1,\ldots,n$.

Hint: For each $i$, the matrix $\begin{bmatrix} a_{ii} \end{bmatrix}$ is a $1\times 1$ principal submatrix of $A$.
<!-- eng end -->

##### 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$。並套用龐加萊分割定理。

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$. Show that $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$.

Hint: Let $S$ be the $n\times 1$ matrix whose first column is $\frac{1}{\sqrt{n}}\bone$. Then apply the Poincaré separation theorem with $S$.
<!-- eng end -->

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

<!-- eng start -->
Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$ and $\bv_1,\ldots,\bv_n$ the corresponding orthonormal eigenbasis. Let $B$ be a $k\times k$ principal submatrix of $A$ with eigenvalues $\mu_1 \leq \cdots \leq \mu_k$ and $\bu_1,\ldots,\bu_{k}$ the corresponding orthonormal eigenbasis. We may assume that $B$ is the submatrix of $A$ indueced from the last $k$ rows and columns. Let

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

Then $B$ can be written as $B = PAP\trans$.

Fix $i$. Then use the given instruction to prove the Cauchy interlacing theorem $\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}$.
<!-- eng end -->

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

<!-- eng start -->
Let $V = \vspan\{\bv_1, \ldots, \bv_{i-1}\} \subseteq \mathbb{R}^n$. Show that the dimension of $PV = \{P\bv: \bv\in V\}$ is at most $i - 1$. Therefore, the dimension of $(PV)^\perp$ is at most $k - i + 1$.
<!-- eng end -->

##### Exercise 6(b)

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

<!-- eng start -->
Let $W = \vspan\{\bu_1, \ldots, \bu_{i}\} \subseteq \mathbb{R}^k$. Show that $W\cap (PV)^\perp$ contains a nonzero vector.
<!-- eng end -->

##### Exercise 6(c)

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

$$
\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)}$。）

<!-- eng start -->
Pick a nonzero vector $\bw\in W\cap (PV)^\perp$ and let $\bv$ be the vector obtained from $\bw$ by padding $n-k$ zeros in the fron. (Thus, $P\bv = \bw$.) Show that

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

(Then one may replace $A$ by $-A$ to get the other inequality $\mu_i \leq \lambda_{n - (k - i)}$.)
<!-- eng end -->

##### 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$ 的時候，
左式和右式都會等於零矩陣，
因此該等式仍然成立。

<!-- eng start -->
Recall the eigenvector-eigenvalue identity introduced in 604-7.

##### Eigenvector-eigenvalue identity

Let $A$ be an $n\times n$ real symmetric matrix such that $\lambda_1,\ldots,\lambda_n$ are its eigenvalues and $\lambda_i$ is a simple eigenvalue. Let $\bv_1,\ldots, \bv_n$ be the corresponding eigenvectors, which form an orthogonal basis. Then

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

Show that the both sides are zero matrices when $\mult_A(\lambda_i) \geq 2$. Therefore, the identity is still true in this case.
<!-- eng end -->