伟大的数学家赫尔曼·韦伊尔(1885-1955)曾说过:“我的工作总是试图将真与美统一起来,但如果只能在二者之间选择,我通常会选择美。”在数学中,美的定理和美的证明的特点之一就是“清晰、简洁”。本文评述了作者16年前的一篇论文中“矩阵行列式引理”的一个简洁优美的证明,并介绍了线性代数中分块矩阵使用的高斯列与列变换技巧。
满足“矩阵行列式引理”
半年前,我看了一篇提交给《应用数学快报》的文章。在这篇关于迭代法的贡献中,有一段话让我很感兴趣:“在提供新迭代格式的收敛性之前,我们推广了[4]的所谓矩阵确定性引理。对于更一般的秩r修正:“(在证明新迭代格式的收敛性之前,我们将[4]中所谓的矩阵行列式引理推广到更一般的秩r修正)。参考文献[4]是16年前我和我的合作者在同一杂志上发表的论文《秩1更新矩阵的特征值及其应用》。
引起我兴趣的是“矩阵行列式引理”这个术语。按照作者的口气,似乎我们的文章给出了这个引理,甚至给它起了名字。但是,我对这个名字一无所知。那天是我第一次看到。我真的很无知!
好在现在信息发达,网上查询信息很方便。我在谷歌搜索中输入短语矩阵行列式引理,电脑屏幕上弹出的第一条信息就是维基百科的“矩阵行列式引理”词条。其内容的第一段是:“在数学中,尤其是线性代数中,矩阵行列式引理计算可逆矩阵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-1 uvT)]= det(A)det(I+A-1 uvT),
其中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的特殊情况下,这是温斯坦-阿伦斯扎因恒等式:
检测器(铟+紫外线)=检测器(铟+ VTU).
然而,条目的作者可能不知道,在2007年发表的另一篇论文《某些扰动矩阵的特征多项式》(《某些扰动矩阵的特征多项式》)中,我们给出了所谓的Varnstam-Aronzaine恒等式的进一步证明:我们直接将用于秩1校正矩阵的特殊矩阵分解公式推广到
然后求两边的行列式得到结果。在维基百科的词条“Weinstein-Aronszajn恒等式”中,证明这个恒等式的技巧是关于2×2分块矩阵的两个经典行列式方程的,所以没有上面的证明那么简洁,缺少一点美感。不过这可能是2007年新证明出来之前最标准最经济的证明之一了。
这就是矩阵行列式引理的基本内容及其在维基百科中的推广。回到我半年前在复习的那篇文章,它的第一个定理是将矩阵行列式引理推广到上面已经证明的一般情况,但只考虑满足本文要求的m = n的特例。作者证明这个定理的思路还是传统的,就是通过一个经典的行列式方程。
以及上式左端2×2分块矩阵的三矩阵分解,然后取行列式成功。
没想到16年前受到Google Matrix的启发,想出了矩阵分解来讨论相关的数学问题,被维基百科词条采纳为“矩阵行列式引理”的标准证明。这让我想起当年写这篇数学随笔的一些细节,我把它记录在这里,作为我当年追求简单与美好的一个回顾。顺便也和读者分享一下线性代数中分块矩阵用到的高斯列与列变换技巧。
纸是怎么炼成的?
那一年和前十年一样,我如期参观了中科院数学与系统科学研究所。我和我的合作者在计算遍历理论领域合作多年,写了很多研究论文,发表了一篇中文合著。这一次,我的合作者告诉我,“谷歌矩阵”这个数学领域的新生事物正在引起应用和计算数学家的关注,因为谷歌在信息搜索引擎出现后不到十年就取得了巨大的商业成功,尤其是它在“PageRank”算法中的核心地位。他认为也许我们也应该“注意”。
我接受了他的好建议,于是开始阅读相关文献,了解了世界上最大的随机矩阵Google Matrix(即每行元素之和等于1的非负矩阵)的基本性质。Google Matrix实际上起源于一个根据所有网页相对重要性的概念定义的N行N列的随机矩阵S,称为原始Google Matrix,然后它与一个秩为1的“扰动矩阵”evT凸组合,其中E是所有N维分量为1的列向量,N维列向量V被标准化以满足vTe = 1。由此得到的Google矩阵G = αS+(1-α)evT不仅是一个随机矩阵,而且是一个正矩阵,即其中的每一个元素都是正数。这里的凸组合系数α选择在0.85的小邻域内。自然,实际的Google Matrix绝不是这么简单,可能是永远不会公开的商业秘密,但是Google曾经在其网站上声明,我们软件的核心是PageRank。
Google的网页搜索服务对客户的成本在于,它能有效快速地计算出满足等式πT= πTG的线向量(π*)T(即G的左特征向量),其所有分量给出了不同网页的“相对重要性排序”。计算方法是直接迭代法,即从一个标准化的初始行向量(π0)T开始,将矩阵G逐一乘以左,得到的迭代行向量序列{(π0)TGk}将趋于极限(π*)T,其收敛速度与G的第二大特征值有关。
Google矩阵形式上是一个主矩阵α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对应的特征向量。矩阵A+uvT经过秩1修正后的n个特征值有哪些,包含在代数重数中?线性代数中,所谓矩阵M的特征值μ的代数重数,是指复数域中特征多项式p(λ) = det (λI-M)的因式分解中因子λ-μ的幂。另一个与代数重数有关的自然数叫做几何重数。特征值μ的几何重数是由μ和0向量对应的所有特征向量组成的“特征值空区间”的维数。对于任何特征值,其代数重数总是大于或等于其几何重数。特别地,如果μ的代数重数是1,那么它的几何重数也是1,那么我们说,特征值μ是单的。
在没有领导监督的自由氛围中,在没有填写表格和报告的轻松环境中,研究人员最有可能提出新颖的想法。坐在一间朝阳的面向访问学者的办公室里,想了想,突然开了窍,选择了一条路线,试图推导出矩阵A+uvT在复数域中秩1修正后的特征多项式Det [λ I-(A+uvT)]的因式分解,以捕捉所有的特征值及其代数倍数。这个行列式所依据的矩阵可以写成(λI-A)-uvT,是矩阵λI-A的秩1修正,只要复λ不是矩阵A的特征值,λI-A就是我想要的可逆矩阵,因为我知道矩阵理论中有可逆矩阵的秩1修正矩阵的行列式公式, 其中在修正后的矩阵行列式和未修正的矩阵行列式之间建立了一种简单而美观的关系:如果m是n×n可逆矩阵,u和v是n维的列向量,那么det (m+uvt) =(。
因为上面的关系可以用来解决我自己提出的特征值摄动问题,所以我必须给出这个初步命题的证明。当然这种初等行列式方程早就是经典的结果了,我以前也见过。
霍姆德(1904-1993),美国著名的计算数学家,在1964年出版了一本很好的书《数值分析中的矩阵论》。他把复数域中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的代数重数特征值。证明简洁的关键是利用矩阵行列式引理得到复域[λ-(λ1+ vTu)](λ-λ2) …(λ-λn)中A+uvT的特征多项式的因式分解。
作为这个矩阵谱秩-1扰动定理的直接应用,代数重数中包含的Google矩阵G = αS+(1-α)evT的特征值为1,αλ2,…,αλn,其中1,λ2,…,λn是代数重数中包含的原Google矩阵S的特征值。这也印证了我当时刚认识的Google Matrix的光谱。
然而,令我惊讶的是,新定理的另一个直接应用导致了关于非负矩阵的Perron-Frobenius理论中关于正矩阵最大特征值的代数重数的断言的直接证明。这个新证明比我目前为止在有关非负矩阵的书籍中看到的证明要短得多。这个断言是,正方阵的谱半径,即所有特征值的最大绝对值(非负矩阵理论中称为最大特征值,因为非负矩阵的谱半径总是一个特征值),是代数重数为1的特征值。
书中给出的这个正矩阵的最大特征值是特征多项式简单零点的结果,证明一般都很长,有的甚至借用了其他学科的知识。比如剑桥大学出版社1997年R. B. Bapat和T. E. S. Raghavan出版的《非负矩阵及应用》一书中定理1.4.4(v)的证明,就使用了博弈论的推理;1985年,R. Horn和C. R. Johnson出版了同一出版社的教材《矩阵分析》,用Schur三角化定理证明了定理8.2.10。在h . Minc 1988年的专著《非负矩阵》中,定理4.3的证明是基于微分的思想。这些证明似乎都不简单或简短。
当时,我和我的合作者打算根据我们多年来对遍历理论中一类正算子的数值分析的研究和实践,写一本英文书《非负矩阵(正算子,和应用)》。我一直很关心非负矩阵,尤其是随机矩阵的性质。Cain计算的遍历理论中著名的ulam方法和我在博士论文中构造的高阶Markov有限维逼近方法,所有映射到有限维函数空的逼近算子都在密度函数的基础上表示为随机矩阵。
于是,被Google matrix吸引,我碰巧证明了一个谱扰动定理,很好奇是否可以用它来简化前段提到的正矩阵最大特征值的代数重数的良好性质的复杂证明。
果然,新的结果给了我一个惊喜。作为秩-1谱扰动定理的最后一个应用例子,我在那篇文章中提供了上述简单的零结论的一个简短证明:(i) A的谱半径r(A)I)几何重数为1的正特征值来自正矩阵的Perron定理;(ii) lim k → ∞[r(A)-1A]k= xyT,其中x和yT是对应于特征值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)。所以,既然r (a) >: 0,那么对于所有的i = 2,…,n,就有r (a) ≠ λi .这证明了r(A)是A的特征多项式的单零点.这个证明很自然地写进了我们的书里,在不可约非负矩阵的最大特征值是特征多项式的单零点的定理之后;它于2009年由新加坡世界科学出版社出版。
乐章结尾部
十六年很快就过去了。几年前,我注意到我与合作者的2007年论文的引用次数超过了1996年发表的一篇计算遍历理论领域的文章,成为我所有学术论文的“引用冠军”。我想也许是因为论文中的主要定理被广泛应用,所以我很荣幸被引用。但我查阅稿件得知,文章的引理证明是由维基百科选取的,论文因为这个矩阵行列式引理及其极简证明引起了研究者的关注。据说根据统计,维基百科位列全球访问量最大的10个网页。
伟大的数学家赫尔曼·韦勒(Hermann Weyl,1885-1955)曾有一句名言:“我的工作总是试图将真善美统一起来,但如果只能在二者之间选择,我通常会选择美。”人们常说“简单就是美”。在数学中,美的定理和美的证明的特点之一就是“清晰、简洁”。精致的校样读起来令人陶醉。比如“根号2是无理数”和“无限素数”的论点不能再短了。因此,它们被高德菲·哈罗德·哈代(1877-1947)写进了脍炙人口的《一个数学家的道歉》,并被收入其中。矩阵行列式引理的最短证明和引理本身一样简洁明了,人们既欣赏公式的优雅,又欣赏推理的巧妙。在维基百科的数学词条里,我们真正体会到了数学的美好!