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

本文的閱讀等級：中級

美國馬里蘭大學馬尼爾‧蘇里 (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

電影中沒有一個學生想出解答，結果是威爾打掃走廊時看見這道題目，趁著四下無人，他在黑板右邊寫下：
(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\}$ 代表頂點 $i$ 和 $j$ 鄰接。注意， $\{2,3\}$ 是一個重邊 (multiedge)，重數為 $2$ 。對應圖 $G$ 的鄰接矩陣 $A=[a_{ij}]$ 為一個 $4\times 4$ 階矩陣，其中 $a_{ij}$ 表示頂點 $i$ 連至 $j$ 的邊數 (見“線性代數在圖論的應用 (一)：鄰接矩陣”)。因為 $G$ 是一個無向圖 (undirected graph)， $A$ 是對稱矩陣。明顯地，威爾寫出了正確的鄰接矩陣 $A$ 。

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

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

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

問題 (3) 求從頂點 $i$ 至 $j$ 的漫步數的母函數 (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)$ 代表從頂點 $i$ 至 $j$ 且長度等於 $n$ 的漫步數。根據題 (2)， $w_n(i\to j)=(A^n)_{ij}$ 。因此，從頂點 $i$ 至 $j$ 的漫步數的母函數為

$\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}B$ 是 $B$ 的伴隨矩陣 (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=1$ ， $j=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)$ 在 $0$ 的 $k$ 次導數，計算 (過程非常繁複) 可得

$\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.

繼續閱讀：

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

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

張盛東 says:

10/01/2013 at 6:35 am

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

- ccjou says:
  
  10/01/2013 at 8:54 am
  
  你是說moment generating function和generating function的目的嗎？我再抽空討論，不過後者涉及的範圍很廣，要講清楚需要花費些功夫。他們和線性代數的關係不大，除了在某些應用(如本文的圖論例子)。
  
  - 張盛東 says:
    
    10/01/2013 at 9:10 am
    
    謝謝老師。在我上的諸多computer science課程和probability的課經常看到generating function這個詞，所以我很好奇這種函數到底有什麼奧妙，僅僅通過將研究的對象作為級數每一項的係數（很像一種變換），就可以從這個級數函數得到很多信息。
    
  - 張盛東 says:
    
    10/02/2013 at 9:41 am
    
    周老師，我昨天特意去看了這部電影了。我有個疑問，那個教授說走廊黑板的那道題是關於”Advanced Fourier System”的證明，但這道題好像好像和Fourier沒什麼關係啊。是不是編劇出錯？
    
ccjou says:

10/02/2013 at 10:40 am

你講的沒錯，確實牛頭不對馬嘴，但可能是製作單位的錯誤。維基百科說：
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提供的，不過或許沒有和編劇討論清楚。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨