Courant-Fischer Theorem

1 定理 #

若\(M\)是实对称矩阵，特征值为 \(\mu_1 \geq \ldots \geq \mu_n\) ，特征向量为 \(v_1, \ldots, v_n\) ，则第\(k\)大的特征值是如下优化问题的答案： 在 \(\mathbb{R}^n\) 的所有 k 维子空间 \(S\) 中，如果在 S 中找到了最小的瑞利商，哪个 S 使得这个最小瑞利商最大？ 具体的公式表达为： \[ \mu_k = \max_{\substack{\text{subspace }S\subseteq \mathbb{R}^n \\ \text{dim} S=k}} \min_{\substack{x\in S \\ x\neq 0}} \frac{x^T Mx}{x^T x} = \min_{\substack{\text{subspace } S\subseteq \mathbb{R}^n \\ \text{dim} S=n-k+1}} \max_{\substack{x\in S \\ x\neq 0}} \frac{x^T Mx}{x^T x} \]

2 证明 #

证明：

这里只证明第一个“max min”，后一个类似。

令\(V=\text{span }\{v_1, \dots , v_k\}\)，则对任意\(\vec{x} \in V\)有\(\vec{x}^T \vec{x} = \sum_{i=1}^k c_i^2\)，且： \[ \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}} = \frac{\sum_{i=1}^{k} c_i^2 \mu_i}{\vec{x}^T \vec{x}} \geq \frac{\mu_k\sum_{i=1}^{k} c_i^2}{\vec{x}^T \vec{x}} = \mu_k\] 由\(\vec{x}\)的任意性，可以取最小值，不等号仍成立： \[\min_{\substack{\vec{x} \in V\\ \vec{x}\neq \vec{0}}}\frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\geq \mu_k\] 在任意的 k 维空间中，对式子左边取最大值，左边也只会更大，即不等号仍成立： \[\max_{\substack{\text{subspace } S \subseteq \RR^n\\ \text{dim } S=k}} \min_{\substack{\vec{x} \in S\\ \vec{x}\neq \vec{0}}}\frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\geq \mu_k\] 下面继续证明另一个方向的不等关系：

令\(S\)为任意 k 维空间，它一定与\(\text{span }\{v_k, \dots , v_n\}\)（n-k+1 维）相交，即存在一个向量\(\vec{x} \in S\)，可以表示成： \[\vec{x} = \sum_{i=k}^n c_i \vec{v_i}\] 所以有： \[ \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}} = \frac{\sum_{i=k}^{n} c_i^2 \mu_i}{\vec{x}^T \vec{x}} \leq \frac{\mu_k\sum_{i=k}^{n} c_i^2}{\vec{x}^T \vec{x}} = \mu_k\] 对左边取最小值，左边只会更小，即不等号仍成立： \[\min_{\substack{\vec{x} \in S\\ \vec{x}\neq \vec{0}}}\frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\leq \mu_k\] 由于\(S\)的任意性，对左边取最大值，不等号仍成立： \[\max_{\substack{\text{subspace } S \subseteq \RR^n\\ \text{dim } S=k}} \min_{\substack{\vec{x} \in S\\ \vec{x}\neq \vec{0}}}\frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\leq \mu_k\]

综上，等号成立。

---