查看原文
其他

一个数学证明的诞生

丁玖 返朴 2024-03-17

星标,才能不错过每日推送!方法见文末动图



大数学家外尔 (Hermann Weyl,1885-1955) 曾说:“我的工作总是设法将真与美统一起来,但如果二者只能择其一,我通常会选择美。”在数学中,美的定理、美的证明,特征之一是“清楚简洁”。本文回顾了作者在十六年前的一篇论文中,对“矩阵行列式引理”的一个简洁优美的证明,介绍了线性代数里用于分块矩阵的高斯行列变换技巧。



撰文 | 丁玖(美国南密西西比大学数学系教授)

相遇“矩阵行列式引理”


半年前,我审读了一篇投往《应用数学快报》(Applied Mathematics Letters的文章。在这篇关于迭代法的来稿里,有段话引起了我的兴趣:“Before proving the convergence of the new iterative scheme we generalize the so-called matrix determinant lemma of [4] for more general rank-r modifications:”(在证明新的迭代方案的收敛性之前,我们将[4]中的所谓矩阵行列式引理推广到更一般的秩-r修正)。参考文献[4]正是我以及合作者于十六年前在同一家杂志上发表的论文“Eigenvalues of rank-one updated matrices with some applications(《秩-1校正矩阵的特征值及其一些应用》)
吊起我胃口的是术语“矩阵行列式引理”,听作者的口气,似乎是我们的文章给出了这条“引理”,甚至还将其加以命名。但是,我对这个名称却是一无所知,那一天是第一次见到它,真是孤陋寡闻!
好在如今资讯发达,在网上查询信息十分便捷。我在谷歌搜索输入词组matrix determinant lemma,电脑屏幕上蹦出来的第一条信息是Wikipedia(维基百科)的“Matrix determinant lemma”条目。它的内容第一段是:“在数学中,特别是线性代数中,矩阵行列式引理计算可逆矩阵 A 与列向量 u 和行向量 vT 的二进积 uvT 之和的行列式。”
接下来,条目给出了这个引理的内容:假设 A 是可逆方阵,u和v是列向量。那么矩阵行列式引理指出:
det (A + uvT) = (1 + vTA-1u) det (A)。
这里uvT 是两个向量u和v的外积。
再接下来,便是上述行列式等式的证明了。令我惊讶(同时也有点窃喜)的是,证明援引的参考文献,也是我的那篇文章。由于
det (A + uvT) = det [A(I + A-1uvT)] = det (A) det (I + A-1uvT),
其中 I 代表与A同阶的单位矩阵,只需对A是单位矩阵 I 时证明矩阵行列式引理就够了。
而此时的等式det (I + uvT) = 1 + vTu 实为对下列分块矩阵分解等式的两边各自求行列式:

并用上“矩阵乘积的行列式等于各因子矩阵行列式的乘积”这一在上面已经用过的事实,以及根据“块三角矩阵的行列式等于所有对角块行列式的乘积”性质得到的结果:分解式左端的行列式是det (I + uvT),而右端的行列式则为1 + vTu。
最后,该条目叙述了矩阵行列式引理的推广:假设 A 是一个可逆的n×n矩阵,U和V是n×m矩阵。那么
det (A + UVT) = det (Im + VTA-1U) det (A)。
在A = In的特殊情形下,这就是韦恩斯坦-阿龙扎因恒等式 (Weinstein-Aronszajn identity)
det (In + UVT) = det (Im + VTU)。
然而,条目的作者可能不知道,我们在2007年发表的另一篇论文“Characteristic polynomials of some perturbed matrices”(《一些扰动矩阵的特征多项式》)中,对所言的韦恩斯坦-阿龙扎因恒等式给出了一步证明:将如上用于秩-1校正矩阵的特殊的矩阵分解式直接推广成

然后再两边求行列式便得结果。在维基百科的条目“Weinstein-Aronszajn identity”中,关于这个恒等式的证明采用的技巧是关于2×2分块矩阵的两个经典行列式等式,因而不及上述证明简洁,少了一点美感。然而这或许是2007年新的证明问世前最为标准和最为经济的证明之一。
如上便是维基百科中关于矩阵行列式引理及其推广的基本内容。回到我半年前正在审稿的文章,它的第一个定理就是将矩阵行列式引理推广到上面已经证明出的一般情形,但只考虑了满足该文要求的m = n特例。作者证明该定理的思路依然是传统的,即通过一个经典行列式等式


以及对上式左端2×2分块矩阵的一个三矩阵分解,再取行列式便获成功。
我没有料到自己十六年前受谷歌矩阵激发,为了探讨相关数学问题而想出的矩阵分解,被维基百科条目采纳为“矩阵行列式引理”的标准证明。这让我想起当年写作这篇数学短文的一些细节,在此记录下来,权当是对当年追求简洁美心态的一次回顾,顺便也与读者分享线性代数里用于分块矩阵的高斯行列变换技巧。

论文是怎样炼成的


那年,同之前的十多年一样,我如期访问了中国科学院数学与系统科学研究院。我和其中一个研究所的合作者在计算遍历理论的领域共同耕耘了许多个春秋,合写了不少研究论文,也出版了一本中文合著。这一次,我的合作者告诉我,“谷歌矩阵”这个数学领域的新生事物,由于问世还不到十年的谷歌公司在信息搜索引擎方面的巨大商业成功,尤其是它在“网页排序 (PageRank) ”算法里的核心地位,正在受到应用和计算数学家们的关注。他觉得我们或许也应该“关注一下”。
我接受了他的好建议,于是开始阅读有关文献,对谷歌矩阵——全世界最大的随机矩阵(即每行元素之和都等于1的非负矩阵)的基本性质有所了解。事实上,谷歌矩阵起源于根据所有网页相对重要性概念而定义出的一个有n行和n列的随机矩阵S,叫做原始谷歌矩阵,然后将它与某个秩为1的“摄动矩阵”evT进行一次凸组合,其中e是n维的分量全为1的列向量,n维列向量v被标准化成满足vTe = 1。结果生成的谷歌矩阵G = αS + (1 - α)evT不仅也是随机矩阵,而且是正矩阵,即其中的每个元素都为正数。这里的凸组合系数α在0.85的一个小邻域中选择。自然,实际上的谷歌矩阵绝非这么简单,或许是永不公开的商业秘密,但谷歌公司曾经在它的网页上声明:我们软件的核心是PageRank。
谷歌公司为顾客提供网页搜索服务的本钱在于,它能有效、快速计算出满足等式πT = πTG的行向量(π*)T(即G的左特征向量),它的所有分量给出不同网页的“相对重要性排名”。计算的方法是直接迭代法,即从一已标准化的初始行向量(π0)T出发,逐次左乘矩阵G,得到的迭代行向量序列{(π0)TGk}将趋向于极限(π*)T,其收敛速率与G的次最大特征值有关。
谷歌矩阵在形式上是主要矩阵αS加上一个秩为1的校正矩阵(1 – α)evT,其中列向量v为合适选取的一个概率正数组,即它的所有分量为正数,并且其和为1。后面这个特殊矩阵具有一般的秩-1矩阵uvT的形式,其中u = (1 - α)e和v均为非零的n维列向量。此外,由于S为随机矩阵,(αS)(1 - α)e = α(1 - α)e,故u = (1 - α)e是矩阵αS对应于特征值α的一个特征向量。这些观察引导了我考虑如下更一般的矩阵特征值摄动问题:
设A为一个n×n矩阵,计入其代数重数,令λ1, λ2, …, λn为A的所有特征值,且u和v为两个n维的非零列向量,其中u是A对应于特征值λ1的一个特征向量。试问秩-1校正后的矩阵A + uvT的计入代数重数的n个特征值是什么?在线性代数中,所谓矩阵M的特征值μ的代数重数说的是,M的特征多项式p(λ) = det (λI - M)在复数域上的因式分解中因子λ - μ的幂次。与代数重数相关的另一个自然数叫几何重数。特征值μ的几何重数是对应于μ的所有特征向量以及0向量所组成的那个“特征子空间”的维数。对任何特征值,它的代数重数总是大于或者等于几何重数。特别地,如果μ的代数重数为1,那么它的几何重数也是1,这时我们说特征值μ是简单的。
在没有领导督促的自由气氛里,在无需填表汇报的宽松环境中,研究者的脑袋瓜最容易冒出新奇的想法。坐在为访问学者提供的一间朝南的阳光明媚的办公室里,思考一番后,我一下子打开了窍门,选出一条路线,设法推出秩-1校正后的矩阵A + uvT之特征多项式det [λI - (A + uvT)]在复数域上的因式分解,来捕捉所有的特征值及其代数重数。而这个行列式所依据的矩阵又可以写成(λI - A) - uvT,它正是矩阵λI – A的秩-1校正。只要复数 λ不是矩阵A的特征值,λI - A就是一个我想要的可逆矩阵,因为我知道矩阵论中有个可逆矩阵之秩-1校正矩阵的行列式公式,它建立了校正后的矩阵行列式与未校正矩阵行列式之间一个简单、漂亮的关系:如果M是一个n×n可逆矩阵,u和v是n维的列向量,那么det (M + uvT) = (1 + vTM-1u) det (M)。


因为上述关系能够用来求解我自己提出的特征值摄动问题,所以我必须给出这个预备命题的证明。当然,这类初等的行列式等式早已是经典结果,我以前也见到过。美国有名的计算数学家豪斯霍尔德 (Aston Scott Householder,1904-1993) 于1964年出版了一本写法别具一格、相当有深度的好书The Theory of Matrices in Numerical Analysis(《数值分析中的矩阵论》),他把复数域上形如I - σuvH的秩-1校正矩阵称为“初等矩阵”,其中的σ为复数,上标H意指“共轭转置”,即把矩阵的每个元素换成共轭复数再将矩阵转置。作者把初等矩阵用作建造矩阵论大厦的地基。他最著名的数学创造“豪斯霍尔德矩阵”I - 2uuH就是一个特殊的初等矩阵,其中u是单位列向量。1987年夏,刚毕业的韩国裔师兄李弘九博士在奔赴新校任教前,邀请我同他开办二人讨论班,轮流报告本书各章内容,让我迷上了这本口碑极佳的著作。作者用了行列式按行展开的方式推演出初等矩阵的行列式公式。
如果去研究院的图书馆借出一本内容丰富的矩阵理论书,只要找到矩阵行列式引理,就可以将所列论证搬来作为我文章手稿中的引理证明。但是我想该等式简单,证明无需外援。况且,外人不大容易借出馆藏图书,我也不想麻烦熟人陪跑一趟帮我借阅。于是我开始着手推出这个简洁漂亮的行列式等式,希望写出的证明也同样是简洁漂亮的。
其实我心中已经有了一个似是而非的处理手段。正如前述,我们只需考虑A = I的特例即可。一个如果不仔细推敲就有可能觉得全对的“证明”是这样的:把Rn视为一个内积空间,它的任意两个向量x和y的欧几里得内积定义为yTx。既然v是非零向量,在此内积下,它的“正交补空间”是Rn的(n – 1)维子空间,这个几何事实可以从三维空间中看得很清楚:在原点处,垂直于一条直线的所有向量组成的平面也与这条直线垂直。因而存在n - 1个线性无关的列向量v1, v2, …, vn-1,使得vTv1 = … = vTvn-1 = 0。故有
(I + uvT)vi = vi, i = 1, 2, …, n - 1。
换言之,1是矩阵I + uvT的特征值,v1, …, vn-1为其对应的线性无关的特征向量。此外,从(I + uvT)u = u + (vTu)u = (1 + vTu)u知,1 + vTu也是I + uvT的特征值,由“矩阵的行列式等于它的所有特征值的乘积”得,det (I + uvT) = 1…1(1 + vTu) = 1 + vTu。等式被证。
这个证明对吗?对于豪斯霍尔德矩阵I - 2uuT,上述论证过程全对,原因是该矩阵计入代数重数的特征值为n - 1个数1及不等于1的数-1,所以矩阵的行列式等于它们的积-1。然而对一般的情形,只要问一个问题,就可以看出毛病出在哪里:若vTu = 0,因而1 + vTu 也是1怎么办?在这种情况下,u属于v的正交补空间,它也像v1, …, vn-1一样是对应于特征值1的特征向量,但却是它们的一个线性组合。事实上,当u和v相互正交时,1是I + uvT的唯一特征值,但它的代数重数是n,而几何重数则为n - 1,因而行列式等式依然为真。不过,这需要严格的证明。
自然,当u与v不彼此正交时,由于I + uvT有两个相异的特征值1和1 + vTu,前者的代数重数和几何重数都为n - 1,后者的代数重数和几何重数均为1,上面关于行列式等式的证明绝对正确。然而对于vTu = 0的例外情形,可以运用逼近的手段和连续的概念来克服出现的困难:存在一个向量序列{uk},使得对所有的k都有vTuk ≠ 0并且成立。然后,对每一个k,根据已证的等式,有det (I + ukvT) = 1 + vTuk。在此等式两端取k趋向于无穷大时的极限,因为行列式是其对应矩阵元素的连续函数,就得到同样的等式
det (I + uvT) = 1 + vTu。


广义高斯行变换


终于,我们获得了一个无懈可击的正确证明,然而,它的弱点也是很显然的:证明太长,因而对读者的耐心是个考验。可以给出矩阵行列式引理的一个较短的证明,它不必像上面那样两种情形分而治之,但它需要的是关于2×2分块矩阵行列式的一个经典公式和同一个分块矩阵的块下三角矩阵和块上三角矩阵分解:



这两个等式本质上都来自关于分块矩阵的广义高斯行变换。
“广义高斯行变换”是通常的高斯消去法中行变换的推广。高斯消去法的目的是将线性方程组的系数矩阵通过初等行变换转变成一个上三角矩阵,然后利用回代法解出与原方程组等价的线性方程组的解。比如说,如果要解二元一次方程组3x - 2y = 1和2x + y = 3。高斯消去法用-2/3乘上第一个方程,然后再加到第二个方程,结果消去x:(7/3)y = 7/3,解得y = 1,将y的值回代到第一个方程解得x = 1。高斯消去法的这个行变换的效果,相当于用其对应的变换矩阵(它由用同样的高斯行变换施加于单位矩阵而得到) 


乘以方程组的系数矩阵


由于变换矩阵的行列式等于1,故高斯行变换不改变矩阵的行列式。
广义高斯行变换与高斯行变换具有同样的思想,只不过它用于矩阵写成分块矩阵的场合。这时原始的消去法——通过一行而改变另一行的初等行变换,被推广成一次性通过几行而改变同样数目的另外几行的变换。换言之,原先的将某个数乘以某一行再加到另一行的高斯行变换,被提速到将某个块矩阵乘以分块矩阵的某一行后再加到另一行的广义高斯行变换,这又等价于用其对应的变换块矩阵(将同一变换用于分块的单位矩阵而得到)乘以被施加变换的那个分块矩阵。同样地,广义高斯行变换不改变原矩阵的行列式。正如通常的高斯行变换思想也可以用于矩阵的列运算上,自然也可以进行广义高斯列变换,只需把“将某个块矩阵乘以分块矩阵的某一行然后再加到另一行”的操作改为“将某块矩阵右乘分块矩阵的某一列然后再加到另一列”,其等价的矩阵乘积是将对应的变换块矩阵右乘被变换的分块矩阵,行列式依然是列变换的不变量。
好了,我们可以验证上面的等式(1)和(2)了。具体说来,对行列式等式(1)左端的分块矩阵,将u乘上第二行后再加到第一行,得到变换后的分块矩阵


而广义高斯行变换不改变矩阵的行列式,且结果所得的块下三角矩阵的行列式等于两个对角块子矩阵的行列式之积:det (A + uvT)  1 = det (A + uvT),故得等式(1)。等式(2)的最简单证明是运用分块矩阵的乘法规则直接将等式右端乘出来,就获得左端的矩阵,但这揭示不出躲藏在等式背后的思想来源。如果追溯此等式的源头,那就是将-vTA-1乘以等式左端分块矩阵的第一行后再加到第二行,该广义高斯行变换的结果就是等式右端乘积中的后一个因子矩阵。这个行变换相当于用“变换矩阵”


乘以被施加该变换的矩阵,而此变换矩阵的逆矩阵就是将它表达式中的那个负号去掉后的结果。因此上述的分块矩阵的分解等式(2)得证。只要取矩阵等式(2)两端的行列式,再用到行列式等式(1),矩阵行列式引理的证明就算大功告成了。

还能更简洁吗?


读者可以感觉到上述关于矩阵行列式引理的第二个证明比较精炼,因为只用了两个公式,两步到位就完成了任务。然而,有没有只用到一个等式就可以一步到位的证明呢?这也是当年我在北京的访问学者办公室里对自己的提问。
其实那时我的头脑里并没有上面的公式(1)和(2),利用正交概念的“不完整证明”却是学过内积空间的人容易想到的一个证法。然而,我是知道广义高斯行列变换技巧的,我正是坐在办公桌前试图用此法一步到位地证明det (I + uvT) = 1 + vTu。我发现,如果将行向量-vT右乘分块矩阵

的第二列,然后加到第一列,结果是分块矩阵


写成矩阵乘积的形式,上述广义高斯列变换等价于等式关系

如果对上式右端的分块矩阵进行如下的广义高斯行变换:将行向量vT乘以第一行后再加到第二行,得到与此运算等价的矩阵乘积

将上面的两个等式结合起来,就催生了如下的块矩阵分解

两边取行列式,左端三个因子矩阵均为块三角矩阵,各自的行列式分别为1, det (I + uvT)和1,右端的块上三角矩阵的行列式等于1 + vTu。这就证明了当A = I时的矩阵行列式引理。所以我在论文中一步到位地用上述的矩阵分解证实了这个预备结果。当然,我在当时以及后来的多年间不知道它已经被人命名为“矩阵行列式引理”。有意思的是我当时也把它写成了引理的形式,因为它的任务是帮助我证明论文中的主要定理。
那么,论文的主要定理是什么呢?它的内容是:如果u是A对应于特征值λ1的一个特征向量,那么矩阵A + uvT的计入代数重数的特征值为λ1 + vTu, λ2, …, λn,其中λ1, λ2, …, λn是A计入代数重数的特征值。其证明简短的关键是利用了矩阵行列式引理,获得A + uvT的特征多项式在复数域上的因式分解[λ - (λ1 + vTu)](λ - λ2) …(λ - λn)。
作为这个矩阵谱秩-1摄动定理的直接应用,谷歌矩阵G = αS + (1 - α)evT计入代数重数的特征值为1, αλ2, …, αλn,其中1, λ2, …, λn为原始谷歌矩阵S计入代数重数的特征值。这也连带确定了我那时刚刚认识的谷歌矩阵的谱。
然而,让我始料未及的是,新定理的另一个直接应用却导致了关于非负矩阵的Perron-Frobenius理论里,一个对正矩阵最大特征值代数重数断言的直接证明,这个新证明比我到那时为止在有关非负矩阵的书中见过的证明要短得多。这个断言是:正的方阵的谱半径,即所有特征值的最大绝对值(在非负矩阵理论里称为最大特征值,理由是非负矩阵的谱半径总是一个特征值),是代数重数为1的特征值。
书本里给出的这个正矩阵最大特征值为特征多项式简单零点的结果,证明一般很长,有的甚至还借来其他学科的知识。例如,在剑桥大学出版社1997年出版的R. B. Bapat和T. E. S. Raghavan合著的书Nonnegative Matrices and Applications(《非负矩阵及其应用》)中的定理1.4.4(v)的证明,用到了来自博弈论(game theory)的推理;R. Horn和C. R. Johnson于1985年经同一出版社推出的教科书Matrix Analysis(《矩阵分析》),用Schur三角化定理证明了定理8.2.10;在H. Minc的1988年专著Nonnegative Matrices(《非负矩阵》)中,定理4.3的证明是基于微分的思路。这些证明似乎都既不简单,也不简短。
那时,我和我的合作者根据我们多年来对遍历理论中一类正算子数值分析的研究实践,准备写一本英文书《非负矩阵、正算子及其应用》(Nonnegative Matrices, Positive Operators, and Applications)。我一直比较关心有关非负矩阵尤其是随机矩阵的性质,盖因计算遍历理论里著名的乌拉姆方法以及我在博士学位论文中构造的高阶马尔可夫有限维逼近方法,采用的各种映到有限维函数空间上的逼近算子,在密度函数基底下的表示都是随机矩阵。所以,在受谷歌矩阵吸引,碰巧证明出了一个谱摄动定理后,我就好奇它能不能用于简化上一段提到的关于正矩阵最大特征值代数重数好性质的复杂证明。
果然,新结果多给了我一个惊喜。作为秩-1谱摄动定理的最后应用例子,我在那篇文章中提供了上述简单零点结论的一个短证明:由正矩阵的Perron定理,(i) A的谱半径r(A)是A的几何重数为1的正特征值;(ii) lim k → ∞ [r(A)-1A]k = xyT,其中x和yT分别是A对应于特征值r(A)的已被标准化的正特征向量和左正特征向量,即A x = r(A)x和yTA = r(A)yT,x > 0和y > 0,且yTx = 1;(iii) r(A)不是矩阵A - r(A)xyT的特征值。如果记r(A), λ2, …, λn为A计入代数重数的特征值,则对于u = -r(A)x和v = y,秩-1谱摄动定理的条件满足,故A - r(A)xyT计入代数重数的特征值为μ, λ2, …, λn,其中μ = r(A) + yT[-r(A)x] = r(A) - r(A) = 0。从而,既然r(A) > 0,那么对所有的i = 2, …, n都有r(A) ≠ λi。这就证明了r(A)是A的特征多项式的简单零点。这个证明自然也被写进了我们的书中,放在关于不可约非负矩阵最大特征值是特征多项式简单零点的那个定理之后;2009年新加坡世界科学出版社出版了它。

尾声


十六年的光阴瞬息过去,几年前我注意到,我与合作者这篇2007年的论文的引用次数,压过了我们1996年发表的一篇计算遍历理论领域的文章,当上了我所有学术论文的“引用数冠军”。我当时以为或许是因为论文中的主要定理应用广泛而荣幸被引。然而,借审稿机会我才获悉,文章的引理证明被维基百科的条目选上,论文是由于这个矩阵行列式引理及其极简证明才受到研究者关注。据说有人统计过,全世界浏览量最大的前十名网页中,维基百科位居其一。
大数学家外尔 (Hermann Weyl,1885-1955) 曾有一句名言:“我的工作总是设法将真与美统一起来,但如果二者只能择其一,我通常会选择美。”人们常说“简单就是美”。在数学中,美的定理、美的证明,特征之一是“清楚简洁”。精炼的证明读之令人陶醉,如“根号2非有理数”及“素数无穷多”的论证不能再短,所以,它们既被爱戴数学美的哈代 (Godfrey Harold Hardy,1877-1947) 写进了脍炙人口的A Mathematician’s Apology(《一个数学家的辩白》),也被收进了再版多次的Proofs from THE BOOK(《数学天书中的证明》)。矩阵行列式引理的最短证明像引理本身一样简洁清晰,人们同时欣赏了公式之雅和推理之妙。在维基百科的数学条目里,我们的的确确体会到了数学美!
写于2023年11月12日星期日美国哈蒂斯堡夏日山庄

出品:科普中国



相关阅读

1  怎样迭代求解线性方程组?

2  再谈迭代:今天不关心混沌与周期,我只想计算

3  这么说迭代,你一定能懂

4  牛顿迭代法传奇(上):张冠李戴的命名

5  牛顿迭代法传奇(下):意犹未尽,柳暗花明


近期推荐

1  小孩子就能作出的结构,却困扰了数学界整整50年

2  理论物理学家米格达尔回忆录:苏联物理学的失乐园

3  数学世界的“大卫王”:普通娃如何成为数学翘楚

4  有机化学界的一场“华山论剑”,结下了丰硕的科学和精神果实

5  有些癌症筛查,无用甚至有害


特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“,可查阅不同主题系列科普文章。

2. 『返朴』提供按月检索文章功能。关注公众号,回复四位数组成的年份+月份,如“1903”,可获取2019年3月的文章索引,以此类推。

版权说明:欢迎个人转发,任何形式的媒体或机构未经授权,不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。


找不到《返朴》了?快加星标!!



长按下方图片关注「返朴」,查看更多历史文章

微信实行乱序推送,常点“在看”,可防失联
继续滑动看下一个
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存