矩阵扰动与 Eigenvalue Interlacing

前面一章讨论 Woodbury formula、RLS 和 Kalman filter 时，核心思想是：

$$\boxed{ \text{旧矩阵} + \text{低秩新信息} \quad \Longrightarrow \quad \text{不从头重算，而是快速更新} }$$

那一章主要关心的是 inverse 和 least squares solution 怎么更新。这一章换一个角度：如果矩阵发生扰动，矩阵的逆会怎样变？特征值又会怎样变？

这两个问题看起来不一样，但它们背后都有同一个主线：

$$\boxed{ \text{扰动的 rank 和大小} \quad \Longrightarrow \quad \text{控制更新后对象能变化多少} }$$

其中 rank 控制的是变化影响多少个方向，而扰动的 magnitude 控制的是这些方向上能变多大。

逆矩阵的差分恒等式

先从逆矩阵开始。

设 $\mathbf{A}$ 和 $\mathbf{B}$ 都是可逆矩阵。我们想比较

$$\mathbf{A}^{-1} \quad \text{和} \quad \mathbf{B}^{-1}$$

也就是想知道矩阵从 $\mathbf{A}$ 变成 $\mathbf{B}$ 以后，逆矩阵发生了什么变化。

一个非常有用的恒等式是

$$\boxed{ \mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1} }$$

它的推导很直接：

$$\begin{align*} \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1} &= \mathbf{B}^{-1}\mathbf{A}\mathbf{A}^{-1} - \mathbf{B}^{-1}\mathbf{B}\mathbf{A}^{-1} \\ &= \mathbf{B}^{-1} - \mathbf{A}^{-1} \end{align*}$$

这个式子重要的地方不仅仅是能算出差值，它把 逆矩阵 的变化和 原矩阵 的变化联系起来：

$$\boxed{ \text{逆矩阵的变化} = \text{可逆矩阵} \times \text{原矩阵的变化} \times \text{可逆矩阵} }$$

也就是说，真正决定 $\mathbf{B}^{-1}-\mathbf{A}^{-1}$ 结构的是中间的

$$\mathbf{A}-\mathbf{B}$$

左右两边的 $\mathbf{B}^{-1}$ 和 $\mathbf{A}^{-1}$ 只是把这个变化换了坐标。

低秩扰动会传递到逆矩阵

因为左右乘可逆矩阵不会改变 rank，所以有

$$\boxed{ \text{rank}(\mathbf{B}^{-1}-\mathbf{A}^{-1}) = \text{rank}(\mathbf{A}-\mathbf{B}) }$$

更准确地说，如果 $\mathbf{A}$ 和 $\mathbf{B}$ 都可逆，那么

$$\text{rank} \left( \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1} \right) = \text{rank}(\mathbf{A}-\mathbf{B})$$

原因是：可逆矩阵只是在 domain 和 range 中做一一对应的线性变换，不会把一个非零方向压扁成零方向，也不会凭空增加新的独立方向。

所以如果

$$\mathbf{B} = \mathbf{A} + \mathbf{u}\mathbf{v}^\top$$

那么

$$\mathbf{B}-\mathbf{A} = \mathbf{u}\mathbf{v}^\top$$

是 rank-one update，于是

$$\mathbf{B}^{-1}-\mathbf{A}^{-1}$$

也仍然是 rank-one 的变化。

这正好解释了为什么上一章里 Sherman-Morrison formula 会成立。一个大矩阵被 rank-one 改了一下，它的逆矩阵不需要完全重新构造；逆矩阵本身也只是发生了一个 rank-one 形式的修正。

因此可以把上一章的结论放进这里：

$$\boxed{ \text{原矩阵低秩变化} \quad \Longrightarrow \quad \text{逆矩阵也低秩变化} }$$

连续扰动下逆矩阵的导数

如果矩阵不是从 $\mathbf{A}$ 一次跳到 $\mathbf{B}$，而是随时间连续变化：

$$\mathbf{A}=\mathbf{A}(t)$$

那么它的逆矩阵也随时间变化：

$$\mathbf{A}(t)^{-1}$$

这时自然会问：

$$\frac{d\mathbf{A}}{dt} \quad \Longrightarrow \quad \frac{d\mathbf{A}^{-1}}{dt}$$

怎么计算？

最直接的方法从恒等式开始：

$$\mathbf{A}(t)\mathbf{A}(t)^{-1} = \mathbf{I}$$

两边对 $t$ 求导。注意这是矩阵乘积，所以要用 product rule：

$$\frac{d\mathbf{A}}{dt}\mathbf{A}^{-1} + \mathbf{A}\frac{d\mathbf{A}^{-1}}{dt} = \mathbf{0}$$

把第一项移到右边：

$$\mathbf{A}\frac{d\mathbf{A}^{-1}}{dt} = - \frac{d\mathbf{A}}{dt}\mathbf{A}^{-1}$$

左乘 $\mathbf{A}^{-1}$，得到

$$\boxed{ \frac{d\mathbf{A}^{-1}}{dt} = - \mathbf{A}^{-1} \frac{d\mathbf{A}}{dt} \mathbf{A}^{-1} }$$

这个公式和标量求导

$$\frac{d}{dt}\left(\frac{1}{a(t)}\right) = - \frac{a'(t)}{a(t)^2}$$

非常像。区别是矩阵不能随便交换顺序，所以标量公式里的

$$-\frac{a'(t)}{a(t)^2}$$

在矩阵里必须写成

$$- \mathbf{A}^{-1} \frac{d\mathbf{A}}{dt} \mathbf{A}^{-1}$$

而不是随便把 $\frac{d\mathbf{A}}{dt}$ 放到别的位置。

从有限差分的角度也能看到同一个结论。令

$$\mathbf{B} = \mathbf{A} + \Delta \mathbf{A}$$

代入前面的恒等式：

$$\mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1}$$

因为

$$\mathbf{A}-\mathbf{B} = - \Delta \mathbf{A}$$

这里的负号来自移项：

• 由 $\mathbf{B}=\mathbf{A}+\Delta \mathbf{A}$ 可得

$$\Delta \mathbf{A} = \mathbf{B}-\mathbf{A}$$

• 因此反过来写 $\mathbf{A}-\mathbf{B}$ 时，就等于

$$\mathbf{A}-\mathbf{B} = - (\mathbf{B}-\mathbf{A}) = - \Delta \mathbf{A}$$

所以

$$(\mathbf{A}+\Delta \mathbf{A})^{-1} - \mathbf{A}^{-1} = - (\mathbf{A}+\Delta \mathbf{A})^{-1} \Delta \mathbf{A} \mathbf{A}^{-1}$$

这个式子就是把前面的恒等式 $\mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1}$ 逐项替换：

• 因为 $\mathbf{B}=\mathbf{A}+\Delta \mathbf{A}$，所以

$$\mathbf{B}^{-1} = (\mathbf{A}+\Delta \mathbf{A})^{-1}$$

• 又因为 $\mathbf{A}-\mathbf{B}=-\Delta \mathbf{A}$，所以

$$\mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1} = (\mathbf{A}+\Delta \mathbf{A})^{-1} (-\Delta \mathbf{A}) \mathbf{A}^{-1}$$

也就是

$$- (\mathbf{A}+\Delta \mathbf{A})^{-1} \Delta \mathbf{A} \mathbf{A}^{-1}$$

两边除以 $\Delta t$：

$$\frac{ (\mathbf{A}+\Delta \mathbf{A})^{-1} - \mathbf{A}^{-1} }{ \Delta t } = - (\mathbf{A}+\Delta \mathbf{A})^{-1} \frac{\Delta \mathbf{A}}{\Delta t} \mathbf{A}^{-1}$$

令 $\Delta t\to 0$，就得到同一个导数公式：

$$\frac{d\mathbf{A}^{-1}}{dt} = - \mathbf{A}^{-1} \frac{d\mathbf{A}}{dt} \mathbf{A}^{-1}$$

所以，矩阵逆的扰动公式可以分成两种看法：

$$\boxed{ \text{有限变化：} \quad \mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1} }$$ $$\boxed{ \text{连续变化：} \quad \frac{d\mathbf{A}^{-1}}{dt} = - \mathbf{A}^{-1} \frac{d\mathbf{A}}{dt} \mathbf{A}^{-1} }$$

连续扰动下特征值的导数

之前介绍的是 $\mathbf{A}(t)^{-1}$ 怎么随时间变化，现在来讨论另一个对象：如果矩阵本身随时间连续变化，

$$\mathbf{A}=\mathbf{A}(t)$$

那么某个 eigenvalue

$$\lambda=\lambda(t)$$

的变化率是什么？

先考虑一个简单 eigenvalue，也就是在附近可以平滑地选出对应的右 eigenvector 和左 eigenvector。右 eigenvector 满足

$$\mathbf{A}(t)\mathbf{x}(t) = \lambda(t)\mathbf{x}(t)$$

左 eigenvector 满足

$$\mathbf{y}(t)^\top\mathbf{A}(t) = \lambda(t)\mathbf{y}(t)^\top$$

等价地说，$\mathbf{y}(t)$ 是 $\mathbf{A}(t)^\top$ 的右 eigenvector。因为 eigenvector 本身可以乘任意非零常数，所以通常会选一个方便的归一化条件：

$$\mathbf{y}(t)^\top\mathbf{x}(t) = 1$$

在这个归一化下，核心公式是

$$\boxed{ \frac{d\lambda}{dt} = \mathbf{y}(t)^\top \frac{d\mathbf{A}}{dt} \mathbf{x}(t) }$$

它的推导从一个标量恒等式开始。因为

$$\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$$

且之前定义了

$$\mathbf{y}(t)^\top\mathbf{x}(t) = 1$$

所以

$$\mathbf{y}^\top\mathbf{A}\mathbf{x} = \mathbf{y}^\top(\lambda\mathbf{x}) = \lambda\mathbf{y}^\top\mathbf{x} = \lambda$$

也就是

$$\lambda(t) = \mathbf{y}(t)^\top\mathbf{A}(t)\mathbf{x}(t)$$

现在对 $t$ 求导。右边有三个随时间变化的因子，所以 product rule 给出

$$\frac{d\lambda}{dt} = \frac{d\mathbf{y}^\top}{dt}\mathbf{A}\mathbf{x} + \mathbf{y}^\top\frac{d\mathbf{A}}{dt}\mathbf{x} + \mathbf{y}^\top\mathbf{A}\frac{d\mathbf{x}}{dt}$$

第一项可以用右 eigenvector 关系化简：

$$\frac{d\mathbf{y}^\top}{dt}\mathbf{A}\mathbf{x} = \frac{d\mathbf{y}^\top}{dt}(\lambda\mathbf{x}) = \lambda\frac{d\mathbf{y}^\top}{dt}\mathbf{x}$$

第三项可以用左 eigenvector 关系化简：

$$\mathbf{y}^\top\mathbf{A}\frac{d\mathbf{x}}{dt} = \lambda\mathbf{y}^\top\frac{d\mathbf{x}}{dt}$$

于是

$$\begin{align*} \frac{d\lambda}{dt} &= \lambda\frac{d\mathbf{y}^\top}{dt}\mathbf{x} + \mathbf{y}^\top\frac{d\mathbf{A}}{dt}\mathbf{x} + \lambda\mathbf{y}^\top\frac{d\mathbf{x}}{dt} \\ &= \lambda \left( \frac{d\mathbf{y}^\top}{dt}\mathbf{x} + \mathbf{y}^\top\frac{d\mathbf{x}}{dt} \right) + \mathbf{y}^\top\frac{d\mathbf{A}}{dt}\mathbf{x} \\ &= \lambda \frac{d}{dt}(\mathbf{y}^\top\mathbf{x}) + \mathbf{y}^\top\frac{d\mathbf{A}}{dt}\mathbf{x} \end{align*}$$

• 这里化简又使用了导数 product rule

但归一化条件给出

$$\mathbf{y}^\top\mathbf{x}=1$$

所以

$$\frac{d}{dt}(\mathbf{y}^\top\mathbf{x}) = \frac{d}{dt}(1) = 0$$

最后只剩下中间那一项：

$$\boxed{ \frac{d\lambda}{dt} = \mathbf{y}^\top \frac{d\mathbf{A}}{dt} \mathbf{x} }$$

如果不强行归一化成 $\mathbf{y}^\top\mathbf{x}=1$，同一个推导会得到

$$\boxed{ \frac{d\lambda}{dt} = \frac{ \mathbf{y}^\top \frac{d\mathbf{A}}{dt} \mathbf{x} }{ \mathbf{y}^\top\mathbf{x} } }$$

这里的分母来自左、右 eigenvector 的任意缩放。没有归一化时，

$$\mathbf{y}^\top\mathbf{A}\mathbf{x} = \mathbf{y}^\top(\lambda\mathbf{x}) = \lambda\mathbf{y}^\top\mathbf{x}$$

所以 $\mathbf{y}^\top\mathbf{A}\mathbf{x}$ 本身不是 $\lambda$，而是 $\lambda$ 乘上 $\mathbf{y}^\top\mathbf{x}$，因此真正对应 $\lambda$ 的量是

$$\lambda = \frac{ \mathbf{y}^\top\mathbf{A}\mathbf{x} }{ \mathbf{y}^\top\mathbf{x} }$$

可以从右 eigenvector 方程直接看出这个分母为什么必须出现，由

$$\mathbf{A}(t)\mathbf{x}(t) = \lambda(t)\mathbf{x}(t)$$

对 $t$ 求导，得到

$$\mathbf{A}'\mathbf{x} + \mathbf{A}\mathbf{x}' = \lambda'\mathbf{x} + \lambda\mathbf{x}'$$

左乘 $\mathbf{y}^\top$：

$$\mathbf{y}^\top\mathbf{A}'\mathbf{x} + \mathbf{y}^\top\mathbf{A}\mathbf{x}' = \lambda'\mathbf{y}^\top\mathbf{x} + \lambda\mathbf{y}^\top\mathbf{x}'$$

利用左 eigenvector 关系

$$\mathbf{y}^\top\mathbf{A} = \lambda\mathbf{y}^\top$$

可得

$$\mathbf{y}^\top\mathbf{A}\mathbf{x}' = \lambda\mathbf{y}^\top\mathbf{x}'$$

于是等式左右两边的 $\lambda\mathbf{y}^\top\mathbf{x}'$ 正好抵消，只剩

$$\lambda'\mathbf{y}^\top\mathbf{x} = \mathbf{y}^\top\mathbf{A}'\mathbf{x}$$

所以

$$\lambda' = \frac{ \mathbf{y}^\top\mathbf{A}'\mathbf{x} }{ \mathbf{y}^\top\mathbf{x} }$$

这说明分母必定出现，在没有固定 $\mathbf{x}$ 和 $\mathbf{y}$ 的尺度时，用来抵消 eigenvector 任意缩放的因子。比如把 $\mathbf{x}$ 换成 $c\mathbf{x}$，分子和分母都会同时乘上 $c$，因此 $\lambda'$ 不会受这种缩放影响。

所以归一化只是让分母消失，并没有改变公式的本质。

这个公式的直观含义是：矩阵的一个小变化

$$\mathbf{A} \longrightarrow \mathbf{A}+\Delta\mathbf{A}$$

会让对应 eigenvalue 产生一阶变化

$$\Delta\lambda \approx \mathbf{y}^\top (\Delta\mathbf{A}) \mathbf{x}$$

也就是说，$\lambda$ 的一阶变化不是由 $\Delta\mathbf{A}$ 的所有元素平均决定的，是由这个扰动夹在对应左、右 eigenvector 之间的投影决定的。

如果 $\mathbf{A}(t)$ 是实对称矩阵，那么左、右 eigenvector 可以取成同一个单位向量：

$$\mathbf{y}(t)=\mathbf{x}(t), \qquad \mathbf{x}(t)^\top\mathbf{x}(t)=1$$

于是公式简化为

$$\boxed{ \frac{d\lambda}{dt} = \mathbf{x}(t)^\top \frac{d\mathbf{A}}{dt} \mathbf{x}(t) }$$

这也是 symmetric matrix 中最常用的 eigenvalue perturbation 公式。

从逆矩阵扰动到特征值扰动

逆矩阵的变化关心的是

$$\mathbf{A}^{-1}$$

但很多数据分析问题更关心矩阵的 spectrum，也就是 eigenvalues。

例如 covariance matrix、Gram matrix、normal matrix 都经常是 symmetric positive semidefinite matrix。它们的 eigenvalues 描述了不同方向上的能量、方差或者信息量。

现在设 $\mathbf{S}$ 是一个实对称矩阵，它的 eigenvalues 按从大到小排列：

$$\gamma_1 \ge \gamma_2 \ge \cdots \ge \gamma_n$$

如果给 $\mathbf{S}$ 加上一个 rank-one positive semidefinite update：

$$\mathbf{S}_{\text{new}} = \mathbf{S} + \mathbf{u}\mathbf{u}^\top$$

新矩阵的 eigenvalues 记作

$$\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n$$

问题是：$\lambda_i$ 和 $\gamma_i$ 之间有什么关系？

直觉上，$\mathbf{u}\mathbf{u}^\top$ 是 positive semidefinite，因为对任意向量 $\mathbf{x}$，

$$\mathbf{x}^\top \mathbf{u}\mathbf{u}^\top \mathbf{x} = (\mathbf{u}^\top\mathbf{x})^2 \ge 0$$

所以它是在某些方向上增加能量，而不是减少能量。

因此我们至少应该期待：

$$\lambda_i \ge \gamma_i$$

也就是每个排序位置上的 eigenvalue 不会下降。

这个结论可以用 Rayleigh quotient 理解。对于单位向量 $\mathbf{x}$，

$$\mathbf{x}^\top (\mathbf{S}+\mathbf{u}\mathbf{u}^\top) \mathbf{x} = \mathbf{x}^\top\mathbf{S}\mathbf{x} + (\mathbf{u}^\top\mathbf{x})^2 \ge \mathbf{x}^\top\mathbf{S}\mathbf{x}$$

每个方向上的 quadratic form 都不变小，所以整体的 eigenvalues 也不会往下掉。

这叫 monotonicity：

$$\boxed{ \mathbf{S}_{\text{new}}-\mathbf{S}\succeq \mathbf{0} \quad \Longrightarrow \quad \lambda_i(\mathbf{S}_{\text{new}}) \ge \lambda_i(\mathbf{S}) }$$

Rank-one 正半定更新的 eigenvalue interlacing

rank-one positive semidefinite update 的结论不只是

$$\lambda_i\ge \gamma_i$$

还会有更强的 interlacing：

$$\boxed{ \lambda_1 \ge \gamma_1 \ge \lambda_2 \ge \gamma_2 \ge \lambda_3 \ge \cdots \ge \gamma_n }$$

也可以写成更紧凑的形式：

$$\boxed{ \lambda_i \ge \gamma_i \ge \lambda_{i+1} }$$

只要下标合法。

这个式子里有两层意思。

第一层是：

$$\lambda_i\ge \gamma_i$$

因为更新是 positive semidefinite，所以旧的第 $i$ 大 eigenvalue 不会变小。

第二层是：

$$\gamma_i\ge \lambda_{i+1}$$

这才是 interlacing 的关键。它说明 rank-one update 虽然可以把某一个方向的 eigenvalue 抬高，但它最多只能让一个新的 eigenvalue 插到某个旧 eigenvalue 前面。

比如对旧的最大 eigenvalue $\gamma_1$ 来说：

$$\lambda_1 \ge \gamma_1 \ge \lambda_2$$

这表示 rank-one 更新之后，最多只有一个新 eigenvalue 能超过旧的最大 eigenvalue。也就是说，$\lambda_1$ 可以超过 $\gamma_1$，但 $\lambda_2$ 不能超过 $\gamma_1$。

所以 rank-one update 并不限制一定要 “更新幅度小”，它的关键在于 “最多影响一个独立方向”。

Rank 控制位置，Magnitude 控制大小

这里很容易误解：rank-one update 并不表示 eigenvalue 只能小幅度改变。

例如

$$\mathbf{S} = \begin{bmatrix} 10 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

它的 eigenvalues 是

$$\gamma_1=10,\qquad \gamma_2=5,\qquad \gamma_3=1$$

现在做一个 rank-one positive semidefinite update：

$$\mathbf{S}_{\text{new}} = \mathbf{S} + 100 \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}$$

也就是

$$\mathbf{S}_{\text{new}} = \begin{bmatrix} 110 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

新 eigenvalues 是

$$\lambda_1=110,\qquad \lambda_2=5,\qquad \lambda_3=1$$

可以看到最大的 eigenvalue 被抬得非常高：

$$\lambda_1=110 \gg \gamma_1=10$$

但 interlacing 仍然成立：

$$110 \ge 10 \ge 5 \ge 5 \ge 1 \ge 1$$

也就是

$$\lambda_1 \ge \gamma_1 \ge \lambda_2 \ge \gamma_2 \ge \lambda_3 \ge \gamma_3$$

这个例子说明：

$$\boxed{ \text{rank 控制有多少个 eigenvalues 能向前挤；magnitude 控制被影响的 eigenvalue 能升多高} }$$

所以不能说 rank-one update 只能造成很小变化。更准确地说，它可以让一个方向变化很大，但不能让很多独立方向同时发生这种向前挤的变化。

Rank-r 更新：最多向前挤 r 个位置

如果更新不是 rank-one，而是 rank-$r$ positive semidefinite update：

$$\mathbf{S}_{\text{new}} = \mathbf{S} + \mathbf{U}\mathbf{U}^\top$$

其中

$$\mathbf{U}\in\mathbb{R}^{n\times r}$$

那么 $\mathbf{U}\mathbf{U}^\top$ 的 rank 最多为 $r$。

这时 interlacing 变成

$$\boxed{ \lambda_i \ge \gamma_i \ge \lambda_{i+r} }$$

只要下标 $i+r$ 没有超过 $n$。

这句话的直观解释是：

$$\boxed{ \text{rank-}r\text{ 更新后，旧的第 }i\text{ 大 eigenvalue 最多被新 eigenvalues 向前挤 }r\text{ 个位置} }$$

例如 rank-$5$ 时，不是说 eigenvalues 必须每 $5$ 个一组整齐交错，而是说

$$\lambda_i \ge \gamma_i \ge \lambda_{i+5}$$

比如对旧的最大 eigenvalue $\gamma_1$：

$$\boxed{ \lambda_1 \ge \gamma_1 \ge \lambda_6 }$$

这表示 rank-$5$ 更新以后，最多可以有 $5$ 个新 eigenvalues 超过旧的最大 eigenvalue $\gamma_1$：

$$\lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5$$

但第 $6$ 个新 eigenvalue 一定不会超过它：

$$\lambda_6 \le \gamma_1$$

所以 rank-$5$ 更新不会 一定 有 $5$ 个 eigenvalues 超过 $\gamma_1$，而是 最多 有 $5$ 个。

更一般地，对于任意旧 eigenvalue $\gamma_i$：

$$\gamma_i \ge \lambda_{i+r}$$

表示它最多向后掉 $r$ 个位置。

Rank-n 更新为什么交错意义会退化

如果矩阵是 $n\times n$，而更新是 rank-$n$，那就已经不是 low-rank update，而是 full-rank update。

形式上，rank-$r$ 的 interlacing 写作

$$\lambda_i \ge \gamma_i \ge \lambda_{i+r}$$

当 $r=n$ 时，右边变成

$$\lambda_{i+n}$$

但这个下标已经超出范围，所以后半个不等式基本失去意义。

剩下的只是 positive semidefinite update 带来的 monotonicity：

$$\boxed{ \lambda_i \ge \gamma_i }$$

这也符合直觉：如果所有方向都可能被更新，那么 rank 对 eigenvalue 位置的限制就没有什么用了。此时更新已经不再是 少数方向的信息加入，而是一个普通的 full-rank perturbation。

所以可以把几个情况总结成：

$$\boxed{ \text{rank-1：} \quad \lambda_i \ge \gamma_i \ge \lambda_{i+1} }$$ $$\boxed{ \text{rank-}r\text{：} \quad \lambda_i \ge \gamma_i \ge \lambda_{i+r} }$$ $$\boxed{ \text{rank-}n\text{：} \quad \text{交错约束基本退化，只剩下正半定更新的单调性} }$$

为什么 rank-r 会对应向前挤 r 位

可以从子空间的角度理解这个结论。

对于对称矩阵，eigenvalues 可以通过 min-max principle 描述。粗略地说，第 $i$ 大 eigenvalue 描述的是：在某个 $i$ 维子空间里，quadratic form 至少能保证达到多大的水平。

rank-$r$ update

$$\mathbf{U}\mathbf{U}^\top$$

只在 $\text{col}(\mathbf{U})$ 相关的方向上增加能量。这个影响空间的维度最多是 $r$：

$$\text{rank}(\mathbf{U}\mathbf{U}^\top) \le r$$

因此它最多能制造出 $r$ 个额外的“高能方向”。这些高能方向可以插到旧 eigenvalues 前面，但因为只有 $r$ 个独立方向，所以不可能无限制地把所有新 eigenvalues 都往前推。

这就是

$$\gamma_i \ge \lambda_{i+r}$$

的直观来源。

换句话说：

$$\boxed{ \text{rank 是维度约束，不是幅度约束} }$$

rank-$r$ 说明新增信息最多占据 $r$ 个独立方向；但在这些方向上，增加的能量可以很大。

如果更新不是 positive semidefinite

前面的 interlacing 默认更新是

$$\mathbf{U}\mathbf{U}^\top$$

这种 positive semidefinite update。

如果扰动不是 positive semidefinite，而是一般的对称低秩扰动

$$\mathbf{S}_{\text{new}} = \mathbf{S} + \mathbf{E}$$

其中 $\mathbf{E}$ 可能既有正方向，也有负方向，那么 eigenvalues 可能上升，也可能下降。

这时就不能再简单写成

$$\lambda_i \ge \gamma_i$$

因为 $\mathbf{E}$ 可能在某些方向上减少能量。

对一般对称扰动，更常见的控制方式是 Weyl inequality：

$$\boxed{ \gamma_i+\lambda_n(\mathbf{E}) \le \lambda_i(\mathbf{S}+\mathbf{E}) \le \gamma_i+\lambda_1(\mathbf{E}) }$$

这里 $\lambda_1(\mathbf{E})$ 是 $\mathbf{E}$ 的最大 eigenvalue，$\lambda_n(\mathbf{E})$ 是最小 eigenvalue。

如果 $\mathbf{E}\succeq \mathbf{0}$，那么

$$\lambda_n(\mathbf{E})\ge 0$$

于是得到单调性：

$$\lambda_i(\mathbf{S}+\mathbf{E}) \ge \gamma_i$$

如果 $\mathbf{E}$ 不是 positive semidefinite，则只能用它的最大和最小 eigenvalue 去夹住变化范围，而不能期待简单的单调上升。

所以在使用 interlacing 时，要先看清楚更新类型：

$$\boxed{ \text{positive semidefinite low-rank update} \quad \Longrightarrow \quad \text{monotonicity + interlacing} }$$ $$\boxed{ \text{general symmetric perturbation} \quad \Longrightarrow \quad \text{只能用更一般的 eigenvalue perturbation bounds} }$$

和前一章的联系

现在可以把第 10 章和这一章连起来看。

在 Woodbury formula 里，我们关心的是矩阵

$$\mathbf{A} \quad \longrightarrow \quad \mathbf{A} + \mathbf{U}\mathbf{V}^\top$$

以后，逆矩阵或线性系统解怎么快速更新。

这一章开头的恒等式说明：

$$\mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1}$$

所以只要 $\mathbf{A}-\mathbf{B}$ 是 low-rank，逆矩阵的变化也是 low-rank。这是 Woodbury 能够存在的结构原因。

而在 least squares、RLS 和 Kalman filter 里，常见更新是

$$\mathbf{A}^\top\mathbf{A} \quad \longrightarrow \quad \mathbf{A}^\top\mathbf{A} + \mathbf{v}\mathbf{v}^\top$$

或者

$$(\mathbf{P}_t^-)^{-1} \quad \longrightarrow \quad (\mathbf{P}_t^-)^{-1} + \mathbf{H}_t^\top\mathbf{R}^{-1}\mathbf{H}_t$$

这些更新往往是 positive semidefinite 的。于是从 spectral point of view 看，它们是在给某些观测方向增加信息量。

如果一次只加入一条观测，那么 normal matrix 发生 rank-one positive semidefinite update；如果一次加入 $r$ 条独立观测，那么就是 rank-$r$ positive semidefinite update。

因此：

$$\boxed{ \text{Woodbury 解释 inverse 怎么更新} }$$ $$\boxed{ \text{interlacing 解释 eigenvalues 怎么排列变化} }$$

两者共同说明：低秩新信息不会完全随机地改变整个矩阵结构，它的影响受到 rank 的限制。

总结

这一章有两条主线。

第一条是逆矩阵扰动。对于可逆矩阵 $\mathbf{A}$ 和 $\mathbf{B}$，

$$\mathbf{B}^{-1}-\mathbf{A}^{-1} = \mathbf{B}^{-1}(\mathbf{A}-\mathbf{B})\mathbf{A}^{-1}$$

所以如果 $\mathbf{A}-\mathbf{B}$ 是 low-rank，那么 $\mathbf{B}^{-1}-\mathbf{A}^{-1}$ 也是 low-rank。连续版本则是

$$\frac{d\mathbf{A}^{-1}}{dt} = - \mathbf{A}^{-1} \frac{d\mathbf{A}}{dt} \mathbf{A}^{-1}$$

第二条是 eigenvalue perturbation。连续扰动下，如果 $\lambda(t)$ 是一个简单 eigenvalue，并且左、右 eigenvector 归一化为

$$\mathbf{y}(t)^\top\mathbf{x}(t)=1$$

那么

$$\boxed{ \frac{d\lambda}{dt} = \mathbf{y}(t)^\top \frac{d\mathbf{A}}{dt} \mathbf{x}(t) }$$

这说明 eigenvalue 的一阶变化由矩阵扰动在对应左、右 eigenvector 方向上的投影决定。

如果进一步考虑 positive semidefinite low-rank update，还会得到 eigenvalue interlacing。若

$$\mathbf{S}_{\text{new}} = \mathbf{S} + \mathbf{U}\mathbf{U}^\top$$

且 $\mathbf{U}\mathbf{U}^\top$ 的 rank 最多为 $r$，旧 eigenvalues 是

$$\gamma_1\ge \gamma_2\ge \cdots \ge \gamma_n$$

新 eigenvalues 是

$$\lambda_1\ge \lambda_2\ge \cdots \ge \lambda_n$$

那么有

$$\boxed{ \lambda_i \ge \gamma_i \ge \lambda_{i+r} }$$

只要下标合法。

这句话最重要的解释是：

$$\boxed{ \text{rank-}r\text{ 正半定更新最多让旧 eigenvalues 被向前挤 }r\text{ 个位置} }$$

但这并不限制被影响的 eigenvalues 能变多大。rank 控制的是“多少个方向”，magnitude 控制的是“这些方向上升多少”。

因此，低秩扰动的核心直觉可以压缩成：

$$\boxed{ \text{低秩扰动不一定小，但它只能沿少数方向改变矩阵} }$$