让谷歌横空出世的世界最大矩阵

图源：pixabay

撰文 ｜丁玖 朱慧坚（广州南方学院）

1998年9月4日，两个25周岁的年轻小伙拉里·佩奇(Larry Page，生于1973年3月26日)和谢尔盖·布林（Sergey Brin，生于1973年8月21日）在加利福尼亚州旧金山湾区圣马特奥（San Mateo）县的城市门洛帕克（Menlo Park）提交了谷歌公司的注册文件。这个小城仅有三万多居民，南面的近邻是斯坦福大学，而他们正在那里攻读计算机科学系的博士学位。

他们创办的这家公司，四分之一个世纪后，其“谷歌搜索”成了全球访问量最高的两个网站之一。佩奇和布林最初将他们开辟的新搜索引擎昵称为“背部按摩（BackRub）”，因为该系统会检查反向链接来评估网站的重要性。最终，他们将名称改为Google，然而这是对古戈尔（googol）一词的错误拼写。古戈尔是一个巨大的数字10100（1后面跟着100个零），选择这个数字是为了表明该搜索引擎旨在提供大量信息。不过，直到今天，全世界的网页个数还远远低于这个已经超过宇宙所有原子个数的大数；或许永远也达不到。

古戈尔由美国哥伦比亚大学数学系教授爱德华·卡斯纳（Edward Kasner，1878-1955）的侄子、年仅9岁的米尔顿·西罗塔（Milton Sirotta）创造，用来表示一个难以想象的大数。卡斯纳在其1940年出版的《数学与想象力》一书中推广了古戈尔的概念，它形象地展示了大数与无穷之间的尺度，想必谷歌的创始人受此启发，给他们的搜索引擎新生儿起了这个拼错了一个字母的名字。顺便一提，卡斯纳最杰出的弟子是首届菲尔兹奖的两名获奖者之一、美国数学家杰西·道格拉斯（Jesse Douglas，1897-1965）。

无论佩奇还是布林，创办公司后都没有待在世界名校斯坦福美丽的校园，稳稳当当地坚持到最后，以获一纸博士证书。他们最终的学位——硕士——仍然高于年长他们18岁的比尔·盖茨（Bill Gates，1955-）；后者入学哈佛大学读本科两年后毅然退学，与合作伙伴开创了微软公司，开启了他一生的辉煌事业。佩奇和布林共同创办的公司——谷歌——同样也成了本世纪全世界最著名的高科技公司之一。没有追求学位圆满的他们三人，后来都被选为美国国家工程院院士。

佩奇和布林都有犹太血统。两人中，年轻半岁的布林有个数学家爸爸，佩奇的父亲则是计算机科学家。布林之父米哈伊·布林（MihailBrin，1947-）是个国际知名的俄罗斯纯粹数学家，专长为动力系统与黎曼几何，本科毕业于莫斯科大学，博士导师为苏联动力系统大家德米特里·阿诺索夫（Dmitri Anosov（1936-2014）和阿纳托尔·诺克（Anatole Katok，1944-2018）。布林教授在普林斯顿大学数学系编辑的纯数学国际顶尖杂志《数学年刊》上发表过三篇论文，也出版过书籍，如与他后来的马里兰大学同事合著的《动力系统引论》，2015年由剑桥大学出版社推出。

小布林6岁时随全家从苏联移民到美国。1990年他追随父亲的脚步跨进了马里兰大学，不过，父亲是数学系的教授，他则在数学系和计算机科学系读本科。三年后，他以数学与计算机科学双专业荣誉毕业生的优异成绩获得学士学位。马里兰大学数学系一直引以自豪的另一个本科毕业生是菲尔兹奖获得者查尔斯·费弗曼（Charles Fefferman，1949-），他17岁就获得数学与物理学的双学位，于普林斯顿大学获得数学博士后，22岁时成为芝加哥大学的正教授；他的同门博士师弟就是另一个菲尔兹奖获得者陶泽轩（Terence Tao，1975-）。

佩奇是个土生土长的美国人，他的父亲卡尔·佩奇（Carl Page Sr.，1938-1996）是笔者之一博士母校密歇根州立大学的计算机科学教授。老佩奇博士毕业于密歇根州的首席大学、也是全美最负盛名的公立大学之一密歇根大学的计算机科学系，在其职业生涯中是美国人工智能研究的先驱之一。可惜佩奇教授英年早逝，未能像布林教授那样目睹了儿子成长为业界巨人。

小佩奇也步了父亲的后尘，一脚跨进密歇根大学的校门，父子俩成为这所被誉为“美国公立大学之母”的中西部巨无霸大学的先后校友。在父母的直接影响下，儿子6岁时就对电脑产生了兴趣，因为他可以“玩弄那些散落在周围的东西”——他父母留下的第一代个人电脑。他成为“小学里第一个用文字处理器交作业的孩子”。可以说他是在电脑配件的丛林中长大的，“熟能生巧”这一中文成语可以恰如其分地形容佩奇从儿童走向青年对计算机世界的痴迷程度。后来他说：“从小我就意识到自己想发明创造。所以我对科技和商业产生了兴趣。大概从12岁起，我就知道自己最终会创办一家公司。”

在密歇根州立大学所在地东兰辛高中毕业后，从1991年到1995年，佩奇在密歇根大学读计算机工程，以荣誉称号获得工程学士学位，然后进入西部学术重镇斯坦福大学攻读计算机科学博士学位，在他创业元年获得硕士学位。

在寻找论文选题时，佩奇考虑探索万维网的数学特性，将其链接结构理解为一个庞大的有向图。他的导师特里·维诺格拉德（Terry Winograd，1946-)鼓励他继续研究这个想法。2008年谷歌20周岁，佩奇以感恩之情回忆道：“这是我收到的最好建议。”

成功实现快速高效网页搜索的好想法，不仅得益于有深远眼光学术导师的好建议，还需要背景类似、志同道合、互补长短的合作伙伴，这对应用科学十分奏效。在斯坦福这个布满才华横溢年轻学者的校园内，同在计算机科学疆场习武的布林加入到佩奇的行列，两人结伴开始了对网页搜索引擎的创新研究。卓有成效的共同努力导致“网页排序（PageRank）”这个互联网史上具有里程碑意义的新颖概念和术语的诞生。

在英文的语义下，两个单词的无空格组合PageRank可以有两层含义；其一是与实施对象相关的如上翻译“网页排序”，其二是“佩奇排序”，理由为Page是佩奇的姓。事实上，“PageRank”这个名字是个双关语，既指网页排名算法，也指其开发者佩奇。该算法最初是作为一种基于链接流行度对搜索结果进行排序的系统而开发的。

四分之一个世纪以来，世人尽知谷歌拥有史上最成功的搜索引擎，然而有几人了解到是什么魔法使它进入市场后迅速走红，又有几人通晓引导它成功的关键数学为何？今天是第七个国际数学日，正是每个数学爱好者甚至数学同情者可以借机接受数学普及的好日子。笔者受中国数学会的一则通知启发，想到谷歌矩阵这个与国际人的日常生活、学习工作、职场发展都有关系的“全世界最大的矩阵”，觉得谈谈它或许是向国际数学日所献的一朵艳丽之花。

由于网页数量庞大（目前网站总数超过13亿，但只有约六分之一的网站“被积极维护”。搜索引擎索引的实际网页数量在40亿至60亿之间，而搜索引擎识别的网页数量则超过130万亿），网络信息检索比传统的信息检索更具挑战性。在网络信息检索研究中，每个网页都被表示为一个超大型有向图中的一个节点，连接这些节点的有向边代表页面之间的超链接。

这种超链接结构可以通过三种信息检索方法进行探索，第一种是“超文本诱导主题搜索”，其代表性论文是J. Kleinberg于1999年在美国计算机协会杂志上发表的Authoritative Sources in a Hyperlinked Environment（超链接环境中的权威来源）；第二种是“链接结构分析的随机方法”；第三种是本文将重点介绍的网页排序法，最初思想由佩奇和布林于1996年酝酿而生，他们对此的第一篇技术性文章由四人合写，其中最后一位作者就是他们的导师维诺格拉德。这篇历史留名的论文于1999年以斯坦福大学计算机科学系技术报告1999-0120的方式公开问世，标题是The PageRank Citation Ranking: Bringing Order to the Web（PageRank引用排名：为网络带来秩序）。尽管该文似乎从未在学术期刊上正式发表，迄今却已被引用了两万余次。可见并非总是在名刊甚至期刊上发表的论文才会“推动科技的进步”。

在网页排序概念出现两年后横空出世的谷歌公司，一开始就在官网声明：

网页排序是我们软件的核心。

又过了以惊人速度壮大发展的四年，与公司员工共舞的其尺寸大得难以想象的那个矩阵——后被人们常挂在嘴边的“谷歌矩阵”，引发出大型通用计算程序包Matlab的开发者克利夫·莫勒（Cleve Moler，1939-）的感慨，在自己公司MathWorks的《Matlab新闻和简讯》上撰文《世界上规模最大的矩阵计算》。

那么，这个世间最大的矩阵是怎么定义出来的？

首先，它是一个非负矩阵，即矩阵的每个元素都是非负实数，并且它也是个方阵，即行数等于列数。其次，它的每一行的所有元素加起来都等于1。这种特殊的非负矩阵有个学名，叫随机矩阵（stochastic matrix）。在线性代数这门应用广泛的数学学科，“非负矩阵理论”构成了一个子学科，而随机矩阵又是其中的核心部分。可惜的是，我们的本科教科书中一般不放进这类东西。

要充分理解谷歌矩阵的定义基础，先得从网页排序的基本想法开始。

网页排序的理念是：

来自重要页面的链接应该比来自不太重要页面的链接权重更高，并且来自任何源页面的链接的重要性应该根据该源页面链接到的页面数量进行缩放。

这个创新思想是容易想得通的。多年前，当笔者之一在国内高校做有关谷歌矩阵的演讲时，向听众如此解释它：国家领袖网页上的内容肯定比数学教授的网页内容在大众眼里更加重要，而且前者的网页会被更多的网页链接到，因此它应享有更加靠前的排名。如果采用数学语言来表达前述的意思，那么该想法是通过定义给定网页P的合理排名r(P)来实现的。r(P)定义为：

r(P) = ∑Q∈I(P)r(Q)/|Q|，

其中I(P)是所有指向P的那些网页组成的集合，r(Q)是网页Q的排名，|Q|表示从网页Q发出的链接数。如上表达式说明，网页P的重要程度，首先依链接到它的其他网页的多寡而定，越多越重要，且那些指向它的网页Q越重要，则P也随之越重要，可谓“水涨船高”；其次，若指向网页P的某个网页Q也指向其他网页，则被链接的网页越多，P在Q眼中的重要性相应就变低，这解释了为何|Q|出现在分母。打个比方，如果阁下的网页被某个名流链接到，不必太得意，或许该名流热衷于社会交际，同时也链接了其他许多人的网页，这样的话你的网页重要性并没有因该名流的光顾而大增。

以上对单个网页P的排名r(P)虽然定义合理，但这是一个隐式定义，因此我们借用迭代法来找到上述“不动点方程”的一个解，方法如下：

假设共有n个网页P1,P2,...,Pn。为每个网页分配一个初始排名r0，最公平合理的初始排名是均匀排名

r0(Pi) = 1/n，i = 1,2,…,n。

然后对k = 1,2,3,...如下操作排名迭代：

rk(Pi) = ∑Pj∈I(Pi)rk−1(Pj)/|Pj|，i = 1,2,…,n。

现在定义n阶方阵P = [pij]ni,j = 1：对于i, j = 1, 2,…, n，若网页Pi链接到网页Pj，则令

pij= 1/|Pi|；

否则的话，定义pij= 0。显见，P是非负方阵且每行元素之和等于1。换言之，P是n阶随机矩阵。此外，对于行向量

πkT= (rk(P1), rk(P2), …, rk(Pn)),

上述的迭代过程可以用矩阵乘法的形式表示：

πkT=(πk-1)TP,k = 1,2,…。

如果下列极限存在的话，佩奇和布林将极限向量

πT= limk→∞πkT

定义为网页排序向量，而它的第i个分量πi则成为网页Pi的排名。

可是，要使得定义不被诟病，他们需要回答两个问题：

1.这个原始的谷歌矩阵P是否存在对应于特征值1的左特征向量πT？若πT存在，归一化（目的让所有分量之和变成1）后的πT是否唯一？

2.当k趋于无穷大时，迭代向量序列πkT=(πk-1)TP的极限是否存在？若存在，那么迭代收敛得多快呢？

现在用一个简单例子说明思想。考虑一个仅有六个网页的微型网络，并使用原始的谷歌矩阵。

注意到矩阵的第二行元素全为零，这是因为没有从第二个网页（对应的有向图节点叫做悬空节点）发出的链接。所以P不是一个随机矩阵！

为了补救，我们将第二行的每个元素加上1/6，便得到一个随机矩阵S：

对于这个经过改造的矩阵，非负矩阵理论中最经典的一个定理派上了大用场，它以两个德国数学家的名字命名——佩龙-佛罗贝尔尼斯定理，年轻的前者佩龙（Oskar Perron，1880-1975）于1907年对正矩阵，即每个元素均为正数的矩阵证明了它，年长的后者佛罗贝尔尼斯（Ferdinand GeorgFrobenius，1849-1917）五年后对所谓的不可约非负矩阵推广了佩龙的结果。一个方阵称为是可约的，意思是说，可以将它的行和列以同样的方式重新排列，其结果矩阵的右下角是个零方阵。譬如，2阶及更高阶的单位矩阵是可约非负矩阵。

即便上述的随机矩阵S是可约的，一个经典的不动点定理——布劳威尔不动点定理却能保证，存在归一化的非负左特征向量πT：

πT= πTS,πTe = 1。

这里按习惯用字母e代表特殊列向量(1,1,…,1)T。任意矩阵A乘以e，所得向量的各分量等于将A的那行元素加起来得到的和，故非负矩阵A为随机矩阵当且仅当Ae = e。

遗憾的是，上例中的随机矩阵S虽然确保了网页排序向量πT的存在性，却由于它是可约的（因为右下角是3阶零矩阵），结果是归一化的πT不能保证唯一且分量个个为正。如果网页排名不唯一，至少会造成网页排序算法迭代不收敛或计算结果混淆不清。当今各种大学排名榜五花八门，结果千奇百怪，搞得大学当局有时高兴有时发愁，就是排名不唯一的后遗症。

为解决这一棘手问题，布林和佩奇引入了S的由参数α∈(0,1)控制的一种“凸组合”扰动；例如，取α = 0.9，得到一个新矩阵：

读者一看就知道G是一个正矩阵。此外，它继承了S是随机矩阵的好性质，这一点的证明简洁而明快：

Ge=(0.9S + 0.1eeT/6)e = 0.9Se + 0.1eeTe/6

= 0.9e + 0.1(eTe)e/6 = 0.9e + 0.1(6)e/6 = 0.9e + 0.1e = e。

这样，按照佩龙-佛罗贝尔尼斯的非负矩阵理论，G不仅存在唯一的归一化左特征向量πT，其具体数值是

πT= (0.03721, 0.05396, 0.04151, 0.3751, 0.206, 0.2862)，

而且正因为这个网页排序向量的所有分量均为正数，它实实在在地提供了所给微型网络总共6个网页的排名。更重要的是，取定初始向量π0T= (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)，直接迭代法

πkT=(πk-1)TG，k = 1,2,...

计算出的归一化向量序列{πkT}收敛到G的唯一归一化左特征向量πT。

有了上面的具体例子垫底，我们可以叙述谷歌矩阵的一般定义及其相应的网页排序算法。如前，假设所有的网页为P1,P2,...,Pn，其对应的n阶原始谷歌矩阵为P。选取一个固定的n维“概率向量”

v = (v1, v2, v3,…, vn)T，

即v的所有分量都是正数，并且其和等于1，即vTe = 1。

将矩阵P的所有零行替换为相同的行向量vT，得到随机矩阵S。现在固定参数α∈(0,1)（早期谷歌公司使用过参数值α= 0.85），并将谷歌矩阵G定义为S和evT的凸组合：

G = αS + (1–α)evT。

G依然是个随机矩阵：

Ge = [αS + (1–α)evT]e =αSe + (1–α)evTe

=αe + (1–α)(vTe)e=αe + (1–α)e = e。

更重要的是，由于S是非负矩阵，evT是正矩阵，它们的凸组合的系数小于1，这保证了G是个正矩阵。如此构造的矩阵G被称为谷歌矩阵。

万事俱备只欠东风，现在可以叙述（但不证明）已超过一百年历史的佩龙-佛罗贝尔尼斯定理在正随机矩阵时的特殊结论了。

正随机矩阵谱定理.设A为一n阶正随机矩阵。则存在归一化的所有分量均为正数的n维行向量πT，即

πT= πTA,πTe = 1；

满足上述性质的πT是唯一的。此外，A的所有特征值的最大模等于1，并且1是A在复平面单位圆上的唯一特征值。更进一步，任给归一化的n维非负初始向量π0T，迭代向量序列

πkT=(πk-1)TA =π0TAk，k = 1,2,...

收敛到πT。

谱定理告诉我们，对于佩奇和布林创造出的谷歌矩阵，上述这个被称为“幂方法”的迭代程式总收敛到网页排序向量。又因为谷歌矩阵规模巨大，幂方法只能是给全球有效网页快速排名的唯一实用办法。

收敛性问题圆满解决后，关注谷歌用于计算网页排序基本算法效率的读者自然会问到“收敛得多快”的应用性问题。学过数值线性代数的人知道幂方法的收敛速率取决于矩阵所有特征值中的次大模。现在我们用矩阵特征多项式的技巧来寻找谷歌矩阵G所有的特征值。

首先，因为S是随机矩阵，1是它的特征值，特征向量是e。记S的所有特征值为1,λ2, λ3, ··· , λn。则αS的征值为α,αλ2,αλ3, …,αλn。为方便起见，令A = αS及u = (1–α)e。则G = A + uvT。

设λ不是A的特征值。从等式λI−G = (λI−A)−uvT，运用著名的矩阵行列式引理，即若B为m阶非奇异矩阵，且x和y为m维向量，则

det(B + xyT) =(1+ yTB-1x)detB，

得到G的特征多项式的表达式

det(λI−G) =[1–vT(λI−A)-1u]det(λI−A)。

由于

(λI−A)u = (1−α)(λI–αS)e = (1−α)(λ−α)e

= (λ−α)(1−α)e = (λ−α)u，

(λI−A)-1u =(λ–α)-1u，

随即便有

1−vT(λI−A)-1u =1−(λ–α)-1vTu= (λ–α)-1[λ–(α+vTu)]。

从而得到

det(λI−G) =(λ–α)-1[λ–(α+vTu)]det(λI−A)。

因为α+vTu=α+vT(1−α)e=α+(1−α) vTe =α+(1−α)= 1，便有

det(λI−G) =(λ–α)-1(λ–1)det(λI−A)

=(λ–α)-1(λ–1)(λ–α)(λ–αλ2) (λ–αλ3)…(λ–αλn)

= (λ–1)(λ–αλ2) (λ–αλ3)…(λ–αλn)。

这就证明了下列的定理：

谷歌矩阵谱定理.谷歌矩阵G=αS + (1–α)evT的所有特征值是

1,αλ2,αλ3, …,αλn。

由于每个λi位于单位圆的内部，故

|αλi|<α < 1,i = 2,3,...,n，

因此幂方法的收敛速率取决于参数值α的大小。这个值如果取得靠近(0, 1)开区间的右端点，幂方法的迭代步伐就会慢下来；反之，若将它取得太小，甚至靠近(0, 1)的左端点，G又与折射出真实网络世界各网页之间“朋友关系”的S相距太远，这样计算虽然快了，但结果或许有不能全方位反映真实世界之危险。总之，选择参数α的数值要顾及到准确与速度的双重思量。

就数学而言，上面的谷歌矩阵谱定理是下面的秩-1矫正矩阵谱扰动定理的一个特殊化。这个一般结果是笔者之一20年前在一篇合作文章中证明的。

秩-1矫正矩阵谱扰动定理.设A为一n阶矩阵，其特征值是λ1, λ2, ..., λn。若u和v为两个n维向量，其中u是A对应于λ1的特征向量，则A+uvT的特征值是λ1+vTu, λ2, …, λn。

将上述定理中的A取为谷歌矩阵谱定理中的αS，u取为(1–α)e，则如前所述，A的特征值是α,αλ2,αλ3, …,αλn，且u是A对应于α的特征向量。则秩-1矫正矩阵谱扰动定理给出G =αS + (1–α)evT的第一个特征值为

λ1+vTu=α+ (1–α)vTe =α+ (1–α) = 1，

而αS的特征值αλ2,αλ3, …,αλn通通留给了G，得到谷歌矩阵谱定理的结论。

过去四分之一个世纪，PageRank 算法不仅成就了一家商业巨头，更深刻改变了人类获取信息的范式。尽管在今天，随着人工智能的演进和网络生态的更迭，传统搜索引擎的形态正经历剧烈的阵痛与重塑，但其背后的数学逻辑——通过矩阵刻画关联、用特征值寻找秩序——依然是处理海量数据的核心思想。今天正值国际数学日，回望这个“世界最大矩阵”，我们感叹的不仅是算法带来的便利，更是数学作为一种普适语言，在纷繁复杂的现实世界中剥离混沌、指引真理的纯粹力量。