Dodgson 縮合法──奇特的行列式運算法

本文的閱讀等級:中級

公元1865年英國數學家道奇森 (Charles Dodgson) 以筆名路易斯‧卡羅 (Lewis Carroll) 出版了影響深遠廣受世人喜愛的童話故事《愛麗絲夢遊仙境》(Alice’s Adventures in Wonderland)。當時流傳一則故事:維多利亞女王非常喜愛《愛麗絲夢遊仙境》,從而建議道奇森將下一本書獻給她。道奇森於是將隨後出版的數學著作《行列式初等論文》(An Elementary Treatise on Determinants) 呈給女王。不過,道奇森本人強烈否認這件事[1]。道奇森很可能是史上最出名的一位數學家,但他在數學方面的貢獻卻鮮為人知。1866年,道奇森發表了一個奇特的行列式運算法,名為縮合法 (condensation):給定一個 n\times n 階矩陣,逐步產生 (n-1)\times(n-1) 階,(n-2)\times(n-2) 階矩陣,直至得到一個 1\times 1 階矩陣,此最小矩陣的元即為原本給定矩陣的行列式。若拿縮合法與愛麗絲的奇幻旅程對比,縮合法不就是那瓶標示著「喝我」(DRINK ME),並讓愛麗絲像「單筒望遠鏡」那樣縮小的飲料嗎?

 
在介紹縮合法之前,我們先引入一個定義。設 A 為一個 n\times n 階矩陣,n\ge 3,刪除 A 的首列和末列,以及首行和末行,可得到 (n-2)\times(n-2) 階矩陣,稱為 A 的內陣 (interior),記作 \mathrm{int}A,例如,

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

的內陣是

\mathrm{int}A=\left[\!\!\begin{array}{rr}  -2&1\\    3&-1    \end{array}\!\!\right]

不論給定的矩陣尺寸為何,Dodgson 縮合法僅涉及 2\times 2 階行列式運算,以下是完整的演算法:

(1) 設 A=[a_{ij}] 為一個 n\times n 階矩陣。若內陣 \mathrm{int}A 包含零元,在不改變行列式的前提下,對 A 執行基本列運算或行運算,目標在產生一個新矩陣使其內陣不含零元,並以此新矩陣替換原矩陣 A

(2) 計算 A 的所有相鄰 2\times 2 階行列式,將結果合併為一個 (n-1)\times(n-1) 階矩陣,記作 B=[b_{ij}],亦即對於 i,j=1,\ldots,n-1

b_{ij}\leftarrow\begin{vmatrix}  a_{ij}&a_{i,j+1}\\    a_{i+1,j}&a_{i+1,j+1}    \end{vmatrix}

(3) 對 B 執行步驟 (2) 的運算,得到 (n-2)\times(n-2) 階矩陣 C=[c_{ij}],再將 C 矩陣各元分別除以內陣 \mathrm{int}A 的對應元,重設此結果為 C,算式如下:對於 i,j=1,\ldots,n-2

\begin{aligned}  c_{ij}&\leftarrow\begin{vmatrix}  b_{ij}&b_{i,j+1}\\    b_{i+1,j}&b_{i+1,j+1}    \end{vmatrix}\\  c_{ij}&\leftarrow\displaystyle\frac{c_{ij}}{a_{i+1,j+1}}\end{aligned}

(4) 設 A\leftarrow BB\leftarrow C,返回步驟 (3) 直到 C1\times 1 階矩陣,所含的元即為 \det A

‘Oh, how I wish I could shut up like a telescope! I think I could, if I only know how to begin.’

 
我們用上例 A 解說縮合法的運算過程。此例 \mathrm{int}A 不含零元,我們直接進入步驟 (2),得到 3\times 3 階矩陣,如下:

\begin{aligned}  B&=\begin{bmatrix}  \left|\!\!\begin{array}{cr}    2&1\\    1&-2    \end{array}\!\!\right|&\left|\!\!\begin{array}{rc}    1&1\\    -2&1    \end{array}\!\!\right|&\begin{vmatrix}    1&2\\    1&0    \end{vmatrix}\\    ~&~&~\\    \left|\!\!\begin{array}{cr}    1&-2\\    1&3    \end{array}\!\!\right|&\left|\!\!\begin{array}{rr}    -2&1\\    3&-1    \end{array}\!\!\right|&\left|\!\!\begin{array}{rr}    1&0\\    -1&-1    \end{array}\!\!\right|\\    ~&~&~\\    \begin{vmatrix}    1&3\\    0&2    \end{vmatrix}&\begin{vmatrix}    3&-1\\    2&-3    \end{vmatrix}&\left|\!\!\begin{array}{rr}    -1&-1\\    -3&1    \end{array}\!\!\right|    \end{bmatrix}=\left[\!\!\begin{array}{rrr}    -5&3&-2\\    5&-1&-1\\    2&-7&-4    \end{array}\!\!\right]\end{aligned}

使用同樣的縮小方法,步驟 (3) 先算出 2\times 2 階矩陣:

\begin{bmatrix}  \left|\!\!\begin{array}{rr}    -5&3\\    5&-1    \end{array}\!\!\right|&\left|\!\!\begin{array}{rr}    3&-2\\    -1&-1    \end{array}\!\!\right|\\    ~&~\\    \begin{vmatrix}    5&-1\\    2&-7    \end{vmatrix}&\begin{vmatrix}    -1&-1\\    -7&-4    \end{vmatrix}    \end{bmatrix}=\begin{bmatrix}    -10&-5\\    -33&-3    \end{bmatrix}

接著以元對元方式將 \begin{bmatrix}    -10&-5\\    -33&-3    \end{bmatrix} 「除以」 \mathrm{int}A=\left[\!\!\begin{array}{rr}    -2&1\\    3&-1    \end{array}\!\!\right],即得

\begin{aligned}  C&=\begin{bmatrix}  -10/-2&-5/1\\    -33/3&-3/-1    \end{bmatrix}=\left[\!\!\begin{array}{rr}    5&-5\\    -11&3    \end{array}\!\!\right]\end{aligned}

步驟 (4) 重設 A\leftarrow BB\leftarrow C\mathrm{int}A\leftarrow\begin{bmatrix}    -1    \end{bmatrix}。回到步驟 (3),再計算 \begin{bmatrix}    \left|\!\!\begin{array}{rr}    5&-5\\    -11&3    \end{array}\!\!\right|\end{bmatrix}=\begin{bmatrix}    -40    \end{bmatrix},立得 C=\begin{bmatrix}    -40/-1    \end{bmatrix}=\begin{bmatrix}    40    \end{bmatrix},故 \det A=40

This time she found a little bottle on it, and round the neck of the bottle was a paper label, with the words ‘DRINK ME’ beautifully printed on it in large letters.

 
縮合法的主要缺點在於內陣不允許零元,且事先無法判斷;一旦發生這個情況,我們只能退回起點重新產生一個符合要求的新矩陣。道奇森曾在論文中舉下例說明此狀況:

\begin{aligned}  \left[\!\!\begin{array}{crrrr}  2&-1&2&1&-3\\    1&2&1&-1&2\\    1&-1&-2&-1&-1\\    2&1&-1&-2&-1\\    1&-2&-1&-1&2    \end{array}\!\!\right]&\to\left[\!\!\begin{array}{rrrr}    5&-5&-3&-1\\    -3&-3&-3&3\\    3&3&3&-1\\    -5&-3&-1&-5    \end{array}\!\!\right]\to\left[\!\!\begin{array}{rrr}    -15&6&12\\    0&0&6\\    6&-6&8    \end{array}\!\!\right]\end{aligned}

不幸地,3\times 3 階矩陣其內陣為 \begin{bmatrix}    0    \end{bmatrix},運算程序被迫停止。他建議的補救方法是令 A 的首列移至最末列,此步驟共執行四次列交換,故行列式值維持不變。對新矩陣重啟運算程序,結果如下:

\begin{aligned}  \left[\!\!\begin{array}{crrrr}  1&2&1&-1&2\\    1&-1&-2&-1&-1\\    2&1&-1&-2&-1\\    1&-2&-1&-1&2\\    2&-1&2&1&-3    \end{array}\!\!\right]&\to\left[\!\!\begin{array}{rrrr}    -3&-3&-3&3\\    3&3&3&-1\\    -5&-3&-1&-5\\    3&-5&1&1    \end{array}\!\!\right]\to\left[\!\!\begin{array}{rrr}    0&0&6\\    6&-6&8\\    -17&8&-4    \end{array}\!\!\right]\to\left[\!\!\begin{array}{rc}    0&12\\    18&40    \end{array}\!\!\right]\to\begin{bmatrix}    36    \end{bmatrix}\end{aligned}

最後得到行列式值 36

 
我們不免好奇縮合法究竟從何而來,背後的運作原理又是什麼?道奇森並未於論文中明講,僅提到此法源自一個著名的行列式定理,後人歸結這個著名的定理應是 Desnanot-Jacobi 恆等式[2,3]。設 A=[a_{ij}]n\times n 階矩陣,令 A_i^j 代表去除 A 的第 i 列和第 j 行後得到的 (n-1)\times(n-1) 階矩陣,而 A_{i,j}^{p,q} 則代表去除 A 的第 ij 列與第 pq 行所得的 (n-2)\times(n-2) 階矩陣,下式即為 Desnanot-Jacobi 恆等式 (證明見本文最末段):

(\det A)(\det A_{1,n}^{1,n})=(\det A_1^1)(\det A_n^n)-(\det A_1^n)(\det A_n^1)

\det A_{1,n}^{1,n}\neq 0,則

\det A=\displaystyle\frac{\begin{vmatrix}  \det A_n^n&\det A_n^1\\    \det A_1^n&\det A_1^1    \end{vmatrix}}{ \det A_{1,n}^{1,n}}

設「空矩陣」,即 0\times 0 階矩陣的行列式為 1,上式給出所有方陣行列式的唯一定義,不僅如此,任意方陣 A 的行列式可寫為 2\times 2 階行列式的遞迴形式。Dodgson 縮合法的高明之處即在於巧妙地將 Desnanot-Jacobi 恆等式包裝成一個易於執行的運算程序。為方便說明,令 A(0)=A,縮合法的演算結果為一串 (n-k)\times(n-k) 階矩陣 A(k)k=1,2,\ldots,n-1。上例中,

\begin{aligned}  A(0)=\left[\!\!\begin{array}{crrr}  2&1&1&2\\    1&-2&1&0\\    1&3&-1&-1\\    0&2&-3&1    \end{array}\!\!\right]&\to A(1)=\left[\!\!\begin{array}{rrr}    -5&3&-2\\    5&-1&-1\\    2&-7&-4    \end{array}\!\!\right]\\    &\to A(2)=\left[\!\!\begin{array}{rr}    5&-5\\    -11&3    \end{array}\!\!\right]\\  &\to A(3)=\begin{bmatrix}    40    \end{bmatrix}\end{aligned}

根據 Desnanot-Jacobi 恆等式,

\begin{aligned}  \det A_1^4&=\left|\!\!\begin{array}{crr}  1&-2&1\\    1&3&-1\\    0&2&-3    \end{array}\!\!\right|=\displaystyle\frac{\begin{vmatrix}    \left|\!\!\begin{array}{cr}    1&-2\\    1&3    \end{array}\!\!\right|&\left|\!\!\begin{array}{rr}    -2&1\\    3&-1    \end{array}\!\!\right|\\    ~&~\\    \begin{vmatrix}    1&3\\    0&2    \end{vmatrix}&\begin{vmatrix}    3&-1\\    2&-3    \end{vmatrix}    \end{vmatrix}}{\det\begin{bmatrix}    3    \end{bmatrix}}=\frac{\begin{vmatrix}    5&-1\\    2&-7    \end{vmatrix}}{3}=-11\end{aligned}

上式與縮合法比較,發現 (A(2))_{21}=\det A_1^4,進一步可確認

A(2)=\begin{bmatrix}  \det A_4^4&\det A_4^1\\    \det A_1^4&\det A_1^1    \end{bmatrix}

 
歸納至一般情況,縮合法中間結果 A(k) 的各個元恰等於 A 的相鄰 (k+1)\times(k+1) 階分塊行列式,因此最後得到 1\times 1 階矩陣 A(n-1) 的元即為整個 n\times n 階矩陣 A 的行列式。

 
以下是 Desnanot-Jacobi 恆等式的證明。令 b_{ij}=(-1)^{i+j}\det A_i^j,並設

B=\begin{bmatrix}  b_{11}&0&0&\cdots&0&b_{n1}\\    b_{12}&1&0&\cdots&0&b_{n2}\\    b_{13}&0&1&\cdots&0&b_{n3}\\    \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\    b_{1,n-1}&0&0&\cdots&1&b_{n,n-1}\\    b_{1n}&0&0&\cdots&0&b_{nn}    \end{bmatrix}

注意,B 和伴隨矩陣 \mathrm{adj}A 的首行與末行相同。利用行列式的餘因子展開公式 (見“行列式的運算公式與性質”),計算確認

AB=\begin{bmatrix}  \det A&a_{12}&a_{13}&\cdots&a_{1,n-1}&0\\    0&a_{22}&a_{23}&\cdots&a_{2,n-1}&0\\    0&a_{32}&a_{33}&\cdots&a_{3,n-1}&0\\    \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\    0&a_{n-1,2}&a_{n-1,3}&\cdots&a_{n-1,n-1}&0\\    0&a_{n2}&a_{n3}&\cdots&a_{n,n-1}&\det A    \end{bmatrix}

同樣利用餘因子展開計算 AB 的行列式,可得

\begin{aligned}  \det(AB)&=(\det A) \begin{vmatrix}  a_{22}&a_{23}&\cdots&a_{2,n-1}&0\\    a_{32}&a_{33}&\cdots&a_{3,n-1}&0\\    \vdots&\vdots&\ddots&\vdots&\vdots\\    a_{n-1,2}&a_{n-1,3}&\cdots&a_{n-1,n-1}&0\\    a_{n2}&a_{n3}&\cdots&a_{n,n-1}&\det A    \end{vmatrix}\\    &=(\det A)^2 \begin{vmatrix}    a_{22}&a_{23}&\cdots&a_{2,n-1}\\    a_{32}&a_{33}&\cdots&a_{3,n-1}\\    \vdots&\vdots&\ddots&\vdots\\    a_{n-1,2}&a_{n-1,3}&\cdots&a_{n-1,n-1}    \end{vmatrix}\\  &=(\det A)^2(\det A_{1,n}^{1,n})\end{aligned}

再以餘因子展開計算 B 的行列式,得到 \det B=b_{11}b_{nn}-b_{1n}b_{n1},但是 b_{11}=\det A_1^1b_{1n}=(-1)^{n+1}\det A_1^nb_{n1}=(-1)^{n+1}\det A_n^1b_{nn}=A_n^n,所以

\det B=\begin{vmatrix}  \det A_n^n&\det A_n^1\\    \det A_1^n&\det A_1^1    \end{vmatrix}

利用矩陣乘積行列式可乘公式 \det(AB)=(\det A)(\det B),就有

(\det A)^2\det A_{1,n}^{1,n}=(\det A) \begin{vmatrix}  \det A_n^n&\det A_n^1\\    \det A_1^n&\det A_1^1    \end{vmatrix}

\det A\neq 0,等號兩邊同時消去 \det A 即證得所求。若 \det A=0,將 AA+\epsilon I 取代,使得 \det(A+\epsilon I)\neq 0,當 \epsilon\to 0,運用連續論證法即得證 (詳見“連續論證法”)。

 
參考來源:
[1] 維基百科:Lewis Carroll
[2] 維基百科:Dodgson Condensation
[3] Adrian Rice and Eve Torrence, “Shutting up like a telescope”: Lewis Carroll’s “Curious” Condensation Method for Evaluating Determinants, College Mathematics Journal, Vol. 38, No. 2, 2007, 85-95.

Advertisements
本篇發表於 線性代數專欄, 行列式 並標籤為 , , , 。將永久鏈結加入書籤。

2 則回應給 Dodgson 縮合法──奇特的行列式運算法

  1. 陳冠羽 說道:

    我發現在3×3階矩陣,內陣為[0]的例子中可以用epsilon代替0,繼續進行運算,最後一樣可以算出36。 不曉得適不適合一般情況?

    • ccjou 說道:

      你提出的想法很有意思。行列式是各個元的連續函數,所以用一個極小的數 \epsilon 取代內陣[0],最後再令 \epsilon\to 0 亦可得到答案。不過,這個作法僅適宜手算,應用於數值計算將因除以 \epsilon 而引入誤差。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s