特征值的重要定理：Courant-Fischer min-max theorem 极大极小定理

前言

Courant-Fischer min-max theorem 是特征值极为重要的一个性质。 但是国内的各种教材资料包括博客上都很少提及。 我自己在科研中曾经用到过。 近期又碰到了另一个精彩的结论 韦尔定理（Wely theorem），有一个应用极大极小定理的简洁美妙的证明。 因此， 这篇博文写一下这个不容忽视的定理。

极大极小定理

首先，本定理针对的是Hermitian 矩阵， 即共轭对称矩阵。 因为只有共轭对称矩阵的特征值是确定为实数值的， 其他矩阵很可能是复数值， 而复数值，也就不存在大小关系了。

Courant-Fisher min-max 定理

对于 n × n n \times n n×n的矩阵 A \mathbf{A} A, 有：

• λ k = min ⁡ dim ⁡ ( U ) = k        max ⁡ x ∈ U , ∥ x ∥ = 1 x H A x \lambda_{k}=\min\limits _{\operatorname{dim}(U)=k}\;\;\; \max \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x λk​=dim(U)=kmin​x∈U,∥x∥=1max​xHAx
• λ k = max ⁡ dim ⁡ ( U ) = n − k + 1        min ⁡ x ∈ U , ∥ x ∥ = 1 x H A x \lambda_{k}=\max\limits_{\operatorname{dim}(U)=n-k+1} \;\;\; \min \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x λk​=dim(U)=n−k+1max​x∈U,∥x∥=1min​xHAx

其中， λ i \lambda_i λi​ 是 第 k k k 小的特征值。

这个定理在两年前接触到的时候一头雾水， 数院的国奖哥以此帮我证明了一个式子的时候更是惊为天人。 核心原因是当时对子空间的概念的认知实在太过不足。 现在回头看虽然仍觉得非常困难，但还是稍微精进了一些。

这个证明， 我参考了维基百科上的证明， 以下是对百科上过程的翻译：

由于 A \mathbf{A} A是共轭对称矩阵， 所以根据共轭对称矩阵的特征分解的性质， 选定其特征向量 { u 1 , … , u n } \left\{u_{1}, \ldots, u_{n}\right\} {u1​,…,un​} 作为一组正交基。 子空间与基相关知识

即， 这就是 n n n维空间的 n n n 个基。

现在， 若有该 n n n维空间的一个子空间 U U U， 其维度为 k k k, 和子空间 s p a n ( u k , … , u n ) \mathrm{span}(u_k, \ldots, u_n) span(uk​,…,un​) (我们假设 u k , ⋯   , u n u_k, \cdots, u_n uk​,⋯,un​对应的特征值为升序排列)， 必定存在一个交集。 这一点其实可以这样证明： 首先 U U U的维度是 k k k, 而 s p a n ( u k , … , u n ) \mathrm{span}(u_k, \ldots, u_n) span(uk​,…,un​)的维度是 n − k + 1 n-k+1 n−k+1。 也就是说， 两者的维度之和 大于 n n n。因此， 必定存在一个非零的交集。（这一点其实可以这样判断： 如果维度之和刚好是 n n n， 那可能两个子空间刚好由一组正交基的两部分扩展二成，是没有交集的。但和为 n + 1 n+1 n+1，如果没有交集，就说明这个空间其实应该有 n + 1 n+1 n+1个正交基， 这是违背的。没有想明白的读者， 可以根据3维空间来想像： 3维空间的两个二维子空间，必有交集。 而3维空间的1个二维子空间和1个一维子空间，是可以没有交集的。）

因此， 假设 v v v 是交集上的一个元素， 即， 既属于子空间 U U U 又属于 子空间 s p a n ( u k , … , u n ) \mathrm{span}(u_k, \ldots, u_n) span(uk​,…,un​)。 那么， x ∈ s p a n ( u k , … , u n ) x\in\mathrm{span}(u_k, \ldots, u_n) x∈span(uk​,…,un​), 因此有：

x = ∑ i = k n α i u i x=\sum_{i=k}^{n} \alpha_{i} u_{i} x=i=k∑n​αi​ui​ (由于 ∣ ∣ x ∣ ∣ = 1 ||x||=1 ∣∣x∣∣=1, 有 ∑ i = k n α i = 1 \sum_{i=k}^{n} \alpha_{i}=1 ∑i=kn​αi​=1) 那么，

x H A x = ∑ i = k n α i 2 u i H A u i = ∑ i = k n λ i α i 2 ≥ λ k x^H\mathbf{A}x=\sum_{i=k}^{n}\alpha_{i}^2u_i^H\mathbf{A}u_i=\sum_{i=k}^{n} \lambda_{i} \alpha_{i}^{2}\ge \lambda_k xHAx=i=k∑n​αi2​uiH​Aui​=i=k∑n​λi​αi2​≥λk​ 不等号来源于我们认为 λ i ≥ λ k , ∀ i > k \lambda_i\ge \lambda_k, \forall i>k λi​≥λk​,∀i>k 即:

  max ⁡ x ∈ U , ∥ x ∥ = 1 x H A x ≥ λ i \ \max \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x\ge \lambda_i  x∈U,∥x∥=1max​xHAx≥λi​

对于所有子空间 U U U都成立。 即：

min ⁡ dim ⁡ ( U ) = k        max ⁡ x ∈ U , ∥ x ∥ = 1 x H A x ≥ λ k \min\limits _{\operatorname{dim}(U)=k}\;\;\; \max \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x\ge \lambda_k dim(U)=kmin​x∈U,∥x∥=1max​xHAx≥λk​

这时候，我们再证另一半：

显然， 空间 V = span ⁡ { u 1 , … , u k } V=\operatorname{span}\left\{u_{1}, \ldots, u_{k}\right\} V=span{u1​,…,uk​} 作为选择的 k k k维空间， 有：

x H A x ≤ λ k x^H\mathbf{A}x\le \lambda_k xHAx≤λk​

这个结论过于明显，不做解释了。 也就是说，   max ⁡ x ∈ V , ∥ x ∥ = 1 x H A x ≤ λ k \ \max \limits_{x \in V,\|x\|=1} x^{H} \mathbf{A} x\le \lambda_k  x∈V,∥x∥=1max​xHAx≤λk​, 而 V V V 显然是 k k k维的子空间 U U U之一， 因此：

min ⁡ dim ⁡ ( U ) = k        max ⁡ x ∈ U , ∥ x ∥ = 1 x H A x ≤ λ k \min\limits _{\operatorname{dim}(U)=k}\;\;\; \max \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x\le \lambda_k dim(U)=kmin​x∈U,∥x∥=1max​xHAx≤λk​

所以有：

min ⁡ dim ⁡ ( U ) = k        max ⁡ x ∈ U , ∥ x ∥ = 1 x H A x = λ k \min\limits _{\operatorname{dim}(U)=k}\;\;\; \max \limits_{x \in U,\|x\|=1} x^{H} \mathbf{A} x= \lambda_k dim(U)=kmin​x∈U,∥x∥=1max​xHAx=λk​

证毕。

经典应用： 韦尔定理 Wely theorem

对于两个 n × n n \times n n×n 的共轭对称矩阵 A \mathbf{A} A 和 B \mathbf{B} B， 有：

λ i ( A ) + λ 1 ( B ) ≤ λ i ( A + B ) ≤ λ i ( A ) + λ n ( B ) \lambda_{i}(A)+\lambda_{1}(B) \leq \lambda_{i}(A+B) \leq \lambda_{i}(A)+\lambda_{n}(B) λi​(A)+λ1​(B)≤λi​(A+B)≤λi​(A)+λn​(B)。

显然，这是一个极为有用的定理。

先说下他的证明：

λ i ( A + B ) = max ⁡ dim ⁡ ( V ) = i min ⁡ x ∈ V , ∥ x ∥ = 1 x H ( A + B ) x = max ⁡ dim ⁡ ( V ) = i min ⁡ x ∈ V , ∥ x ∥ = 1 ( x H A x + x H B x ) ≥ max ⁡ dim ⁡ ( V ) = i ( min ⁡ x ∈ V , ∥ x ∥ = 1 x H A x + min ⁡ x ∈ V , ∥ x ∥ = 1 x H B x ) ≥ max ⁡ dim ⁡ ( V ) = i min ⁡ x ∈ V , ∥ x ∥ = 1 x H A x + min ⁡ x ∈ V , ∥ x ∥ = 1 x H B x = max ⁡ dim ⁡ ( V ) = i min ⁡ x ∈ V , ∥ x ∥ = 1 x H A x + λ 1 ( B ) = λ i ( A ) + λ 1 ( B ) \begin{aligned} \lambda_{i}(A+B)=& \max _{\operatorname{dim}(V)=i} \min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1} \boldsymbol{x}^{H}(A+B) \boldsymbol{x} \\ &=\max _{\operatorname{dim}(V)=i} \min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1}\left(\boldsymbol{x}^{H} A \boldsymbol{x}+\boldsymbol{x}^{H} B \boldsymbol{x}\right) \\ &\ge \max _{\operatorname{dim}(V)=i} \left(\min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1}\boldsymbol{x}^{H} A \boldsymbol{x}+\min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1}\boldsymbol{x}^{H} B \boldsymbol{x}\right) \\ & \geq \max _{\operatorname{dim}(V)=i} \min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1} \boldsymbol{x}^{H} A \boldsymbol{x}+\min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1} \boldsymbol{x}^{H} \boldsymbol{B} \boldsymbol{x} \\ &=\max _{\operatorname{dim}(V)=i} \min _{\boldsymbol{x} \in V,\|\boldsymbol{x}\|=1} \boldsymbol{x}^{H} A \boldsymbol{x}+\lambda_{\boldsymbol{1}}(B)=\lambda_{i}(A)+\lambda_{\boldsymbol{1}}(B) \end{aligned} λi​(A+B)=​dim(V)=imax​x∈V,∥x∥=1min​xH(A+B)x=dim(V)=imax​x∈V,∥x∥=1min​(xHAx+xHBx)≥dim(V)=imax​(x∈V,∥x∥=1min​xHAx+x∈V,∥x∥=1min​xHBx)≥dim(V)=imax​x∈V,∥x∥=1min​xHAx+x∈V,∥x∥=1min​xHBx=dim(V)=imax​x∈V,∥x∥=1min​xHAx+λ1​(B)=λi​(A)+λ1​(B)​

非常简洁。

这个定理可以推出一些有用的结论：

• 可以确定两个共轭对称矩阵和 的 特征值的 范围。
• 一个共轭对称矩阵 加上一个正定共轭对称矩阵， 特征值必增大。