返朴

从不动点到网页排序:非负矩阵的奥秘

一个实矩阵,只因所有元素都不小于零,就会拥有一些特别的性质。这些性质既能与拓扑学中的不动点联系起来,也会出现在网页排序和一个三角形迭代问题中。沿着佩隆与佛罗贝尼乌斯的工作,我们来看看这些性质从何而来。

本文收录于合集:数学课

撰文 | 丁玖(广州南方学院数学与统计学院教授)

从非负矩阵说起

非负矩阵,顾名思义,就是所有元素都是非负实数的矩阵。如果是个非负矩阵,这个性质常被写成一目了然的不等式形式。两个同型(行数和列数分别相同)的实矩阵和如果满足,则说前者大于或等于后者,记作。一个非负矩阵的行数可以不等于列数。不过,非负矩阵理论中最精彩的部分是关于非负方阵的谱定理,所以本文的主角是非负方阵。

如果要求一个非负矩阵的所有元素都是正数,那么这个矩阵就被称为正矩阵,写成。我们在之前的返朴文章《从抛物线到马鞍面,如何理解矩阵二次型?》中介绍过比“正矩阵”多了一个字的术语“正定矩阵”。尽管都有一个“正”字,这两种矩阵却完全“风马牛不相及”:实的阶正定矩阵的“正”意指二次型对所有维非零实向量,都取正数。正定矩阵可以携带负元素,比如主对角元均为且其他元素都是的二阶矩阵是正定的,却不是非负矩阵,更不要说是正矩阵了。另一方面,正矩阵不一定是正定矩阵,比如所有元素都是的二阶方阵是个奇异矩阵,因而不可能是正定矩阵。

非负矩阵的谱性质有哪些特别之处?在细细道来之前,我们先来回顾矩阵谱的概念。设为一个实数域或复数域上的阶方阵。如果存在一个复数和一个非零维复列向量,使得等式成立,那么被称为的一个特征值,而则被叫做对应于的一个特征向量。

根据线性方程组的解理论,复数是矩阵的特征值当且仅当是特征方程的一个根,其中记号表示行列式,是与同阶的单位矩阵。由于是复变元的次多项式(称为的特征多项式),代数基本定理推出,计入根的重数,阶矩阵的特征多项式有个根,因此恰好有个特征值,其重数称为该特征值的代数重数,而属于特征值的全部特征向量再添加零向量所构成的对应特征子空间(即矩阵的零空间)的维数称为的几何重数。每个特征值的几何重数总是小于或等于代数重数。

给定矩阵的所有特征值组成的集合称为的谱,通常记为,其中各特征值的模的最大值被叫作的谱半径,记作。

线性代数关于向量和矩阵的范数理论中有个基本事实:矩阵的谱半径小于或等于任一个由向量范数诱导出的矩阵范数。特别地,由向量的-范数诱导出的矩阵-范数有表达式

故有不等式。

一般而言,方阵的谱半径不一定是的特征值,尽管至少有一个特征值,它的模等于谱半径。一个简单例子是

它有两个彼此共轭的虚数特征值和,因此的谱半径,然而并非是的一个特征值。注意到这个阶非对称实矩阵不是非负矩阵。

这就引出了一个有趣的问题:非负矩阵的谱半径一定会是的一个特征值吗?如果答案为真,则我们可以把称为的最大特征值,因为此时的其他特征值的模都不比这个特征值的模来得更大。

从不动点到佩隆定理

然而,要回答这个问题,我们最好先把目光放在比非负矩阵稍稍加了一个“所有元素非零”额外条件的正矩阵上。对这类更为特殊的非负矩阵,我们将跟随一百二十年前还未进入而立之年的德国数学家佩隆(Oskar Perron,1880-1975),叙述年轻有为的他所建立的关于正矩阵的谱理论中的最重要结果。然而这里采用的证明方法却是后人从拓扑学中的大定理得到灵感的。

这条拓扑学定理属于荷兰数学家布劳威尔(Luitzen Egbertus Jan Brouwer,1881-1966)。它的内容是:将欧几里得空间内的一个非空有界闭凸子集映到自身的任意连续映射必有不动点。更详细地说,假设是的一个非空子集,满足条件:它当中的所有向量的个分量的绝对值都小于同一个正常数,并且中的任意一个收敛向量序列的极限属于,此外对中任意两个向量和,它们的凸组合也属于,其中是闭区间中的任意数。如果映射的个分量函数都是个自变量的连续函数,那么在中存在一点,它是的一个不动点,即。这个用途极为广泛的命题,标准名字是“布劳威尔不动点定理”。

当时,布劳威尔不动点定理以如下的面貌出现:将有界闭区间映到自身的连续函数一定有不动点。这本质上就是初等微积分里的“介值定理”,众所周知的证明方法是构造性的“二分法”。然而一旦维数大于一,这个经典的不动点定理的精髓由分析学进化到拓扑学,证明的难度也向上蹦跳了一个台阶。上世纪六十年代一位微分拓扑学家的漂亮反证法,十年后引导了一名因修课而得知证明思想的博士研究生李天岩(1945-2020)给出了布劳威尔不动点定理的构造性证明,由此开创出计算数学的一个新领域——现代同伦延拓法。

布劳威尔不动点定理中关于定义域的三个条件,对不动点的存在性缺一不可。若定义域是非凸有界闭集,反例是将两个闭区间的并集映到自身的变号函数;若定义域是无界闭凸集,反例是将实数轴映到自身的平移函数;若定义域是非闭有界凸集,反例是将开区间映到自身的压缩函数。最后若将有界闭凸集映到自身的映射不连续,反例是定义在上的函数

下面,我们叙述并巧用布劳威尔不动点定理来证明关于正矩阵的谱最令人啧啧称奇的性质。它是佩隆26岁时采集到的一朵数学鲜花。

佩隆定理. 设为一阶正矩阵,则它的谱半径是个正数,并且是的特征值,且对应的特征子空间由一正向量张成,因而维数等于。

证明. 我们先从如下观察入手,以请出布劳威尔不动点定理这位高手。对于给定的正矩阵,假若存在一个复特征值和一个对应的非负特征向量,则对等式两边左乘分量全为的行向量,得。数的直观意义是向量的所有分量之和。因为非负向量不为零,;又因为为正矩阵,,由此推得。这样,作为两个正数之商,

上面的表达式给了我们灵感构造一个可以运用布劳威尔不动点定理的映射。

如果定义一个非线性映射,它把非零非负向量映到正向量

则是的不动点:

显然在定义域上处处连续。注意到当满足时,如上定义的满足同样的等式,而集合是欧几里得空间中的标准单纯形(例如当时,它是的第一卦限内顶点分别是的那个等边三角形)。很容易验证:作为的非空子集,是有界的、闭的、凸的。此外,,且当时,。

综上所述,由公式(1)定义的映射

符合布劳威尔不动点定理的全部假设,因此存在向量使得。换言之,。既然,非负向量不为零,故它是对应于的一个特征向量。因为,有,所以特征值,且隐含

即是对应于正特征值的一个正特征向量。

把如上结果用于正矩阵,便存在正数和正向量使得。从等式以及,可知。

现在证明:等于的谱半径。设对复数和非零复向量有。记为将的各分量改成其模而得到的对应于的非负向量。因为任意非零数乘以特征向量依然是对应于同一个特征值的特征向量,故可将标准化,则得到。这时有。用正向量左乘该不等式的两端,便得。因为,所以。这就证明了。

最后证明,如果,其中不为零,那么是的一个常数倍。倘若不然,则和线性无关。由于为正向量,存在实数使得为一非零非负向量,且至少有个分量等于零。然后,在的两边同除以,得

这导致了矛盾。所以必定是的某个常数倍。定理的证明完毕。

上述定理马上推出下列结论:

推论1. 设是一个阶正矩阵,则存在唯一的正向量,满足

上式中的“归一化”的正特征向量称为的佩隆向量。

允许零元素之后

利用数学分析中的常用技巧——极限法,借助于如上的正矩阵谱定理,就不难获得关于非负方阵的下述推论;这也回答了文章开头提出的问题。

推论2. 设是一个阶非负方阵,则它的谱半径是的特征值,并且对应有一个非负的特征向量。

证明. 对的所有零元素加上同一个正数,将如此扰动后获得的正矩阵记为。令为的佩隆向量,则对所有都成立。这些向量都属于有界闭集,根据微积分中的魏尔斯特拉斯列紧定理,存在收敛于的单调递减正数数列,使得。极限步骤进一步推出。由此可知为一非零向量。又因为矩阵序列是单调递减的,即,且以为其下界,根据下文引理1将要证明的谱半径单调性,正数序列也是单调递减的。所以初等微积分中的单调收敛定理保证极限

存在。对所有都成立的不等式推出极限。在恒等式

两边求极限得,即是的一个非负特征值,并以为一对应的非负特征向量。由此可见。已证的两个不等式和隐含等式。这就完成了推论2的证明。

上述证明中用到的一个谱半径比较结果可以写成下列引理:

引理1. 若阶实方阵和满足,则。

证明. 这个结论可以用计算谱半径的经典公式和一个数学常识来证明。阶实矩阵的谱半径,其中是上的任一向量范数诱导出的矩阵空间上的矩阵范数。这里取矩阵的-范数最方便,因推出对所有都有,由此。不等式两边求当时的极限,便得。证毕。

正矩阵和一般非负矩阵都以谱半径作为最大特征值。但在相应特征向量的正性与特征值的重数上,两者却可能有“天壤之别”。细看佩隆定理,正矩阵的谱半径所对应的特征子空间是一维的,即这个最大特征值的几何重数为。此外它带出了漂亮的佩隆向量这一处处为正的标准特征向量。这里没有提及的另一个事实是:正矩阵谱半径的代数重数也是,即它是特征多项式的单根。然而,这一事实在许多标准的非负矩阵教科书中,证明起来却令人惊讶地繁琐,甚至需要其他学科概念的帮助。本文作者在合著《非负矩阵、正算子及其应用》(Jiu Ding and Aihui Zhou,Nonnegative Matrices, Positive Operators, and Applications, World Scientific, 2009)中,运用了他们当时新近建立的矩阵秩矫正谱扰动定理,给出了一个比较简洁的证明(见该书定理2.1.2)。

再瞧瞧推论2,除了谱半径是特征值并携带了一个非负特征向量这个好消息外,似乎听不到其他鼓舞人心的新闻了。举个例子,零矩阵就是一个最简单的非负矩阵,它的所有特征值都是,谱半径自然也是,而每一个非零向量都是它所对应的特征向量。看来,要想非负矩阵“共享”正矩阵如上所述的优良的谱性质,必须对它们的结构施加一定的限制。这就是在年轻数学家佩隆提出他的正矩阵谱理论五年后的1912年,他的德国同胞、资深数学家佛罗贝尼乌斯(Ferdinand Georg Frobenius,1849-1917)所做出的重要推广。

佛罗贝尼乌斯的接力

对佩隆定理的这个直接推广,处理的非负矩阵属于所谓的“不可约矩阵”的范畴。它的否定词组可约矩阵是指这样的方阵,如果将它的所有行和所有列按照同等的先后顺序重新排列,结果在矩阵的左下角出现了一个行数加上列数等于原先方阵阶数的零矩阵。用数学语言来定义这个概念,就是:一个阶方阵被称为是可约的,如果存在一个阶排列矩阵,使得

其中和都是方阵。排列矩阵是将单位矩阵的行重新排列后的产物,它的转置也是排列矩阵。不难验证,排列矩阵左乘矩阵,其结果是将被乘矩阵的行按照单位矩阵变成排列矩阵的方式重新排列;用同一方式排列矩阵的列相当于将之前的排列矩阵的转置右乘该矩阵。

如果方阵不是可约的,则称它为不可约矩阵。以下关于不可约矩阵的讨论均设。不可约矩阵具有如下的好性质。因为它将被用来证明后面的主要命题——佛罗贝尼乌斯定理,所以把它写成一个引理。

引理2. 设阶非负矩阵是不可约的,则是正矩阵。

证明. 对,令为阶单位矩阵的第列,它除了第个分量为非零数外,其余的分量均为。考虑向量。因为,所以,故。特别地,的第个分量继承了第个分量的正性。我们给出断言:由于是不可约矩阵,向量一定有第个分量大于,其中,这样的第个分量也大于;也就是说经过的作用后,结果向量的正分量的个数比至少多一。

用反证法证明如上断言较易。倘若不然,则的所有指标不等于的分量均是。这时的第个分量是个非负数,其余分量都为。另一方面,恰恰等于的第列。如果我们将的第行和第行对调,再对调所得矩阵的第列和第列,其结果是(2)式所示的块上三角矩阵,其中的零矩阵块是,这意味着是可约矩阵,与假设矛盾。举个例子,阶矩阵

是可约的,因为依次互换它的第一行和第三行及第一列和第三列,结果是

由此可见,的某个指标非的分量为正数。因此上述断言为真。这样保证了非负向量至少有两个分量为正。

如上推理的思想实际上指出了更一般的结论:任给尚有零分量的非零非负向量,向量的正分量个数比的正分量个数至少多一。这样一来,从开始,依次左乘,至多经过步后,就得到一个正向量。乘上正向量自然还是正向量,所以最终得到:,即矩阵的第列大于。由于从取到,便有结论:是正矩阵。引理2得证。

现在叙述并证明佛罗贝尼乌斯对佩隆定理从正矩阵到不可约非负矩阵的直接推广。

佛罗贝尼乌斯定理. 设为一阶不可约非负矩阵。则它的谱半径是个正数,并且是的特征值,且对应的特征子空间由一正向量张成,因而维数等于。

证明. 由前面关于一般非负矩阵的结论,是的特征值,且对应于一个非负特征向量。因为,

由引理2,,推出。从而

由此得到。这就证明了的谱半径为正特征值且对应于一个正的特征向量。同样的结论用于得:具有对应于特征值的正的左特征向量,即。证明定理最后一结论即谱半径的几何重数为,与对正矩阵情形时的论证如出一辙,不再重复。证毕。

从1907年的佩隆到1912年的佛罗贝尼乌斯,这一对相差31岁的新老德意志数学家以五年之隔,接力棒似地分别挖掘出正矩阵和不可约非负矩阵的一系列谱性质,形成了矩阵理论中的一个有机整体,如今统称为“非负矩阵的佩隆-佛罗贝尼乌斯理论”,本文介绍的两个定理是这个理论中最经典的结果。

佩隆和佛罗贝尼乌斯,像他们那个时代的许多数学家一样,在很多领域留下足迹,不像今日许多数学家那么“只专一行”。佩隆的主要研究领域是常微分方程和偏微分方程,一项著名工作是对椭圆型偏微分方程的狄利克雷问题提出的佩隆方法。他对连分数也素有研究,写了一部百科全书式的著作。对自然数集合,他引入了一个有趣的“佩隆悖论”:设为最大的正整数。若,则,这与的定义相矛盾。因此,。这个趣例提醒我们:未经论证就假定优化问题存在解,可能会导出荒唐的结论。

至于佛罗贝尼乌斯,在数学上留下的足迹就更多了。他最有名的工作位于椭圆函数、微分方程、数论和群论。在逼近论,他对后来称为帕德逼近的一类有理逼近作出了早期的重要贡献;这一名称来自法国数学家帕德(Henri Padé,1863-1953)。在线性代数,他给出了关于矩阵特征多项式的凯莱-哈密顿定理的第一个完整证明。

有趣的是,尽管非负矩阵的佩隆-佛罗贝尼乌斯理论在他们各自的学术履历表上都不是最耀眼的光点,这个理论通过谷歌创始人发明的“网页排序”极大地改变了当今世界。鉴于这两个德国人对非负矩阵(可视为欧几里得空间上的有穷维正算子)理论的开创性贡献,在现代遍历理论中起着中心作用的一类无穷维正算子——与给定非线性自映射相对应的“转移算子”,尽管与他们没什么关联,却也被冠以“佛罗贝尼乌斯-佩隆算子”之名。命名者是现代学科非线性分析的开创者之一、波兰裔美国数学家和氢弹之父乌拉姆(Stanislaw Ulam,1909-1984)。他在1960年出版的名著A Collection of Mathematical Problems(《数学问题集》)中提出这一名称,原因之一是该线性算子继承了不少非负矩阵的优点。他在书中提出的逼近佛罗贝尼乌斯-佩隆算子的第一个数值方法,本质上是用一类保结构的非负矩阵来近似无穷维正算子。受乌拉姆方法指引,本文作者写出了博士论文,并在“计算遍历理论”子学科中迄今耕耘了三十余年。

随机矩阵的用武之地

提到“概率”,人们就会想到介乎于和之间的一个实数,它所表达的是某个可能发生的事件的可能性的数值量化。任何事件的概率总是非负数,有个基本事件的样本空间上的概率分布可用“概率向量”表示,其中所有的属于区间,加起来等于。这就给出了一个的非负矩阵。由此可以想象,概率论中到处都有非负矩阵施展拳脚的活动场所,如同分析力学的疆场中到处弥漫着微分方程的硝烟。

确实如此,在属于概率论大范畴的随机过程理论中,比如更具体一点的马尔科夫链,所谓的“转移矩阵”就是满足某个额外条件的非负方阵,它的第行第列元素是从状态转入状态的概率。由于每个状态在下一阶段都要进入所有可能状态中的某一个,这就给出了转移矩阵必须满足的额外条件:矩阵的每行元素加起来都等于。这样的矩阵在各类应用领域实在是太重要了,必须起个学名,叫“随机矩阵”。顾名思义,它与随机过程有着紧密的联系。

如果读者还没有碰到过随机矩阵,但是曾经用过谷歌搜索,实际上你早就隐式地体验过了随机矩阵的厉害之处,因为谷歌公司早期赖以“发家致富”的一大本钱就是用来定义网页排序向量的“谷歌矩阵”;这是一个规模极其庞大的随机矩阵!本文作者与合作者曾于2026年的国际数学日在《知识分子》上登过文章《让谷歌横空出世的世界最大矩阵》,科普了谷歌矩阵用于网页排序的数学原理。

从随机矩阵的定义立马知道,非负方阵为随机矩阵当且仅当。此时,已是的特征值,且以为一对应的正特征向量。由于和有相同的特征值,。又因为是随机矩阵,,故。换句话说,随机矩阵的所有特征值的模不大于其最大特征值。

然而,如果随机矩阵是可约的,则它的最大特征值不能保证是单重的。这里不深入讨论特征子空间和左特征子空间的结构。另一方面,尽管从上面关于一般非负矩阵的推论2可知,随机矩阵带有非负的左特征向量:,但得益于的特殊结构,可以再次借用光辉的布劳威尔不动点定理,给出该结论的直接而简单的如下证明:

如前一样定义有界闭凸集。任给向量,有且,即。由布劳威尔不动点定理,存在满足,或写成。因为非零且分量之和为,它是对应于谱半径的归一化的非负左特征向量。把看作概率分布,等式意味着经过一次状态转移,分布保持不变。这样的分布称为平稳分布。

如果一个随机矩阵的每一列元素加起来也等于,则称它为双随机矩阵。这时是它的最大特征值所对应的特征向量和左特征向量。前面定义可约矩阵时用到的排列矩阵就是双随机矩阵的佳例,并且极易判定,它们的凸组合也是双随机矩阵。然而,更令人兴奋的是其“逆命题”:任意双随机矩阵都可以表示为同阶排列矩阵的凸组合。用凸集的语言说,给定阶数的所有双随机矩阵组成的集合,其极点恰好是同阶数的排列矩阵。这后一个断言是由著名的美国父子数学家中的儿子伯克霍夫(Garrett Birkhoff,1911-1996)于1946年证明的。

三角形会变成什么样

如同随机矩阵,双随机矩阵有数不清的应用。在本文最后,我们将它用于三角形的迭代。取一三角形,作它的内切圆,由三个对应切点连接成的三角形记为,其中是上的切点,其余类推。再作的内切圆,三切点构成三角形。以此类推,得一三角形序列。试问:这些三角形的形状最终会是怎样?

三角形的形状决定于它的三个内角。若当前三角形的三个内角为、、,运用中学平面几何,不难验证:下一三角形的对应内角为,其余两角同理。因此,之后的三角形以三内角作为分量的维列向量等于双随机矩阵

乘以当前的三角形以三内角作为分量的维列向量。这样,从初始三角形开始迭代步后得到的三角形的三内角列向量,就是上述矩阵的次方乘以初始三角形的三内角列向量。

所以,问题归结于极限是否存在?如果存在,极限为何?本文所讲的知识不能回答这个问题。随机矩阵的幂次的极限问题将留待在下一篇文章中细表。这里先给出答案:

因此,三角形三内角向量最终趋向于。换言之,无论初始三角形的形状如何,上述迭代三角形序列的最终形状是等边三角形。

致谢.感谢周舒义编辑的认真修改与编辑,使得数学表述更为严格;由于他的把关,初稿中的几处误写得以改正。

图片

相关阅读

图片

1.微小扰动下的变与不变:矩阵求逆是连续运算吗?

2.一个矩阵,怎样把圆拉成椭圆?

3.比特征多项式更触及灵魂:矩阵的最小多项式

4.矩阵的若尔当标准型

5.从抛物线到马鞍面,如何理解矩阵二次型?

图片

近期推荐

图片

1.一个神话版的鸡兔同笼问题,竟蕴含着深刻的前沿物理

2.AI时代,什么才是真正属于人类的数学?

3.为什么越来越多科研基金,开始用抽签决定谁拿经费?

4.专访张寿武、袁新意:一篇被拒稿的论文,如何长成一套受欢迎的奠基性理论

5.王虹、邓煜和北大数学:顶尖人才的成长需要怎样的土壤?

特 别 提 示

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

2. 投稿、转载、应聘、商务合作等,皆可联系:[email protected] 

版权说明:欢迎个人转发,任何形式的媒体或机构未经授权,不得转载和摘编。

Image

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

Image
微信实行乱序推送,常点“在看”,可防失联
Image