This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
Cauchy interlacing theorem
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
from sym import sym_from_list
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
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.
執行以下程式碼。
Run the code below.### 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)
計算 $B$ 的特徵值 $\mu_1 \leq \cdots \leq \mu_{n-1}$。
Find the eigenvalues $\mu_1 \leq \cdots \leq \mu_{n-1}$ of $B$.驗證是否 $\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$。
Verify that $\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$.令 $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$ 的特徵向量的重數。
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$.令 $A$ 為一 $n\times n$ 實對稱矩陣。
令 $Q$ 為一 $n\times n$ 實垂直矩陣、而 $S$ 為由 $Q$ 的前 $k$ 行所構成的 $n\times k$ 矩陣。
證明 $A$ 和 $B = S\trans AS$ 的特徵值具有交錯性質。
這個定理稱作龐加萊分割定理（Poincaré separation theorem）。
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** .令 $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$ 主子矩陣。
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$.令 $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$。並套用龐加萊分割定理。
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$.令 $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$ 個列。
令
則 $B$ 也可以寫成 $B = PAP\trans$。
固定一個 $i$，依照以下步驟證明柯西交錯定理 $\lambda_i \leq \mu_i \leq \lambda_{n - (k - i)}$。
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)}$.令 $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$。
令 $W = \vspan\{\bu_1, \ldots, \bu_{i}\} \subseteq \mathbb{R}^k$。
說明 $W\cap (PV)^\perp$ 必存在非零向量。
任取一非零向量 $\bw\in W\cap (PV)^\perp$，
並令 $\bv$ 為在 $\bw$ 前面補 $n-k$ 個零的向量
（因此 $P\bv = \bw$）。
說明
（之後只要把 $A$ 取代成 $-A$ 就可以證明另一側的不等式 $\mu_i \leq \lambda_{n - (k - i)}$。）
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)}$.)回顧 604-7 提到的特徵向量-特徵值等式。
若 $A$ 為一 $n\times n$ 實對稱矩陣。
其特徵值為 $\lambda_1,\ldots,\lambda_n$ 且某一個 $\lambda_i$ 只出現一次沒有重覆。
令 $\bv_1,\ldots, \bv_n$ 為其相對應的特徵向量，且其形成一垂直標準基。
說明儘管在 $\mult_A(\lambda_i) \geq 2$ 的時候，
左式和右式都會等於零矩陣，
因此該等式仍然成立。