on
Rayleigh Quotient
瑞利商，常用于将优化问题与矩阵的特征值和特征向量联系起来
1 定义 #
实对称矩阵 \(M\) 和非零向量 \(x\) ，瑞利商定义为： \[ R(M,x) = \frac{x^TMx}{x^Tx} = \frac{\sum_{ij}M_{ij}x_ix_j}{\sum_{ij}x_ix_j} \]
2 性质 #
-
当 \(x\) 是特征向量时，瑞利商就是其对应的特征值
证明：
如果 \(M\psi = \lambda\psi\) , 那么： \(\frac{\psi^T M\psi}{\psi^T \psi}=\frac{\psi^T \lambda\psi}{\psi^T \psi} = \lambda\)
-
瑞利商的最大值就是矩阵 \(M\) 的最大特征值，瑞利商的最小值就是矩阵 \(M\) 的最小特征值： \[ \lambda_{min} \leq \frac{x^T Mx}{x^T x} \leq \lambda_{max} \]
引理：若实对称矩阵\(\vec{M}\)的特征值和对应的标准正交特征向量分别为\(\mu_1, \dots , \mu_n\)和\(\vec{v}_1, \dots, \vec{v}_n\)。且向量\(\vec{x}\)表示为以这些标准正交特征向量为基的形式： \[\vec{x}=\sum_{i=1}^{n}c_i \vec{v}_i\] 则有： \[\vec{x}^T \vec{M} \vec{x}=\sum_{i=1}^n c_i^2 \mu_i\]
证明：
利用谱定理展开： \[\begin{align} \vec{x}^T \vec{M} \vec{x} &= \left( \sum_{i=1}^{n}c_i \vec{v}_i \right)^T \left( \sum_{i=1}^n \mu_i \vec{v}_i \vec{v}_i^T \right) \left( \sum_{i=1}^{n}c_i \vec{v}_i \right)\\ &= \left( \sum_{i=1}^{n}c_i \vec{v}_i \right)^T \left( \sum_{i=1}^n c_i \mu_i \vec{v}_i \right)\\ &= \sum_{i,j} c_i c_j \mu_j \vec{v}_i^T \vec{v}_j\\ &= \sum_i^n c_i^2 \mu_i \end{align}\]
证明：
利用谱定理将\(M\)展开： \[\frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^{T}\vec{x}} = \frac{\vec{x}^{T}\sum_{i}^{n}\lambda_i \vec{u_i} \vec{u_i}^T \vec{x}}{\vec{x}^{T}\vec{x}}\] 将特征值从小到大排列，可得： \[\frac{\lambda_1 \sum_{i}^{n}\left( \vec{x}^T \vec{u_i} \right)^2}{\vec{x}^T \vec{x}} \leq \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^{T}\vec{x}}\leq \frac{\lambda_n \sum_{i}^{n}\left( \vec{x}^T \vec{u_i} \right)^2}{\vec{x}^T \vec{x}}\] 由于\(\vec{u}\)是一组标准正交基，所以\(\sum_{i}^{n}\left( \vec{x}^T \vec{u_i} \right)^2\)恰为\(\vec{x}^T \vec{x}\)。 且当\(\vec{x}\)为\(\lambda_1\)和\(\lambda_{n}\)对应的特征向量时，上述两不等号取等号。
-
以上结论可以推广到所有特征值，令\(\vec{M}\)是 n 维实对称矩阵，它的特征值从大到小为：\(\mu_1, \dots , \mu_n\)，对应的特征向量分别是\(\vec{v_1}, \dots ,\vec{v_n}\)，那么：
\[\vec{v_1} \in \argmax_{\|\vec{x}\|=1} \vec{x}^T \vec{M} \vec{x}\]
且对\(2\leq i\leq n\)，有：
\[\vec{v_i} \in \argmax_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v_j}=0, \forall j < i}} \vec{x}^T \vec{M} \vec{x}\]
类似有：
\[\vec{v_i} \in \argmin_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v_j}=0, \forall j>i}} \vec{x}^T \vec{M} \vec{x}\]
对于特征值，类似有：
\[\mu_1 = \max_{\| \vec{x} \|=1} \vec{x}^T \vec{M} \vec{x} = \max_{\vec{x}\neq 0} \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\]
对于\(2\leq i\leq n\)，有：
\[\mu_i = \max_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v_j}=0, \forall j<i}} \vec{x}^T \vec{M} \vec{x} = \max_{\substack{\vec{x}\neq 0 \\ \vec{x}^T \vec{v_j}=0, \forall j<i}} \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\]
\[\mu_i = \min_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v_j}=0, \forall j>i}} \vec{x}^T \vec{M} \vec{x} = \min_{\substack{\vec{x}\neq 0 \\ \vec{x}^T \vec{v_j}=0, \forall j>i}} \frac{\vec{x}^T \vec{M} \vec{x}}{\vec{x}^T \vec{x}}\]
如果特征值是从小到大排列，则上述所有 min、max 互换即可。
证明：
对\(\vec{M}\)特征分解：\(\vec{M} = \vec{Q}^T \vec{\Lambda} \vec{Q}\)，所以\(\vec{x}^T \vec{M} \vec{x} = (\vec{Q}\vec{x})^T \vec{\Lambda} (\vec{Q}\vec{x})\)，因为\(\vec{Q}\)是正交矩阵，所以\(\|\vec{Q}\vec{x}\|=\|\vec{x}\|\)，可以不失一般性地只考虑\(\vec{M}=\Lambda\)是一个对角矩阵的情况（此时特征值不变，特征向量左乘一个\(\vec{Q}\)）。
所以\(\vec{x}^T \vec{M} \vec{x} = (x_1, \dots , x_n)\begin{pmatrix} \mu_1 & & \\ & \ddots & \\ & & \mu_n \end{pmatrix} \begin{pmatrix} x_1\\ \vdots\\ x_n \end{pmatrix} =\sum_{i=1}^{n}\mu_i x_i^2 \)
此时\(\vec{M}\)是对角矩阵，其特征向量为\(\vec{v_i}=\vec{e_i}, i=1 \dots n\)，即标准基。
下面证明：
\[\mu_k = \max_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v}_i=0, \forall i<k}} \vec{x}^T \vec{M} \vec{x}\]
其中限制条件\(\vec{x}^T \vec{v}_i = 0, \forall i<k\)等价于\(x_i = \langle \vec{x}, \vec{e}_i\rangle =0, \forall i<k\)，再加上另一个条件\(\|\vec{x}\|=1\)，有：
\[\vec{x}^T \vec{M} \vec{x} = \sum_{i=1}^{n}\mu_i x_i^2 = \sum_{i=k}^{n}\mu_i x_i^2 \leq \mu_k \sum_{i=k}^n x_i^2 = \mu_{k}\]
再说明上述不等号可以取到：令\(\vec{x} = \vec{e}_k\)，可以验证它满足上述两个限制条件。此时\(\vec{x}^T \vec{M} \vec{x} = \mu_k\)，从而证明了： \[\mu_k = \max_{\substack{\|\vec{x}\|=1 \\ \vec{x}^T \vec{v}_i=0, \forall i<k}} \vec{x}^T \vec{M} \vec{x}\]