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

本文的閱讀等級:中級

二項式定理 (binomial theorem) 由牛頓於公元1664-65年間提出,此定理給出 x+y 的整數次冪展開公式:

\displaystyle (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k

其中 \binom{n}{k}=\frac{n!}{k!(n-k)!}nk 的組合數目,稱為二項式係數,它遵守帕斯卡(Pascal)法則:

\displaystyle\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}

證明如下。令 \Psi 表示 n 個元素構成的集合,設 x\in\Psi,由 \Psi 中選取 k 個元素可分開兩種情況討論:若不取 x,則必須從 \Psi\setminus\{x\} 選取 k 個元素,組合數為 \binom{n-1}{k};若選取 x,則還要從 \Psi\setminus\{x\} 取其餘 (k-1) 個元素,組合數為 \binom{n-1}{k-1}。帕斯卡法則的代數證明請見“二項式係數公式”。

 
帕斯卡三角形是二項式係數遞歸關係的一種三角形陣列排序,前面七列如下:

\begin{array}{ccccccccccccc} &&& &&& 1&&&&&&\\ &&&&& 1  & &  1 &&&&&\\ &&&& 1  & & 2  & &  1 &&&&\\ &&&1 && 3 && 3&& 1 &&&\\ &&1&& 4&&6&&4&&1&&\\ &1&&5&&10&&10&&5&&1&\\ 1&&6&&15&&20&&15&&6&&1 \end{array}

首列標記為 n=0,每列左起為 k=0,例如,第五列 (n=4) 的第三個元 (k=2) 是 \binom{n}{k}=\binom{4}{2}=6。擷取帕斯卡三角形最前 n 列,右邊補足 0,即構成一 n\times n 階下三角矩陣 P=[p_{ij}],稱為帕斯卡矩陣[1],定義如下:若 i\ge j,則 p_{ij}=\binom{i-1}{j-1},否則 p_{ij}=0。下面列出前四個:

\begin{bmatrix} 1 \end{bmatrix},~\begin{bmatrix}  1&0\\  1&1  \end{bmatrix},~\begin{bmatrix}  1&0&0\\  1&1&0\\  1&2&1  \end{bmatrix},~\begin{bmatrix}  1&0&0&0\\  1&1&0&0\\  1&2&1&0\\  1&3&3&1  \end{bmatrix}

 
帕斯卡矩陣 P 的主對角元都是1,故 \det P=1P 是可逆矩陣。計算發現

\begin{aligned} \begin{bmatrix} 1&0\\  1&1  \end{bmatrix}^{-1}&=\left[\!\!\begin{array}{rc}  1&0\\  -1&1  \end{array}\!\!\right],\\  \begin{bmatrix}  1&0&0\\  1&1&0\\  1&2&1  \end{bmatrix}^{-1}&=\left[\!\!\begin{array}{rrc}  1&0&0\\  -1&1&0\\  1&-2&1  \end{array}\!\!\right],\\  \begin{bmatrix}  1&0&0&0\\  1&1&0&0\\  1&2&1&0\\  1&3&3&1  \end{bmatrix}^{-1}&=\left[\!\!\begin{array}{rrrc}  1&0&0&0\\  -1&1&0&0\\  1&-2&1&0\\  -1&3&-3&1  \end{array}\!\!\right];\end{aligned}

前面幾個帕斯卡矩陣與其逆矩陣呈現一種特殊關係:P^{-1} 的每個元的絕對值和 P 的對應元相同,但其正負號如棋盤交錯排列。考慮一般情況,定義 n\times n 階矩陣 Q=[q_{ij}] 如下:若 i\ge jq_{ij}=(-1)^{i-j}\binom{i-1}{j-1},否則 q_{ij}=0。下面我們利用二項式定理來證明 Q=P^{-1}。兩個下三角矩陣乘積仍為下三角矩陣,所以對於 i<j,必有 (PQ)_{ij}=0,且當 i=j(PQ)_{ij}=1。接下來只要證明當 i>j(PQ)_{ij}=0 即可。考慮 i>j,寫出 i=j+ll>0,細心推導可得

\displaystyle\begin{aligned} (PQ)_{ij}&=\sum_{k=0}^{l}p_{i,j+k}q_{j+k,j}=\sum_{k=0}^{l}p_{j+l,j+k}q_{j+k,j}\\ &=\sum_{k=0}^{l}\binom{j+l-1}{j+k-1}(-1)^{2j+k}\binom{j+k-1}{j-1}\\ &=\sum_{k=0}^{l}\frac{(j+l-1)!}{(j+k-1)!(l-k)!}\frac{(j+k-1)!}{(j-1)!k!}(-1)^k\\ &=\sum_{k=0}^l\frac{(j+l-1)!}{(l-k)!(j-1)!k!}(-1)^k\\ &=\frac{(j+l-1)!}{(j-1)!l!}\sum_{k=0}^l\frac{l!}{(l-k)!k!}(-1)^k\\ &=\binom{j+l-1}{j-1}\sum_{k=0}^l\binom{l}{k}(-1)^k\\ &=\binom{i-1}{j-1}\sum_{k=0}^l\binom{l}{k}(1)^{l-k}(-1)^k\\ &=\binom{i-1}{j-1}(1+(-1))^l=0,\end{aligned}

整個證明的關鍵在於最後一個步驟:提出 \binom{i-1}{j-1} 並以二項式定理表達 (1+(-1))^l

 
帕斯卡矩陣 P 的冪矩陣 P^k 是否也有簡易的計算公式?從逆矩陣 P^{-1} (即 Q) 的形式,很容易將帕斯卡矩陣予以推廣。定義 n\times n 階下三角矩陣 P(t) 如下:若 i\ge j(P(t))_{ij}=t^{i-j}\binom{i-1}{j-1},否則 (P(t))_{ij}=0。譬如,若 n=4

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=P(1)P^{-1}=P(-1),那麼對於任何整數 k,是否也有 P^k=P(k)?答案是肯定的。我們需要下面的恆等式:若 k 為一正整數,

P(k)=P(1)P(k-1)

重複前述證明方法,抽離出係數後再引用 (1+(k-1))^l 的二項式定理展開式即可證明上式成立。因為 P(0)=IP(1)=P,就有

\begin{aligned} P(k)&=P(1)P(k-1)=P(1)(P(1)P(k-2))=(P(1))^2P(k-2)=\cdots\\ &=(P(1))^kP(0)=P^kI=P^k;\end{aligned}

根據 P(t) 的定義,同樣有 P(-k)=(P(k))^{-1}=(P^{k})^{-1}=P^{-k}

 
對於任意實數 tP^t=P(t) 是否也成立?不妨從代數中找尋靈感。對於實數 a>0,我們知道 a^t=e^{ht},其中 h=\ln a。如法炮製,我們也期待 P^t 可以表示為矩陣指數 (見“矩陣指數”),即存在一方陣 H 使得 P(t)=e^{Ht}。下一個問題是如何找出 H。為了從 P(t) 抽取 H,我們對 P(t)=e^{Ht} 微分,結果如下:

\displaystyle \frac{d}{dt}P(t)=\frac{d}{dt}e^{Ht}=He^{Ht}=HP(t)

代入 t=0,可得

\displaystyle \left.\frac{d}{dt}P(t)\right|_{t=0}=HP(0)=HI=H

看一個例子,若 n=4

\displaystyle \frac{d}{dt}P(t)=\begin{bmatrix} 0&0&0&0\\ 1&0&0&0\\ 2t&2&0&0\\ 3t^2&6t&3&0 \end{bmatrix}

因此

\displaystyle H=\left.\frac{d}{dt}P(t)\right|_{t=0}=\begin{bmatrix} 0&0&0&0\\ 1&0&0&0\\ 0&2&0&0\\ 0&0&3&0 \end{bmatrix}

這個結果透露一般 n\times nH 矩陣極可能有相仿型態,於是我們將此特例推廣至一般情況。考慮 n\times n 階矩陣 H=[h_{ij}],各元定義如下:若 i=j+1h_{ij}=j,否則 h_{ij}=0。當 n=4

H^2=\begin{bmatrix} 0&0&0&0\\ 0&0&0&0\\ 2&0&0&0\\ 0&6&0&0 \end{bmatrix},~H^3=\begin{bmatrix} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 6&0&0&0 \end{bmatrix},~H^4=0,

由此推論一般 n\times nH 是冪零 (nilpotent) 矩陣 (見“特殊矩陣(1):冪零矩陣”),即當 k\ge nH^k=0。若 k<n,運用歸納法不難證明:若 i=j+k(H^k)_{ij}=\frac{(i-1)!}{(j-1)!},否則 (H^k)_{ij}=0

 
準備就緒,下面我們證明 P(t)=e^{Ht}。若 t=0,則 P(t)=P(0)=Ie^{Ht}=e^0=I。若 t\neq 0,因為當 k\ge nH^k=0,就有

\displaystyle e^{Ht}=I+tH+\frac{t^2}{2!}H^2+\cdots+\frac{t^{n-1}}{(n-1)!}H^{n-1}

由上式等號右邊判斷 e^{H t} 是下三角矩陣,且主對角元全都為 1。若 i>j,令 k=i-j,等號右邊矩陣和僅有 (t^k/k!)H^k(i,j) 元不為零,故

\displaystyle (e^{Ht})_{ij}=\frac{t^k}{k!}(H^k)_{ij}=t^{k}\frac{(i-1)!}{(i-j)!(j-1)!}=t^{i-j}\binom{i-1}{j-1}=(P(t))_{ij}

因此得證。

 
利用 P(t)=e^{Ht},即知對於任意實數 st

P(s)P(t)=e^{Hs}e^{Ht}=e^{H(s+t)}=P(s+t)

(P(t))^{-1}=(e^{Ht})^{-1}=e^{-Ht}=P(-t)

這說明 P^t=P(t) 滿足指數性質:P^sP^t=P^{s+t}(P^t)^{-1}=P^{-t}。設 t=1/kk 為一正整數,立得 P 的根矩陣 P^{1/k}。當 n=4,例如,

P^{1/2}=P(1/2)=\left[\!\!\begin{array}{rrrc} 1&0&0&0\\ 1/2&1&0&0\\ 1/4&1&1&0\\ 1/8&3/4&3/2&1 \end{array}\!\!\right],~~P^{1/3}=P(1/3)=\left[\!\!\begin{array}{rrcc} 1&0&0&0\\ 1/3&1&0&0\\ 1/9&2/3&0&0\\ 1/27&1/3&1&1 \end{array}\!\!\right]

t=1,帕斯卡矩陣可表示成矩陣指數:P=e^H,所以 H 也稱為創造 (creation) 矩陣或衍生 (derivation) 矩陣。下文將繼續探討帕斯卡矩陣 P 與創造矩陣 H 的其他相關性質。

 
參考文獻:
[1] G. Call and D. Velleman, Pascal’s matrices, The American Mathematical Monthly, Vol. 100, No. 4, 1993, pp 372-376.

繼續閱讀:
廣告
本篇發表於 特殊矩陣, 線性代數專欄 並標籤為 , , , , , , , , , 。將永久鏈結加入書籤。

One Response to 特殊矩陣 (15):Pascal 矩陣 (上)

  1. suehang 說道:

    杨辉三角形的矩阵分析,很有意思,之前未见人做过,学习!

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s