小姐姐深夜微信：一个计算特征向量的“新”方法

引子：
前日深夜，小姐姐阿杰在群里@我，怀着忐忑的心情点开一看，是一条链接。小姐姐惜字如金，真是让人摸不着头脑。链接中是公众号量子位在知乎上发表的一篇文章，本人一向喜欢量子位的文章，但是这篇文章的标题确实有点标题党（哈哈，我这篇文章也是）的嫌疑，标题为“三个物理学家意外发现基础数学新方法，陶哲轩：我开始压根不信。”这标题一看还挺吓人，基础数学新方法，还意外发现，还有陶哲轩大神加持光环。不看也得看了，遂将内容和部分帖子的讨论内容整理如下。

0. 故事的开始：中微子振荡

中微子在物理学上是个有意思的存在，因为其相互作用较为微弱，所以探测器来较为困难，也就显得更为神秘。另外就是本来在规范场模型中，中微子被假设为没有质量，但是通过中微子振荡实验，发现中微子十有质量的，因此才会出现中微子振荡现象，也就是大亚湾中微子实验室的一大贡献。描述中微子振荡的方程恰好是一个本征方程，即
$|\psi_{\alpha}> \ = \ U|\psi_{i}>$
其中， $|\psi_{\alpha}>$ 表示味，而 $|\psi_{i}>$ 表示中微子味对应的质量。当然这里并不准备讲述中微子的完整模型，只是想说说为啥三个物理学家关系这个问题，对于学过量子力学的人都知道，在物理学中一个物理算符 $\hat A$ 作用于态函数，如果是可观测物理量，则必然对应于一个实数值，因而表示为一个本征方程
$\hat A \psi \ =\ a\psi$
所以曾经和一个南大数学教授一起玩笑说，做物理的，大部分时间要么在计算本征方程，要么在处理矩阵对角化问题（矩阵对角化往往意味着可以分离变量，降低微分方程的求解难度）。

1. 特征值和特征向量

既然要聊这个话题，就简单复习一下

1.1 定义

令 $A$ 为一个 $n \times n$ 的方阵，如果存在一个非零向量 $\boldsymbol x$ 使得 $A \boldsymbol x \ =\ \lambda \boldsymbol x$ ，则称标量 $\lambda$ 为特征值，自然称 $\boldsymbol x$ 为属于 $\lambda$ 的特征向量。
我们知道，一个矩阵就是一个包含旋转和伸缩的表换，而对于特征向量，该矩阵只有伸缩变换而没有旋转变换。因此，几何意义上来说，特征向量是一个稳态。尤其是在对角化问题上，可以利用特征向量构成矩阵的列向量，继而实现矩阵的对角化
$X^{-1}AX\ = \ D$

1.2 应用

特征值和特征向量在处理随机过程和线性微分方程组中都有着深刻而明确的意义。Steven J. Leon在《线性代数》^[1]中举了这样一个有趣的例子，在某城镇中，每年 $30\%$ 的已婚女性离婚，且 $20\%$ 的单身女性结婚。假定共有 $8000$ 名已婚女性和2000名单身女性，且总人口数保持不变。在保持结婚率和离婚率保持不变的情况下，将当前结婚女性和单身女性写为向量 $w_0=(8000, 2000)^T$ ，1年后的结婚女性和单身女性为
$w_1=Aw_0=\begin{bmatrix}0.7&0.2\\0.3&0.8\end{bmatrix}\begin{bmatrix}8000\\2000\end{bmatrix}=\begin{bmatrix}6000\\4000\end{bmatrix}$ （取了约化后的值）那么对于第2年结婚女性和单身女性人数可以计算为 $w_2=Aw_1=A^2w_0$ ，那么一般地，对于 $n$ 年之后有 $w_n=A^nw_0$ ，近似计算有
$w_{10}=\begin{bmatrix} 4004\\5996 \end{bmatrix}, \quad w_{20}=\begin{bmatrix} 4000\\6000\end{bmatrix}, \quad w_{30}=\begin{bmatrix} 4000\\6000\end{bmatrix}$
而矩阵 $A$ 的一个特征向量就是 $\boldsymbol x_1 = (2,3)^T$ 。观察后我们发现，这一个过程最终稳定在特征向量方向上。

这是一个简单理解特征向量的例子，而更为特别的，在机器学习PCA算法中，利用协方差(方差)向特征向量进行投影，继而实现数据的“降为打击”。这或许也是大家如此关心当前这个话题原因之一。

2. 计算特征向量的“旧”思路

反正我是不知道别人，我大学的时候求特征向量就靠“猜”，实在懒得算，用笔算的也复杂不到哪去，所以真没太注意“标准流程”，但实际上标准思路基本根据定义来的，
首先，将特征方程 $Ax=\lambda x$ 换成形式为 $(A-\lambda I)x=0$ ；
然后，其解集定义为特征空间 $N(A-\lambda I)$ ；
为了保证上述有非平凡解，则将特征值问题转化为代数方程 $det(A-\lambda I)=0$ ，根据上述求解得特征值 $(\lambda _1, \lambda _2, \dots , \lambda_n)$ 并带入原方程得到对应得特征向量 $(x_1, x_2, \dots, x_n)$ 。

3. “新”方法的证明思路

注意，以下过程是建立再矩阵 $A$ 是Hermite矩阵的前提之下的。
在第二版论文^[2]当中,证明过程十分简洁，但又很抽象，本人也没有什么好的办法更为通俗得解释，首先是利用Cauchy-Binet公式作为引理，不失一般性的，如果让 $A$ 的一个本征值 $\lambda_n(A)=0$ ，那么可以对 $A$ 去掉一列，将剩下的 $n \times n-1$ 矩阵记为 $B=\begin{bmatrix} B' \\ X \end{bmatrix}$ ，这里假设矩阵对角化为 $A=VDV^*$ ，其中 $D \equiv diag(\lambda_1(A), \dots, \lambda_{n-1}(A),0)$ ，此时可以取 $B \rightarrow V^*B$ 以及 $v_n \rightarrow V^*v_n=e_n$ ，再假设 $A=D$ 以及 $v_n=e_n$ ，那么显然有 $det(B^*AB)=\prod_{i=1}^{n-1}\lambda_i(A)|det(B')^2|$ ，同理，最终证明
$\prod_{i=1}^{n-1}\lambda_i(A)|det(B, v_n)|^2=det(B^*AB) \tag{1}$
这一部分的证明看似有些乱，但实际上却是很简单自然的结果，根据假设实际上有下式成立
$A=D\equiv \left[ \begin{array}{ccc|c} \lambda_1(A) & \cdots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & \lambda_{n-1}(A) & 0 \\ \hline 0 & \cdots & 0 & 0 \end{array} \right] = \left[ \begin{array}{c|c} B & X^T \\ \hline X&0 \end{array} \right]$
如此，一个简洁的计算即可获得证明。不得不说构造的很是精巧。
接下来就是利用伴随矩阵的的证明，即对于公式
$\left| v_{i,j} \right|^2 \prod^n_{k=1; k\ne i}\left(\lambda_i(A)-\lambda_k(A) \right)=\prod_{k=1}^{n-1}\left(\lambda_i(A)-\lambda_k(M_j) \right) \tag{2}$
很显然，如果我们取 $j=1,i=n$ . 使用 $\lambda_n(A)I_n$ 变换 $A$ 有 $\lambda_n(A)=0$ ，这样 $A$ 剩余的特征值就等同于 $M_j$ 的特征值。并利用方程(1)，方程(2)也就化为
$\left| v_{n,1} \right|^2 \prod^{n-1}_{k=1}\lambda_k(A)=\prod_{k=1}^{n-1}\lambda_k(M_1)=det(M_1) \tag{3}$
这其实就反映了文章的重点，当我们擦去一个特征值，并不会影响其余特征值的求解，那么反过来就建立了当前的特征值与子矩阵特征值和特征向量之间的关系。伴随矩阵的证明过程不再赘述，最终我们可以得到结论
结论：如果擦除特征向量的一个元素，即 $v_{ij}=0$ ，那么子矩阵 $M_j$ 的特征值也相应变化为 $\lambda_i(A)$ 。
值得一提的是，文中说再引理2证明过程中提供了一种相位的计算机制，即
$adj(\lambda_i(A)I_n-A)=\prod_{k=1;k\ne i}^n(\lambda_i(A)-\lambda_k(A))v_iv_i^*$
但是个人觉得对于相位的处理还是不够直观，似乎计算起来并不容易。

4. 举个例子

为了方便计算，将上述公式写为
$\left| v_{i,j} \right|^2 =\frac{\prod_{k=1}^{n-1}\left(\lambda_i(A)-\lambda_k(M_j) \right)}{\prod^n_{k=1; k\ne i}\left(\lambda_i(A)-\lambda_k(A) \right)} \tag{4}$
那么这里随便找一个对称矩阵 $\begin{bmatrix} 1 & 2 \\ 1 & 4 \end{bmatrix}$ ，其特征值 $(\lambda_1,\lambda_2)$ 为 $(0,5)$ ，因此有
$|v_{1,1}|^2=\frac{0-4}{0-5}=\frac{4}{5} \\ |v_{1,1}|^2=\frac{0-1}{0-5}=\frac{1}{5}$
故而暂不考虑相位时， $\lambda_1$ 对应的特征向量为 $\begin{bmatrix} \frac{2\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{bmatrix}$ ，特别的，求得的结果是单位长度的。

5. 新方法的若干评论

最初，该方法由Tao协作三位物理学家公布，随后Quanta Magazine^[3]关注并报道此事。根据知乎^[4]上的一个评论来看，最初几位作者是以“原创”结果发表的，但随即发现其实前人已经给出了该结果，遂在第二版论文中隐去“原创”部分。而Tao也在自己的博客中总结了前人的进展。大神们严谨的态度令人倾佩。

原本现在本部分对各个论坛的讨论做一个总结，但是奈何家里网络不靠谱就写到这儿吧。值得罗嗦一下的是，我觉得无论公式是不是新发现，我觉得有些知识回顾一下还是有好处的，让人有一种常读常新的感觉。每一次仔细思考之后，都能获得一些新想法。因为对于同一个问题的回顾，我们自身的知识背景就有了不同，如此，我们可能在PCA方面的对称问题上或许又有了新的思考。特别是，该方法引申出对于数据，如果它包含了一定的对称性(比如Hermite矩阵)，或许我们就能够更多思考数据本身的内在联系。这或许才是这个事情带给我们最大的收益。

参考文献

Steven J. Leon.《线性代数》 ↩
Denton P, Parke S, Tao T, Zhang X. Eigenvectors from Eigenvalues ↩
Neutrinos Lead to Unexpected Discovery in Basic Math ↩
知乎：如何通俗地解释陶哲轩等人简化矩阵特征向量求解的方法? ↩