[UCAS矩阵论]5.3对称矩阵特征值的极性
实对称矩阵特征值的极性与 Rayleigh 商
本节中记实对称矩阵 \(A\) 的特征值按大小排列为 \(\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n\),对应标准正交特征向量系为 \(p_1,p_2,\ldots,p_n\).
将 Rayleigh 商定义在实对称矩阵上是为了保证特征值一定是实数,这样才可以比较。
定义:设 \(A\) 是 \(n\) 阶实对称矩阵,\(x\in\mathbb R^n\),定义矩阵 \(A\) 的 Rayleigh 商为: \[ R(x)=\frac{x^TAx}{x^Tx},\quad x\neq 0 \] 定理:设 \(A\) 为实对称矩阵,则: \[ \min_{x\neq 0}R(x)=\lambda_1,\quad\max_{x\neq 0}R(x)=\lambda_n \]
证明:任取 \(x\neq 0\),依标准正交特征向量系分解 \(x=c_1p_1+\cdots+c_np_n\),则: \[x^Tx=c_1^2+\cdots+c_n^2,\quad x^TAx=c_1^2\lambda_1+\cdots+c_n^2\lambda_n\] 故: \[R(x)=k_1\lambda_1+\cdots+k_n\lambda_n,\quad\text{where}\; k_i=\frac{c_i^2}{c_1^2+\cdots+c_n^2}\] 容易推出 \(\lambda_1\leq R(x)\leq\lambda_n\),且 \(R(p_1)=\lambda_1,\,R(p_n)=\lambda_n\). 证毕。
证明 2(梯度法):取对数 \(\ln R(x)=\ln (x^TAx)-\ln(x^Tx)\),求导并令为零: \[\frac{\mathrm d\ln R(x)}{\mathrm dx}=\frac{2Ax}{x^TAx}-\frac{2x}{x^Tx}=0\implies Ax=R(x)x\] 因此极值点处 \(R(x)\) 为 \(A\) 的特征值,\(x\) 为对应特征向量。于是最小值为最小特征值 \(\lambda_1\),最大值为最大特征值 \(\lambda_n\). 证毕。
(或者转换成约束 \(x^Tx=1\) 下的优化问题,引入拉格朗日乘子求解)
由于 \(x\) 模长不影响 \(R(x)\),所以上述定理也常常写作: \[\min_{\Vert x\Vert_2=1}x^TAx=\lambda_1,\quad\max_{\Vert x\Vert_2=1}x^TAx=\lambda_n\] 下文视情况两种写法都可能出现。
定理:设 \(A\) 为实对称矩阵,则对于任意的 \(1\leq r\leq n\) 有: \[ \min_{X^TX=I_r}\text{tr}(X^TAX)=\lambda_1+\cdots+\lambda_r \]
将 Rayleigh 商中的向量扩展为矩阵。
证明:对 \(A\) 作谱分解 \(A=P\Lambda P^T\),其中 \(P\) 为正交矩阵,\(\Lambda=\text{diag}(\lambda_1,\ldots,\lambda_n)\). 记 \(B=P^TX\),则问题转化为对角矩阵情形,即求证: \[\min_{B^TB=I_r}\text{tr}(B^T\Lambda B)=\lambda_1+\cdots+\lambda_r\] 记 \(BB^T\) 的对角元素为 \(B_{11},\ldots,B_{nn}\),则可以证明在 \(B^TB=I\) 的条件下,\(0\leq B_{ii}\leq 1\). 因此: \[\text{tr}(B^T\Lambda B)=\text{tr}(\Lambda BB^T)=\lambda_1B_{11}+\cdots+\lambda_n B_{nn}\] 所以这是一个关于 \(B_{11},\ldots,B_{nn}\) 的线性约束下的线性问题,最小值必然在约束区域的顶点处取得。显然这个顶点应该是 \(B_{11}=\cdots=B_{rr}=1\),\(B_{r+1,r+1}=\cdots=B_{nn}=0\),此时取到最小值 \(\lambda_1+\cdots+\lambda_r\). 证毕。
定理:设 \(x\in L(p_r,p_{r+1},\ldots,p_s),\,1\leq r\leq s\leq n\),则: \[ \min_{x\neq 0}R(x)=\lambda_r,\quad\max_{x\neq 0}R(x)=\lambda_s \]
证明与前面的定理证明类似。
这个定理表明 Rayleigh 商在特征向量张成的子空间中的极值就是对应最大最小特征值。但是在实际应用中,特征向量张成的子空间并不好找,所以下面的 Courant-Fischer 定理只限制子空间维数为 \(k\),再对所有 \(k\) 维子空间求极值。
定理(Courant-Fischer):设 \(V_k\) 表示 \(\mathbb R^n\) 中的任意一个 \(k\) 维子空间,则: \[ \lambda_k=\min_{V_k}\max_{x\in V_k,x\neq0}R(x) \] 或写作: \[ \lambda_k=\min_{V_k}\max_{x\in V_k,\Vert x\Vert_2=1}x^TAx \]
证明:取 \(V_k=L(p_1,\ldots,p_k)\),根据前一个定理有: \[\max_{x\neq 0}R(x)=\lambda_k\] 因此下面只需要证明对所有 \(V_k\),\(\max\limits_{x\neq 0}R(x)\geq \lambda_k\).
构造 \(R^n\) 的 \(n-k+1\) 维子空间 \(W_k=L(p_k,p_{k+1},\ldots,p_n)\),则任一 \(V_k\) 与 \(W_k\) 必有交集。取非零向量 \(x\in V_k\cap W_k\),设 \(x=c_kp_k+\cdots+c_np_n\),则: \[R(x)=\frac{c_k^2\lambda_k+\cdots+c_n^2\lambda_n}{c_k^2+\cdots c_n^2}\geq \lambda_k\] 证毕。
将 \(A\) 替换成 \(-A\),能立刻得到如下定理: \[\lambda_{n-k+1}=\max_{V_k}\min_{x\in V_k,x\neq0}R(x)\]
定理:设实对称矩阵 \(A\) 和 \(A+Q\) 的特征值分别为 \(\lambda_1\leq\cdots\leq\lambda_n\) 和 \(\mu_1\leq\cdots\leq\mu_n\),则: \[ |\lambda_i-\mu_i|\leq \Vert Q\Vert_2 \]
证明:利用 Courant-Fischer 定理, \[\begin{align}\mu_i+\Vert Q\Vert_2&=\min_{V_i}\max_{x\in V_i,\Vert x\Vert_2=1}x^T(A+Q)x+\Vert Q\Vert_2I\\&=\min_{V_i}\max_{x\in V_i,\Vert x\Vert_2=1}x^T(A+Q+\Vert Q\Vert_2I)x\\&\geq\min_{V_i}\max_{x\in V_i,\Vert x\Vert_2=1}x^TAx\\&=\lambda_i\end{align}\] 不等式是因为 \(Q+\Vert Q\Vert_2I\) 为半正定矩阵。另一个方向可以进行类似的证明(用 \(Q-\Vert Q\Vert_2I\) 为半负定矩阵)。
为什么 \(Q+\Vert Q\Vert_2I\) 是半正定矩阵?对 \(Q\) 进行谱分解 \(Q=P\Lambda P^T\),则: \[Q+\Vert Q\Vert_2I=P\Lambda P^T+\Vert\Lambda\Vert_2I=P(\Lambda +\Vert\Lambda\Vert_2I)P^T\] 因此只需要证明对角矩阵 \(\Lambda +\Vert\Lambda\Vert_2I\) 是半正定矩阵。由于 \(\Vert\Lambda\Vert_2=\rho(\Lambda)\),因此其对角元素一定非负,这样就完成了证明。
广义特征值的极性与广义 Rayleigh 商
定义:设 \(A,B\) 为 \(n\) 阶实对称矩阵,且 \(B\) 正定,定义矩阵 \(A\) 相对于矩阵 \(B\) 的广义 Rayleigh 商为: \[ R(x)=\frac{x^TAx}{x^TBx},\quad x\neq 0 \] 定理:非零向量 \(x_0\) 是 \(R(x)\) 的驻点的充要条件是 \(x_0\) 为 \(Ax=\lambda Bx\) 的属于特征值 \(\lambda\) 的特征向量。
推论:若 \(x_0\) 是 \(A\) 相对于 \(B\) 的特征向量,则 \(R(x_0)\) 是与之对应的特征值。
定理(Courant-Fischer 定理在广义特征值上的扩展):广义特征值问题有如下极小极大性质: \[ \begin{align} \lambda_k&=\min_{V_k}\max_{x\in V_k,x\neq 0}R(x)\\ \lambda_{n-k+1}&=\max_{V_k}\min_{x\in V_k,x\neq0}R(x) \end{align} \]
矩阵奇异值的极性
定理:设 \(A\in\mathbb R^{m\times n}_r\) 的奇异值为: \[ 0=\sigma_1=\sigma_2=\cdots=\sigma_{n-r}<\sigma_{n-r+1}\leq\cdots\leq\sigma_n \] \(A+Q\in\mathbb R^{m\times n}_{r'}\) 的奇异值为: \[ 0=\tau_1=\tau_2=\cdots=\tau_{n-r'}<\tau_{n-r'+1}\leq\cdots\leq\tau_n \] 则有: \[ |\sigma_i-\tau_i|\leq \Vert Q\Vert_2\quad(i=1,2,\ldots,n) \]
对比第一节最后一个定理。