特殊矩陣 (15):Pascal 矩陣 (下)

本文的閱讀等級:中級

我們將前文“特殊矩陣 (15):Pascal 矩陣 (上)”的主要結果整理於下。首先定義一 n\times n 階創造矩陣 H=[h_{ij}]:若 i=j+1h_{ij}=j,否則 h_{ij}=0。創造矩陣 H 衍生出矩陣指數,如下:

\displaystyle  P(t)=e^{Ht}=\sum_{k=0}^{\infty}\frac{t^k}{k!}H^k

其中 t 是實數。因為 H 是冪零矩陣,即對於 k\ge nH^k=0,故 P(t) 可表示為 Hn-1 次多項式:

\displaystyle  P(t)=\sum_{k=0}^{n-1}\frac{t^k}{k!}H^k

代入 t=0,可得 P(0)=I;代入 t=1,可得 P(1)=e^{H}。展開上式等號右邊即推得 P(t)(i,j) 元:若 i\ge j(P(t))_{ij}=t^{i-j}\binom{i-1}{j-1},否則 (P(t))_{ij}=0。提醒讀者,我們定義 \binom{i}{0}=1i\ge 0\binom{0}{j}=0j>0。令帕斯卡矩陣為 P=[p_{ij}]=P(1)=e^H (亦即若 i\ge jp_{ij}=\binom{i-1}{j-1},否則 p_{ij}=0),所以對於任意實數 tP(t)=e^{Ht}=P^t,並有以下必然結果:

P(s)P(t)=P(s+t)

s=-t,即得 P(-t)P(t)=P(0)=I,故 P^t 是可逆矩陣,且 (P^t)^{-1}=P(t)^{-1}=P(-t);當 t=1,就得到帕斯卡逆矩陣 P^{-1}=P(-1)。下面是 n=4 的例子:

H=\begin{bmatrix}  0&0&0&0\\    1&0&0&0\\    0&2&0&0\\    0&0&3&0    \end{bmatrix},~P(t)=\begin{bmatrix}    1&0&0&0\\    t&1&0&0\\    t^2&2t&1&0\\    t^3&3t^2&3t&1    \end{bmatrix},

P=\begin{bmatrix}  1&0&0&0\\    1&1&0&0\\    1&2&1&0\\    1&3&3&1    \end{bmatrix},~P^{-1}=\left[\!\!\begin{array}{rrrc}  1&0&0&0\\  -1&1&0&0\\  1&-2&1&0\\  -1&3&-3&1  \end{array}\!\!\right]

本文將繼續探討創造矩陣 H、矩陣指數 P(t) 和帕斯卡矩陣 P 的其他性質[1]

 
因為 P(t) 的主對角元皆為1,P(t) 的特徵值全部是1。若 t\neq 0\dim N(P(t)-I)=1,得知 P(t) 僅有一特徵向量 (0,\ldots,0,1),故不可對角化。定義 n\times n 階對角矩陣 D(t)=\mathrm{diag}(1,t,t^2,\ldots,t^{n-1}),若 t\neq 0,則

P(t)=D(t)PD(t)^{-1}

只要 t\neq 0P(t) 相似於帕斯卡矩陣 P,即知 \{P(t)\vert t\neq 0\} 組成一相似矩陣大家庭,帕斯卡逆矩陣 P^{-1} 也是其中成員:

P^{-1}=P(-1)=D(-1)PD(-1)^{-1}

另外,由於 P(t)H 的多項式,立得 P(t)H=HP(t),故 P(t)H 是可交換矩陣。

 
運用 P^t=P(t) 很容易推導出二項式係數的一些恆等式。當 t=2,比較 P^2=P(2) 等號兩邊的 (i,j) 元,可知

\displaystyle  \sum_{k=j}^i\binom{i-1}{k-1}\binom{k-1}{j-1}=2^{i-j}\binom{i-1}{j-1},~~~i\ge j

代入 i=n+1j=1,因為 \binom{k}{0}=1,可得

\displaystyle  \sum_{k=1}^{n+1}\binom{n}{k-1}\binom{k-1}{0}=\sum_{k=0}^n\binom{n}{k}=2^n

代入 i=n+1j=2,因為 \binom{k}{1}=k,可得

\displaystyle  \sum_{k=0}^nk\binom{n}{k}=n2^{n-1}

代入 i=n+1j=3,因為 \binom{k}{2}=k(k-1)/2,可得

\displaystyle  \sum_{k=0}^n\frac{k(k-1)}{2}\binom{n}{k}=\frac{n(n-1)}{2}2^{n-2}

再使用前一個恆等式,就有

\displaystyle\begin{aligned}  \sum_{k=0}^nk^2\binom{n}{k}&=(n^2-n)2^{n-2}+\sum_{k=0}^nk\binom{n}{k}\\    &=(n^2-n)2^{n-2}+n2^{n-1}\\  &=(n^2+n)2^{n-2},\end{aligned}

重複上述步驟可以推導出 \sum_{k=0}^nk^m\binom{n}{k} 的公式,m>2。若比較 P(1)P(-1)=I 等號兩邊的 (i,j) 元,可知

\displaystyle  \sum_{k=j}^i(-1)^k\binom{i-1}{k-1}\binom{k-1}{j-1}=(-1)^j\delta_{ij},~~~i\ge j

其中 \delta_{ij}=1i=j,否則 \delta_{ij}=0。將 i=n+1j=1 代入上式,即得到

\displaystyle  \sum_{k=0}^{n}(-1)^k\binom{n}{k}=0

 
既然帕斯卡矩陣來自帕斯卡三角形,我們不免好奇 n\times n 階帕斯卡矩陣如何由 (n-1)\times(n-1) 階帕斯卡矩陣生成?令 P_n 代表 n\times n 階帕斯卡矩陣,以 n=4 為例,將 P_4 化簡如下:

\left[\!\!\begin{array}{rrrc}  1&0&0&0\\    -1&1&0&0\\    0&-1&1&0\\    0&0&-1&1    \end{array}\!\!\right]\begin{bmatrix}    1&0&0&0\\    1&1&0&0\\    1&2&1&0\\    1&3&3&1    \end{bmatrix}=\begin{bmatrix}    1&0&0&0\\    0&1&0&0\\    0&1&1&0\\    0&1&2&1    \end{bmatrix}

注意 P_3 出現於右下 3\times 3 階分塊。推廣至一般情況,令 n\times n 階消元矩陣 E=[e_{ij}] 如下:e_{ii}=1e_{i,i-1}=-1,其他 e_{ij}=0。因為 EP_n 是下三角矩陣,考慮 i\ge j,乘開 EP_n,利用帕斯卡法則可得

\displaystyle\begin{aligned}  (EP_n)_{ij}&=(P_n)_{i,j}-(P_{n})_{i-1,j}\\    &=\binom{i-1}{j-1}-\binom{i-2}{j-1}=\binom{i-2}{j-2}\\  &=(P_{n})_{i-1,j-1},\end{aligned}

其中 (EP_n)_{11}=\binom{0}{0}-\binom{-1}{0}=1-0=1(EP_n)_{i1}=\binom{i-1}{0}-\binom{i-2}{0}=1-1=0i>1,因此證得

EP_n=\begin{bmatrix}  1&\mathbf{0}^T\\    \mathbf{0}&P_{n-1}\end{bmatrix}

為簡化符號,令 \hat{P}_{n}=\begin{bmatrix}    1&\mathbf{0}^T\\    \mathbf{0}&P_{n-1}    \end{bmatrix},也就有 P_n=E^{-1}\hat{P}_{n},不難驗證 (E^{-1})_{ij}=1i\ge j,否則 (E^{-1})_{ij}=0,譬如,當 n=4

E^{-1}=\begin{bmatrix}  1&0&0&0\\    1&1&0&0\\    1&1&1&0\\    1&1&1&1    \end{bmatrix}

對於 i\ge j,比較 P_n=E^{-1}\hat{P}_n 等號兩邊的 (i,j) 元,便得到下面的二項式係數恆等式:

\displaystyle  (E^{-1}\hat{P}_{n})_{ij}=\sum_{k=1}^n(E^{-1})_{ik}(\hat{P}_n)_{kj}=\sum_{k=j}^i\binom{k-2}{j-2}=\binom{i-1}{j-1}

 
考慮帕斯卡矩陣 P 的交互乘積 S=PP^T,若 n=4

S=\begin{bmatrix}  1&0&0&0\\  1&1&0&0\\  1&2&1&0\\  1&3&3&1  \end{bmatrix}\begin{bmatrix}  1&1&1&1\\  0&1&2&3\\  0&0&1&3\\  0&0&0&1  \end{bmatrix}=\left[\!\!\begin{array}{ccrr}  1&1&1&1\\    1&2&3&4\\    1&3&6&10\\    1&4&10&20    \end{array}\!\!\right]

對稱矩陣 S=[s_{ij}] 擷取帕斯卡三角形的中央菱形部分,故稱為對稱帕斯卡矩陣,其中各元是 s_{ij}=\binom{i+j-2}{j-1}。運用組合數學證明 PP^TS 有相同的 (i,j) 元,即

\displaystyle  \sum_{k=1}^np_{ik}p_{jk}=\sum_{k=1}^n\binom{i-1}{k-1}\binom{j-1}{k-1}=\binom{i+j-2}{j-1}=s_{ij}

並不是一件容易的事。下面介紹一個簡單的證法 (其他證明方法請參閱[2])。我們何不反過來看這個問題?先假設 S 來自帕斯卡三角形。給定初始條件:s_{i0}=s_{0j}=0s_{11}=1s_{ij} 由下列遞歸關係產生:

s_{ij}=s_{i-1,j}+s_{i,j-1}

再來只要證明 S=PP^T 即可。運用數學歸納法,假設 S_{n-1}=P_{n-1}P_{n-1}^T,寫出

EP_nP_n^TE^T=(EP_n)(EP_n)^T=\begin{bmatrix}  1&\mathbf{0}^T\\    \mathbf{0}&P_{n-1}    \end{bmatrix}\begin{bmatrix}    1&\mathbf{0}^T\\    \mathbf{0}&P_{n-1}^T    \end{bmatrix}=\begin{bmatrix}    1&\mathbf{0}^T\\    \mathbf{0}&S_{n-1}    \end{bmatrix}

因為 E 可逆,若能夠證明 ES_nE^T=\begin{bmatrix}    1&\mathbf{0}^T\\    \mathbf{0}&S_{n-1}    \end{bmatrix},等於證明了 S_n=P_nP_n^T。考慮 (ES_n)(i,j) 元:

(ES_n)_{ij}=(S_n)_{ij}-(S_n)_{i-1,j}

由此可推得

(ES_nE^T)_{ij}=((S_n)_{ij}-(S_n)_{i-1,j})-((S_n)_{i,j-1}-(S_n)_{i-1,j-1})=(S_n)_{i-1,j-1}

最末一個步驟利用 (S_n)_{ij} 的遞歸生成性質將等號右邊前三項消去,故證得所求。

 
從對稱帕斯卡矩陣 S 和帕斯卡矩陣 P 的關係 S=PP^T 可以推演出什麼恆等式嗎?比較上式等號兩邊的主對角元,即得

\displaystyle  \sum_{k=1}^n\binom{i-1}{k-1}^2=\sum_{k=1}^{i-1}\binom{i-1}{k-1}^2=\binom{2i-2}{i-1}=i\cdot c_{i-1}

其中 c_i=\binom{2i}{i}/(i+1) 稱為卡塔蘭數 (Catalan numbers),相關討論請見“矩陣鏈乘積的最佳計算順序”。

 
下面我們說明對稱帕斯卡矩陣 S 的特徵值性質。因為 P 可逆,故知 S=PP^T 也可逆。令 D=D(-1)=\mathrm{diag}(1,-1,1,-1,\ldots),顯然 D^{-1}=D,則 P^{-1}=DPD^{-1}(P^T)^{-1}=DP^TD^{-1},利用這些關係式可導出

\begin{aligned}  S^{-1}&=(PP^T)^{-1}=(P^T)^{-1}P^{-1}\\  &=(DP^TD^{-1})(DPD^{-1})=DP^TPD^{-1}\\  &=(DP^T)(PP^T)(DP^T)^{-1}=(DP^T)S(DP^T)^{-1},\end{aligned}

即知 S^{-1} 相似於 S,故 S 的特徵值必須是成對的 \lambda1/\lambda,或者單獨的 \lambda=1。譬如,S_3 有特徵值 4+\sqrt{15},4-\sqrt{15},1

 
本文利用帕斯卡矩陣 P、對稱帕斯卡矩陣 PP^TP^t=P(t) 推導出一些二項式係數恆等式,有興趣深入探索更多二項式係數恆等式的讀者請參考維基百科。不過究竟有多少人會因認識這些恆等式與其證明而感到興奮?答案如何,大家心知肚明,但恐怕沒有人比美國計算機科學教授高德納 (Donald Knuth) 更坦率,他在大作《計算機程序設計的藝術》(Fundamental Algorithms: Volume I, The Art of Computer Programming) 中明白點破:

There are so many relations present that when someone finds a new identity, there aren’t many people who get excited about it any more, except the discoverer!

 
本文參考:
[1] L. Aceto and D. Trigiante, The Matrices of Pascal and Other Greats, The American Mathematical Monthly, Vol. 108, 2001, pp 232-245.
[2] A. Edelman and G. Strang, Pascal matrices, The American Mathematical Monthly,Vol. 111, 2004, pp 189-197.

This entry was posted in 特殊矩陣, 線性代數專欄 and tagged , , , , , , , . Bookmark the permalink.

3 則回應給 特殊矩陣 (15):Pascal 矩陣 (下)

  1. 延伸寸 說:

    Sing for the sake of singing.

    • ccjou 說:

      我想起電影「阿甘正傳」裡 Forrest Gump 講過的一段話(解釋他為何不停地跑步):

      That day, for no particular reason, I decided to go for a little run. So I ran to the end of the road. And when I got there, I thought maybe I’d run to the end of town. And when I got there, I thought maybe I’d just run across Greenbow County. And I figured, since I run this far, maybe I’d just run across the great state of Alabama. And that’s what I did. I ran clear across Alabama. For no particular reason I just kept on going. I ran clear to the ocean. And when I got there, I figured, since I’d gone this far, I might as well turn around, just keep on going. When I got to another ocean, I figured, since I’d gone this far, I might as well just turn back, keep right on going.

  2. ccjou 說:

    YouTube 有這段 i just felt like running 影片:

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s