電影《心靈捕手》的數學問題 (一)

本文的閱讀等級:中級

美國馬里蘭大學馬尼爾‧蘇里 (Manil Suri) 教授說[1]

在新聞媒體或文化領域,很少會出現數學這個主題。很多時候,當數學出現在一部小說或電影中時,我就會想起契訶夫諺語中的槍:如果一個數學家不發瘋,就別讓他出場。對數學的焦慮感,像厚厚的陰霾一樣籠罩着萬事萬物。

我知道關於「數學與人物」的電影法則有:如果你是一個正常人,那麼你當害怕或討厭數學;如果你解開別人解不出的數學題,那麼你不是書呆子就是精神異常者;如果你的數學本來其爛無比,有一天卻突然擁有超強的特異能力,那麼你可能被外星人附體或腦部受到不明來源的輻射汙染。在電影《心靈捕手》(Good Will Hunting),麻省理工學院的朗博教授 (Gerald Lambeau) 為激勵學生上進,他在走廊黑板公布數學難題並保證答對者將可名利雙收。清潔工威爾 (Will Hunting) 擁有過人的天賦,性格叛逆亟需心理治療,但尚未惡化到發瘋的地步[2]。朗博教授和威爾同在一棟大樓工作,不過兩人沒有任何交集。本文討論朗博教授張貼的第一個問題。下面是電影片段 (字幕見[3])。

 
朗博教授在黑板左邊寫的題目如下:

G is the graph. Find
(1) the adjacency matrix A,
(2) the matrix giving the number of 3 step walks,
(3) the generating function for walks from point i\to j,
(4) the generating function for walks from point 1\to 3.

The graph G

The graph G

 
電影中沒有一個學生想出解答,結果是威爾打掃走廊時看見這道題目,趁著四下無人,他在黑板右邊寫下:
(1)

\displaystyle A=\begin{bmatrix} 0&1&0&1\\ 1&0&2&1\\ 0&2&0&0\\ 1&1&0&0 \end{bmatrix}

(2)

\displaystyle A^3=\left[\!\!\begin{array}{crrc} 2&7&2&3\\ 7&2&12&7\\ 2&12&0&2\\ 3&7&2&2 \end{array}\!\!\right]

(3)

\displaystyle \Gamma^{w}(p_i\to p_j;z)=\sum_{n=0}^\infty w_n(i\to j)z^n=\frac{\det(I_{ij}-zA_{ij})}{\det(I-zA)}

(4)

\displaystyle\begin{aligned} \left|\!\!\begin{array}{rrr} -z&0&-z\\ 1&-2z&-z\\ -z&0&1 \end{array}\!\!\right|\cdot\left|\!\!\begin{array}{rrrr} 1&-z&0&-z\\ -z&1&-2z&-z\\ 0&-2z&1&0\\ -z&-z&0&1 \end{array}\!\!\right|&=\frac{2z^2+2z^3}{1-7z^2-2z^3+4z^4}\\ &=2z^2+2z^3+14z^4+18z^5+94z^6+\cdots \end{aligned}

朗博教授讀了威爾的答案,臉上露出一絲微笑,滿意地說:「這是對的。」威爾果真答對所有的問題?現在還言之過早。古云:「盡信書不如無書。」這句話的「書」可改成「師」,意思就是不必照單全收老師說的話 (尤其是電影裡的老師)。

威爾正在閱讀朗博教授的問題 From http://twelvebytwelve.net/gwh-images/gwh-00079.jpg

 
問題 (1) 求圖 G 的鄰接矩陣 (adjacency matrix) A。圖 G(V,E) 包含頂點集合 V=\{1,2,3,4\} 和邊集合 E=\{\{1,2\},\{1,4\},\{2,3\},\{2,3\},\{2,4\}\},其中 \{i,j\} 代表頂點 ij 鄰接。注意,\{2,3\} 是一重邊 (multiedge),重數為 2。對應圖 G 的鄰接矩陣 A=[a_{ij}] 為一 4\times 4 階矩陣,其中 a_{ij} 表示頂點 i 連至 j 的邊數 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。因為 G 是一個無向圖 (undirected graph),A 是對稱矩陣。明顯地,威爾寫出了正確的鄰接矩陣 A

 
問題 (2) 要找出一矩陣使其 (i,j) 元等於從頂點 ij 且長度等於 3 的漫步 (walk) 總數。鄰接矩陣的冪矩陣 A^n(i,j)(A^n)_{ij} 即是從頂點 ij 且長度為 n 的漫步數。證明採用數學歸納法。若 n=1,則 A^n=A,鄰接矩陣直接指出連接各頂點長度為 1 的漫步數。假設 n=m 時命題成立,(A^{m})_{ij} 即為從 ij 且長度等於 m 的漫步數。寫出矩陣乘法表達式

\displaystyle (A^{m+1})_{ij}=\sum_{k=1}^n(A^{m})_{ik}a_{kj}

因為 a_{kj} 表示從頂點 kj 且長度為 1 的漫步數,立即推論 (A^{m+1})_{ij} 是從頂點 ij 且長度為 m+1 的漫步數。所以 A^3 即為所求,威爾答對了第二題。

 
問題 (3) 求從頂點 ij 的漫步數的母函數 (generating function,或稱生成函數)。一序列 \{a_n\}_0^\infty 的母函數是一種形式冪級數 (formal power series):

\displaystyle \Gamma(a_n;z)=\sum_{n=0}^\infty a_nz^n

w_n(i\to j) 代表從頂點 ij 且長度等於 n 的漫步數。根據題 (2),w_n(i\to j)=(A^n)_{ij}。因此,從頂點 ij 的漫步數的母函數為

\displaystyle \Gamma(w_n(i\to j);z)=\sum_{n=0}^\infty w_n(i\to j)z^n=\sum_{n=0}^\infty(A^n)_{ij}z^n

接下來的問題是如何計算無窮級數 \sum_{n=0}^\infty z^n(A^n)_{ij}?回想等比級數公式 \sum_{n=0}^\infty x^n=\frac{1}{1-x},其中 \vert x\vert <1。矩陣也存在類似的公式。若 \Vert zA\Vert<1,則 I-zA 是一可逆矩陣且

\displaystyle (I-zA)^{-1}=\sum_{n=0}^\infty (zA)^n

稱為 Neumann 無窮級數 (見“Neumann 無窮級數”)。所以,\Gamma(w_n(i\to j);z) 即為 (I-zA)^{-1}(i,j) 元。使用克拉瑪公式衍生的逆矩陣公式 (見“伴隨矩陣”)

\displaystyle B^{-1}=\frac{1}{\det B}\hbox{adj}B

其中 \hbox{adj}BB 的伴隨矩陣 (adjugate 或 classical adjoint),(\hbox{adj}B)_{ij}b_{ji} 的餘因子 (cofactor),即

\displaystyle (\hbox{adj}B)_{ij}=(-1)^{i+j}\det\tilde{B}_{ji}

這裡 \tilde{B}_{ji} 表示移除 B 的第 j 列和第 i 行後所得的子陣。將 B=I-zA 代入逆矩陣公式,(I-zA)^{-1}(i,j) 元有下列算式:

\displaystyle \left((I-zA)^{-1}\right)_{ij}=\frac{(-1)^{i+j}\det(\tilde{I}_{ji}-z\tilde{A}_{ji})}{\det (I-zA)}

因為 I-zA 是對稱矩陣,\tilde{I}_{ji}-z\tilde{A}_{ji}=\tilde{I}_{ij}-z\tilde{A}_{ij},故漫步數的母函數為

\displaystyle \Gamma(w_n(i\to j);z)=\sum_{n=0}^\infty w_n(i\to j)z^n=(-1)^{i+j}\frac{\det(\tilde{I}_{ij}-z\tilde{A}_{ij})}{\det (I-zA)}

威爾的解答有一個小錯,母函數公式遺漏了 (-1)^{i+j},大概是劇組或場務的疏忽。威爾將母函數寫成 \Gamma^w(p_i\to p_j;z),我不確定 p_i 代表甚麼意思 (可能是 point)。另外,他用 A_{ij} 表示刪除 4\times 4 階矩陣 A 的第 i 列和第 j 行之後得到的 3\times 3 階子陣。為了避免與 A(i,j) 元混淆,上面我用 \tilde{A}_{ij} 替代 A_{ij}

 
欲解出問題 (4),只要將 i=1j=3 代入題 (3) 導出的公式即可:

\displaystyle\begin{aligned} \Gamma(w_n(1\to 3);z)&=(-1)^{1+3}\frac{\det(\tilde{I}_{13}-z\tilde{A}_{13})}{\det (I-zA)}\\ &=\left|\!\!\begin{array}{rrr} -z&1&-z\\ 0&-2z&0\\ -z&-z&1 \end{array}\!\!\right|\cdot\left|\!\!\begin{array}{rrrr} 1&-z&0&-z\\ -z&1&-2z&-z\\ 0&-2z&1&0\\ -z&-z&0&1 \end{array}\!\!\right|^{-1}\\ &=\frac{2z^3+2z^2}{4z^4-2z^3-7z^2+1}\\ &=\frac{(z+1)2z^2}{(z+1)(4z^3-6z^2-z+1)}=\frac{2z^2}{4z^3-6z^2-z+1}. \end{aligned}

最後再將分式以多項式表示。寫出

\displaystyle f(z)=\frac{2z^2}{4z^3-6z^2-z+1}

利用泰勒展開式 f(z)=\sum_{k=0}^\infty\frac{f^{(k)}(0)}{k!}z^k,其中 f^{(k)}(0)f(z)0k 次導數,計算 (過程非常繁複) 可得

\displaystyle f(z)=2z^2+2z^3+14z^4+18z^5+94z^6+\cdots

在母函數 \Gamma(w_n(1\to 3);z),四階行列式是分母,但威爾的四階行列式外面少了上標 -1 (或前面漏了一個除號)。拍攝這個場景時,或許數學顧問未親臨片場以致於發生如此明顯的失誤。

 
朗博教授公告的挑戰問題看似困難,然而解答過程僅使用了幾個基本工具,包括等比級數公式、逆矩陣公式和泰勒展開式。藉由這個解題活動,我希望傳達一個正面訊息:即便我們不是數學天才,甚或對數學感到焦慮,但只要我們持續嘗試努力也能解開讓人望而生畏的難題。

 
註解:
[1] 紐約時報,2013年9月27日,“How to Fall in Love with Math?”,原文是 “The subject rarely appears in the news media or the cultural arena. Often, when math shows up in a novel or a movie, I am reminded of Chekhov’s proverbial gun: make sure the mathematician goes crazy if you put one in. Hanging thickly over everything is the gloom of math anxiety.” 中譯文取自中文版〈愛上神奇的數學〉。契訶夫諺語:「假如不打算開火,就別讓一支上膛的來福槍出現。」
[2] 維基百科:心靈捕手
[3] 字幕:
[Singing]
I love you forever, here in my heart…
STUDENT: Professor Lambeau.
LAMBEAU: Yes?
STUDENT: I’m in your applied theories class. We’re all up at the Math and Science building.
LAMBEAU: Come ‘ere…. It’s Saturday! Unless you wanna’ have a drink with me tonight.
STUDENT: …. Maybe …. We just couldn’t wait until Monday to find out.
LAMBEAU: Find out what?
STUDENT: Who proved the theorem.
[Hallway]
LAMBEAU: This is correct. Who did this? Jack?
STUDENT: Wasn’t me.
LAMBEAU: Nemesh?
STUDENT: No way.

繼續閱讀:
This entry was posted in 圖論 and tagged , , , , , , . Bookmark the permalink.

5 則回應給 電影《心靈捕手》的數學問題 (一)

  1. 張盛東 說:

    周老師,能否講解下生成函數?我在概率論見過moment generating function,在組合數學又見過exponential generating function。為何這些級數有這樣的性質?和線代有沒關係?

    • ccjou 說:

      你是說moment generating function和generating function的目的嗎?我再抽空討論,不過後者涉及的範圍很廣,要講清楚需要花費些功夫。他們和線性代數的關係不大,除了在某些應用(如本文的圖論例子)。

      • 張盛東 說:

        謝謝老師。在我上的諸多computer science課程和probability的課經常看到generating function這個詞,所以我很好奇這種函數到底有什麼奧妙,僅僅通過將研究的對象作為級數每一項的係數(很像一種變換),就可以從這個級數函數得到很多信息。

      • 張盛東 說:

        周老師,我昨天特意去看了這部電影了。我有個疑問,那個教授說走廊黑板的那道題是關於"Advanced Fourier System"的證明,但這道題好像好像和Fourier沒什麼關係啊。是不是編劇出錯?

  2. ccjou 說:

    你講的沒錯,確實牛頭不對馬嘴,但可能是製作單位的錯誤。維基百科說:
    http://zh.wikipedia.org/wiki/%E5%BF%83%E7%81%B5%E6%8D%95%E6%89%8B

    麥特·戴蒙,哈佛大學校友,原本想把主角塑造成物理學天才。他和當時的哈佛大學教授兼諾貝爾物理學獎得主Sheldon L. Glashow討論了該想法。Glashow告訴戴蒙他的假設並不成立,而且建議他把主角改寫成一個數學天才。他還介紹了在麻省理工擔任數學教授的姐夫/妹夫Daniel Kleitman給戴蒙認識,為電影提供意見。後來Glashow和Kleitman兩人的名字都在電影的致謝名單中出現。

    我懷疑題目是Kleitman提供的,不過或許沒有和編劇討論清楚。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s