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

$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}

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

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

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

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

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

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

$\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)}$

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

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

[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 電影《心靈捕手》的數學問題 (一)

1. 張盛東 說道：

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

• ccjou 說道：

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

• 張盛東 說道：

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

• 張盛東 說道：