讓谷歌橫空出世的世界最大矩陣

圖源：pixabay

撰文 ｜丁玖 朱慧堅（廣州南方學(xué)院）

1998年9月4日，兩個25周歲的年輕小伙拉里·佩奇(Larry Page，生于1973年3月26日)和謝爾蓋·布林（Sergey Brin，生于1973年8月21日）在加利福尼亞州舊金山灣區(qū)圣馬特奧（San Mateo）縣的城市門洛帕克（Menlo Park）提交了谷歌公司的注冊文件。這個小城僅有三萬多居民，南面的近鄰是斯坦福大學(xué)，而他們正在那里攻讀計算機科學(xué)系的博士學(xué)位。

他們創(chuàng)辦的這家公司，四分之一個世紀后，其“谷歌搜索”成了全球訪問量最高的兩個網(wǎng)站之一。佩奇和布林最初將他們開辟的新搜索引擎昵稱為“背部按摩（BackRub）”，因為該系統(tǒng)會檢查反向鏈接來評估網(wǎng)站的重要性。最終，他們將名稱改為Google，然而這是對古戈爾（googol）一詞的錯誤拼寫。古戈爾是一個巨大的數(shù)字10100（1后面跟著100個零），選擇這個數(shù)字是為了表明該搜索引擎旨在提供大量信息。不過，直到今天，全世界的網(wǎng)頁個數(shù)還遠遠低于這個已經(jīng)超過宇宙所有原子個數(shù)的大數(shù)；或許永遠也達不到。

古戈爾由美國哥倫比亞大學(xué)數(shù)學(xué)系教授愛德華·卡斯納（Edward Kasner，1878-1955）的侄子、年僅9歲的米爾頓·西羅塔（Milton Sirotta）創(chuàng)造，用來表示一個難以想象的大數(shù)。卡斯納在其1940年出版的《數(shù)學(xué)與想象力》一書中推廣了古戈爾的概念，它形象地展示了大數(shù)與無窮之間的尺度，想必谷歌的創(chuàng)始人受此啟發(fā)，給他們的搜索引擎新生兒起了這個拼錯了一個字母的名字。順便一提，卡斯納最杰出的弟子是首屆菲爾茲獎的兩名獲獎?wù)咧弧⒚绹鴶?shù)學(xué)家杰西·道格拉斯（Jesse Douglas，1897-1965）。

無論佩奇還是布林，創(chuàng)辦公司后都沒有待在世界名校斯坦福美麗的校園，穩(wěn)穩(wěn)當(dāng)當(dāng)?shù)貓猿值阶詈螅垣@一紙博士證書。他們最終的學(xué)位——碩士——仍然高于年長他們18歲的比爾·蓋茨（Bill Gates，1955-）；后者入學(xué)哈佛大學(xué)讀本科兩年后毅然退學(xué)，與合作伙伴開創(chuàng)了微軟公司，開啟了他一生的輝煌事業(yè)。佩奇和布林共同創(chuàng)辦的公司——谷歌——同樣也成了本世紀全世界最著名的高科技公司之一。沒有追求學(xué)位圓滿的他們?nèi)耍髞矶急贿x為美國國家工程院院士。

佩奇和布林都有猶太血統(tǒng)。兩人中，年輕半歲的布林有個數(shù)學(xué)家爸爸，佩奇的父親則是計算機科學(xué)家。布林之父米哈伊·布林（MihailBrin，1947-）是個國際知名的俄羅斯純粹數(shù)學(xué)家，專長為動力系統(tǒng)與黎曼幾何，本科畢業(yè)于莫斯科大學(xué)，博士導(dǎo)師為蘇聯(lián)動力系統(tǒng)大家德米特里·阿諾索夫（Dmitri Anosov（1936-2014）和阿納托爾·諾克（Anatole Katok，1944-2018）。布林教授在普林斯頓大學(xué)數(shù)學(xué)系編輯的純數(shù)學(xué)國際頂尖雜志《數(shù)學(xué)年刊》上發(fā)表過三篇論文，也出版過書籍，如與他后來的馬里蘭大學(xué)同事合著的《動力系統(tǒng)引論》，2015年由劍橋大學(xué)出版社推出。

小布林6歲時隨全家從蘇聯(lián)移民到美國。1990年他追隨父親的腳步跨進了馬里蘭大學(xué)，不過，父親是數(shù)學(xué)系的教授，他則在數(shù)學(xué)系和計算機科學(xué)系讀本科。三年后，他以數(shù)學(xué)與計算機科學(xué)雙專業(yè)榮譽畢業(yè)生的優(yōu)異成績獲得學(xué)士學(xué)位。馬里蘭大學(xué)數(shù)學(xué)系一直引以自豪的另一個本科畢業(yè)生是菲爾茲獎獲得者查爾斯·費弗曼（Charles Fefferman，1949-），他17歲就獲得數(shù)學(xué)與物理學(xué)的雙學(xué)位，于普林斯頓大學(xué)獲得數(shù)學(xué)博士后，22歲時成為芝加哥大學(xué)的正教授；他的同門博士師弟就是另一個菲爾茲獎獲得者陶澤軒（Terence Tao，1975-）。

佩奇是個土生土長的美國人，他的父親卡爾·佩奇（Carl Page Sr.，1938-1996）是筆者之一博士母校密歇根州立大學(xué)的計算機科學(xué)教授。老佩奇博士畢業(yè)于密歇根州的首席大學(xué)、也是全美最負盛名的公立大學(xué)之一密歇根大學(xué)的計算機科學(xué)系，在其職業(yè)生涯中是美國人工智能研究的先驅(qū)之一。可惜佩奇教授英年早逝，未能像布林教授那樣目睹了兒子成長為業(yè)界巨人。

小佩奇也步了父親的后塵，一腳跨進密歇根大學(xué)的校門，父子倆成為這所被譽為“美國公立大學(xué)之母”的中西部巨無霸大學(xué)的先后校友。在父母的直接影響下，兒子6歲時就對電腦產(chǎn)生了興趣，因為他可以“玩弄那些散落在周圍的東西”——他父母留下的第一代個人電腦。他成為“小學(xué)里第一個用文字處理器交作業(yè)的孩子”。可以說他是在電腦配件的叢林中長大的，“熟能生巧”這一中文成語可以恰如其分地形容佩奇從兒童走向青年對計算機世界的癡迷程度。后來他說：“從小我就意識到自己想發(fā)明創(chuàng)造。所以我對科技和商業(yè)產(chǎn)生了興趣。大概從12歲起，我就知道自己最終會創(chuàng)辦一家公司。”

在密歇根州立大學(xué)所在地東蘭辛高中畢業(yè)后，從1991年到1995年，佩奇在密歇根大學(xué)讀計算機工程，以榮譽稱號獲得工程學(xué)士學(xué)位，然后進入西部學(xué)術(shù)重鎮(zhèn)斯坦福大學(xué)攻讀計算機科學(xué)博士學(xué)位，在他創(chuàng)業(yè)元年獲得碩士學(xué)位。

在尋找論文選題時，佩奇考慮探索萬維網(wǎng)的數(shù)學(xué)特性，將其鏈接結(jié)構(gòu)理解為一個龐大的有向圖。他的導(dǎo)師特里·維諾格拉德（Terry Winograd，1946-)鼓勵他繼續(xù)研究這個想法。2008年谷歌20周歲，佩奇以感恩之情回憶道：“這是我收到的最好建議。”

成功實現(xiàn)快速高效網(wǎng)頁搜索的好想法，不僅得益于有深遠眼光學(xué)術(shù)導(dǎo)師的好建議，還需要背景類似、志同道合、互補長短的合作伙伴，這對應(yīng)用科學(xué)十分奏效。在斯坦福這個布滿才華橫溢年輕學(xué)者的校園內(nèi)，同在計算機科學(xué)疆場習(xí)武的布林加入到佩奇的行列，兩人結(jié)伴開始了對網(wǎng)頁搜索引擎的創(chuàng)新研究。卓有成效的共同努力導(dǎo)致“網(wǎng)頁排序（PageRank）”這個互聯(lián)網(wǎng)史上具有里程碑意義的新穎概念和術(shù)語的誕生。

在英文的語義下，兩個單詞的無空格組合PageRank可以有兩層含義；其一是與實施對象相關(guān)的如上翻譯“網(wǎng)頁排序”，其二是“佩奇排序”，理由為Page是佩奇的姓。事實上，“PageRank”這個名字是個雙關(guān)語，既指網(wǎng)頁排名算法，也指其開發(fā)者佩奇。該算法最初是作為一種基于鏈接流行度對搜索結(jié)果進行排序的系統(tǒng)而開發(fā)的。

四分之一個世紀以來，世人盡知谷歌擁有史上最成功的搜索引擎，然而有幾人了解到是什么魔法使它進入市場后迅速走紅，又有幾人通曉引導(dǎo)它成功的關(guān)鍵數(shù)學(xué)為何？今天是第七個國際數(shù)學(xué)日，正是每個數(shù)學(xué)愛好者甚至數(shù)學(xué)同情者可以借機接受數(shù)學(xué)普及的好日子。筆者受中國數(shù)學(xué)會的一則通知啟發(fā)，想到谷歌矩陣這個與國際人的日常生活、學(xué)習(xí)工作、職場發(fā)展都有關(guān)系的“全世界最大的矩陣”，覺得談?wù)勊蛟S是向國際數(shù)學(xué)日所獻的一朵艷麗之花。

由于網(wǎng)頁數(shù)量龐大（目前網(wǎng)站總數(shù)超過13億，但只有約六分之一的網(wǎng)站“被積極維護”。搜索引擎索引的實際網(wǎng)頁數(shù)量在40億至60億之間，而搜索引擎識別的網(wǎng)頁數(shù)量則超過130萬億），網(wǎng)絡(luò)信息檢索比傳統(tǒng)的信息檢索更具挑戰(zhàn)性。在網(wǎng)絡(luò)信息檢索研究中，每個網(wǎng)頁都被表示為一個超大型有向圖中的一個節(jié)點，連接這些節(jié)點的有向邊代表頁面之間的超鏈接。

這種超鏈接結(jié)構(gòu)可以通過三種信息檢索方法進行探索，第一種是“超文本誘導(dǎo)主題搜索”，其代表性論文是J. Kleinberg于1999年在美國計算機協(xié)會雜志上發(fā)表的Authoritative Sources in a Hyperlinked Environment（超鏈接環(huán)境中的權(quán)威來源）；第二種是“鏈接結(jié)構(gòu)分析的隨機方法”；第三種是本文將重點介紹的網(wǎng)頁排序法，最初思想由佩奇和布林于1996年醞釀而生，他們對此的第一篇技術(shù)性文章由四人合寫，其中最后一位作者就是他們的導(dǎo)師維諾格拉德。這篇歷史留名的論文于1999年以斯坦福大學(xué)計算機科學(xué)系技術(shù)報告1999-0120的方式公開問世，標題是The PageRank Citation Ranking: Bringing Order to the Web（PageRank引用排名：為網(wǎng)絡(luò)帶來秩序）。盡管該文似乎從未在學(xué)術(shù)期刊上正式發(fā)表，迄今卻已被引用了兩萬余次。可見并非總是在名刊甚至期刊上發(fā)表的論文才會“推動科技的進步”。

在網(wǎng)頁排序概念出現(xiàn)兩年后橫空出世的谷歌公司，一開始就在官網(wǎng)聲明：

網(wǎng)頁排序是我們軟件的核心。

又過了以驚人速度壯大發(fā)展的四年，與公司員工共舞的其尺寸大得難以想象的那個矩陣——后被人們常掛在嘴邊的“谷歌矩陣”，引發(fā)出大型通用計算程序包Matlab的開發(fā)者克利夫·莫勒（Cleve Moler，1939-）的感慨，在自己公司MathWorks的《Matlab新聞和簡訊》上撰文《世界上規(guī)模最大的矩陣計算》。

那么，這個世間最大的矩陣是怎么定義出來的？

首先，它是一個非負矩陣，即矩陣的每個元素都是非負實數(shù)，并且它也是個方陣，即行數(shù)等于列數(shù)。其次，它的每一行的所有元素加起來都等于1。這種特殊的非負矩陣有個學(xué)名，叫隨機矩陣（stochastic matrix）。在線性代數(shù)這門應(yīng)用廣泛的數(shù)學(xué)學(xué)科，“非負矩陣理論”構(gòu)成了一個子學(xué)科，而隨機矩陣又是其中的核心部分。可惜的是，我們的本科教科書中一般不放進這類東西。

要充分理解谷歌矩陣的定義基礎(chǔ)，先得從網(wǎng)頁排序的基本想法開始。

網(wǎng)頁排序的理念是：

來自重要頁面的鏈接應(yīng)該比來自不太重要頁面的鏈接權(quán)重更高，并且來自任何源頁面的鏈接的重要性應(yīng)該根據(jù)該源頁面鏈接到的頁面數(shù)量進行縮放。

這個創(chuàng)新思想是容易想得通的。多年前，當(dāng)筆者之一在國內(nèi)高校做有關(guān)谷歌矩陣的演講時，向聽眾如此解釋它：國家領(lǐng)袖網(wǎng)頁上的內(nèi)容肯定比數(shù)學(xué)教授的網(wǎng)頁內(nèi)容在大眾眼里更加重要，而且前者的網(wǎng)頁會被更多的網(wǎng)頁鏈接到，因此它應(yīng)享有更加靠前的排名。如果采用數(shù)學(xué)語言來表達前述的意思，那么該想法是通過定義給定網(wǎng)頁P的合理排名r(P)來實現(xiàn)的。r(P)定義為：

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

其中I(P)是所有指向P的那些網(wǎng)頁組成的集合，r(Q)是網(wǎng)頁Q的排名，|Q|表示從網(wǎng)頁Q發(fā)出的鏈接數(shù)。如上表達式說明，網(wǎng)頁P的重要程度，首先依鏈接到它的其他網(wǎng)頁的多寡而定，越多越重要，且那些指向它的網(wǎng)頁Q越重要，則P也隨之越重要，可謂“水漲船高”；其次，若指向網(wǎng)頁P的某個網(wǎng)頁Q也指向其他網(wǎng)頁，則被鏈接的網(wǎng)頁越多，P在Q眼中的重要性相應(yīng)就變低，這解釋了為何|Q|出現(xiàn)在分母。打個比方，如果閣下的網(wǎng)頁被某個名流鏈接到，不必太得意，或許該名流熱衷于社會交際，同時也鏈接了其他許多人的網(wǎng)頁，這樣的話你的網(wǎng)頁重要性并沒有因該名流的光顧而大增。

以上對單個網(wǎng)頁P的排名r(P)雖然定義合理，但這是一個隱式定義，因此我們借用迭代法來找到上述“不動點方程”的一個解，方法如下：

假設(shè)共有n個網(wǎng)頁P1,P2,...,Pn。為每個網(wǎng)頁分配一個初始排名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。

現(xiàn)在定義n階方陣P = [pij]ni,j = 1：對于i, j = 1, 2,…, n，若網(wǎng)頁Pi鏈接到網(wǎng)頁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

定義為網(wǎng)頁排序向量，而它的第i個分量πi則成為網(wǎng)頁Pi的排名。

可是，要使得定義不被詬病，他們需要回答兩個問題：

1.這個原始的谷歌矩陣P是否存在對應(yīng)于特征值1的左特征向量πT？若πT存在，歸一化（目的讓所有分量之和變成1）后的πT是否唯一？

2.當(dāng)k趨于無窮大時，迭代向量序列πkT=(πk-1)TP的極限是否存在？若存在，那么迭代收斂得多快呢？

現(xiàn)在用一個簡單例子說明思想。考慮一個僅有六個網(wǎng)頁的微型網(wǎng)絡(luò)，并使用原始的谷歌矩陣。

注意到矩陣的第二行元素全為零，這是因為沒有從第二個網(wǎng)頁（對應(yīng)的有向圖節(jié)點叫做懸空節(jié)點）發(fā)出的鏈接。所以P不是一個隨機矩陣！

為了補救，我們將第二行的每個元素加上1/6，便得到一個隨機矩陣S：

對于這個經(jīng)過改造的矩陣，非負矩陣理論中最經(jīng)典的一個定理派上了大用場，它以兩個德國數(shù)學(xué)家的名字命名——佩龍-佛羅貝爾尼斯定理，年輕的前者佩龍（Oskar Perron，1880-1975）于1907年對正矩陣，即每個元素均為正數(shù)的矩陣證明了它，年長的后者佛羅貝爾尼斯（Ferdinand GeorgFrobenius，1849-1917）五年后對所謂的不可約非負矩陣推廣了佩龍的結(jié)果。一個方陣稱為是可約的，意思是說，可以將它的行和列以同樣的方式重新排列，其結(jié)果矩陣的右下角是個零方陣。譬如，2階及更高階的單位矩陣是可約非負矩陣。

即便上述的隨機矩陣S是可約的，一個經(jīng)典的不動點定理——布勞威爾不動點定理卻能保證，存在歸一化的非負左特征向量πT：

πT= πTS,πTe = 1。

這里按習(xí)慣用字母e代表特殊列向量(1,1,…,1)T。任意矩陣A乘以e，所得向量的各分量等于將A的那行元素加起來得到的和，故非負矩陣A為隨機矩陣當(dāng)且僅當(dāng)Ae = e。

遺憾的是，上例中的隨機矩陣S雖然確保了網(wǎng)頁排序向量πT的存在性，卻由于它是可約的（因為右下角是3階零矩陣），結(jié)果是歸一化的πT不能保證唯一且分量個個為正。如果網(wǎng)頁排名不唯一，至少會造成網(wǎng)頁排序算法迭代不收斂或計算結(jié)果混淆不清。當(dāng)今各種大學(xué)排名榜五花八門，結(jié)果千奇百怪，搞得大學(xué)當(dāng)局有時高興有時發(fā)愁，就是排名不唯一的后遺癥。

為解決這一棘手問題，布林和佩奇引入了S的由參數(shù)α∈(0,1)控制的一種“凸組合”擾動；例如，取α = 0.9，得到一個新矩陣：

讀者一看就知道G是一個正矩陣。此外，它繼承了S是隨機矩陣的好性質(zhì)，這一點的證明簡潔而明快：

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，其具體數(shù)值是

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

而且正因為這個網(wǎng)頁排序向量的所有分量均為正數(shù)，它實實在在地提供了所給微型網(wǎng)絡(luò)總共6個網(wǎng)頁的排名。更重要的是，取定初始向量π0T= (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)，直接迭代法

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

計算出的歸一化向量序列{πkT}收斂到G的唯一歸一化左特征向量πT。

有了上面的具體例子墊底，我們可以敘述谷歌矩陣的一般定義及其相應(yīng)的網(wǎng)頁排序算法。如前，假設(shè)所有的網(wǎng)頁為P1,P2,...,Pn，其對應(yīng)的n階原始谷歌矩陣為P。選取一個固定的n維“概率向量”

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

即v的所有分量都是正數(shù)，并且其和等于1，即vTe = 1。

將矩陣P的所有零行替換為相同的行向量vT，得到隨機矩陣S。現(xiàn)在固定參數(shù)α∈(0,1)（早期谷歌公司使用過參數(shù)值α= 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是正矩陣，它們的凸組合的系數(shù)小于1，這保證了G是個正矩陣。如此構(gòu)造的矩陣G被稱為谷歌矩陣。

萬事俱備只欠東風(fēng)，現(xiàn)在可以敘述（但不證明）已超過一百年歷史的佩龍-佛羅貝爾尼斯定理在正隨機矩陣時的特殊結(jié)論了。

正隨機矩陣譜定理.設(shè)A為一n階正隨機矩陣。則存在歸一化的所有分量均為正數(shù)的n維行向量πT，即

πT= πTA,πTe = 1；

滿足上述性質(zhì)的πT是唯一的。此外，A的所有特征值的最大模等于1，并且1是A在復(fù)平面單位圓上的唯一特征值。更進一步，任給歸一化的n維非負初始向量π0T，迭代向量序列

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

收斂到πT。

譜定理告訴我們，對于佩奇和布林創(chuàng)造出的谷歌矩陣，上述這個被稱為“冪方法”的迭代程式總收斂到網(wǎng)頁排序向量。又因為谷歌矩陣規(guī)模巨大，冪方法只能是給全球有效網(wǎng)頁快速排名的唯一實用辦法。

收斂性問題圓滿解決后，關(guān)注谷歌用于計算網(wǎng)頁排序基本算法效率的讀者自然會問到“收斂得多快”的應(yīng)用性問題。學(xué)過數(shù)值線性代數(shù)的人知道冪方法的收斂速率取決于矩陣所有特征值中的次大模。現(xiàn)在我們用矩陣特征多項式的技巧來尋找谷歌矩陣G所有的特征值。

首先，因為S是隨機矩陣，1是它的特征值，特征向量是e。記S的所有特征值為1,λ2, λ3, ··· , λn。則αS的征值為α,αλ2,αλ3, …,αλn。為方便起見，令A(yù) = αS及u = (1–α)e。則G = A + uvT。

設(shè)λ不是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位于單位圓的內(nèi)部，故

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

因此冪方法的收斂速率取決于參數(shù)值α的大小。這個值如果取得靠近(0, 1)開區(qū)間的右端點，冪方法的迭代步伐就會慢下來；反之，若將它取得太小，甚至靠近(0, 1)的左端點，G又與折射出真實網(wǎng)絡(luò)世界各網(wǎng)頁之間“朋友關(guān)系”的S相距太遠，這樣計算雖然快了，但結(jié)果或許有不能全方位反映真實世界之危險。總之，選擇參數(shù)α的數(shù)值要顧及到準確與速度的雙重思量。

就數(shù)學(xué)而言，上面的谷歌矩陣譜定理是下面的秩-1矯正矩陣譜擾動定理的一個特殊化。這個一般結(jié)果是筆者之一20年前在一篇合作文章中證明的。

秩-1矯正矩陣譜擾動定理.設(shè)A為一n階矩陣，其特征值是λ1, λ2, ..., λn。若u和v為兩個n維向量，其中u是A對應(yīng)于λ1的特征向量，則A+uvT的特征值是λ1+vTu, λ2, …, λn。

將上述定理中的A取為谷歌矩陣譜定理中的αS，u取為(1–α)e，則如前所述，A的特征值是α,αλ2,αλ3, …,αλn，且u是A對應(yīng)于α的特征向量。則秩-1矯正矩陣譜擾動定理給出G =αS + (1–α)evT的第一個特征值為

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

而αS的特征值αλ2,αλ3, …,αλn通通留給了G，得到谷歌矩陣譜定理的結(jié)論。

過去四分之一個世紀，PageRank 算法不僅成就了一家商業(yè)巨頭，更深刻改變了人類獲取信息的范式。盡管在今天，隨著人工智能的演進和網(wǎng)絡(luò)生態(tài)的更迭，傳統(tǒng)搜索引擎的形態(tài)正經(jīng)歷劇烈的陣痛與重塑，但其背后的數(shù)學(xué)邏輯——通過矩陣刻畫關(guān)聯(lián)、用特征值尋找秩序——依然是處理海量數(shù)據(jù)的核心思想。今天正值國際數(shù)學(xué)日，回望這個“世界最大矩陣”，我們感嘆的不僅是算法帶來的便利，更是數(shù)學(xué)作為一種普適語言，在紛繁復(fù)雜的現(xiàn)實世界中剝離混沌、指引真理的純粹力量。