Chiò 演算法──另類行列式計算法

本文的閱讀等級:初級

傳統的行列式手算方法多數採用餘因子 (cofactor) 展開,也稱為 Laplace 展開,作法是將高階行列式逐步降階至二階行列式,再以熟知的公式算出 (見“行列式的運算公式與性質”)。如下例,對第二列執行餘因子的展開式為

\begin{aligned}  \left|\!\!\begin{array}{rrc}    2&-5&4\\    1&0&3\\    -4&5&3    \end{array}\!\!\right|&=(-1)\left|\!\!\begin{array}{rc}    -5&4\\    5&3    \end{array}\!\!\right|+0\left|\!\!\begin{array}{rc}    2&4\\    -4&3    \end{array}\!\!\right|-3\left|\!\!\begin{array}{rr}    2&-5\\    -4&5    \end{array}\!\!\right|\\    &=(-1)(-15-20)-3(10-20)=65.\end{aligned}

對於尺寸較大的行列式,餘因子展開式的麻煩是必須經過多次降階,寫出的展開式因此相當繁複。

 
高斯消去法也常應用於行列式的計算:將矩陣化簡為上三角矩陣,行列式值即為該矩陣的主對角元乘積。基本列運算的取代運算 (將某一列的倍數加進另一列) 並不會改變行列式值,列交換運算 (交換兩列) 反轉行列式正負號,而伸縮運算 (將一列乘以非零常數 k) 則使行列式伸縮 k 倍。如下例,先將第一列和第二列交換,再執行消去運算:

\begin{aligned}  \left|\!\!\begin{array}{rrc}    2&-5&4\\    1&0&3\\    -4&5&3    \end{array}\!\!\right|&=-\left|\!\!\begin{array}{rrc}    1&0&3\\    2&-5&4\\    -4&5&3    \end{array}\!\!\right|=-\left|\!\!\begin{array}{crr}    1&0&3\\    0&-5&-2\\    0&5&15    \end{array}\!\!\right|=-\left|\!\!\begin{array}{crr}    1&0&3\\    0&-5&-2\\    0&0&13    \end{array}\!\!\right|\\  &=-1\cdot(-5)\cdot 13=65.\end{aligned}

 
本文介紹一種幾乎失傳的另類行列式計算法,由義大利數學家奇奧 (Felice Chiò) 於公元1853年提出[1]。Chiò 演算法將給定的 n 階行列式降為一個 (n-1) 階行列式,繼續再降為 (n-2) 階行列式,重複此過程直到得出一個低階 (三階或二階) 行列式。整個過程僅涉及二階行列式計算,因此運算操作非常簡易。下面先介紹 Chiò 演算法的計算程序,再詳述此法的證明。

 
A=[a_{ij}] 為一 n\times n 階矩陣,且 a_{nn}\neq 0,稱為軸元 (pivot element),稍後會說明如何將此限制排除。令 D=[d_{ij}] 為一 (n-1)\times(n-1) 階矩陣,各元定義為

d_{ij}=\begin{vmatrix}    a_{ij}&a_{in}\\    a_{nj}&a_{nn}    \end{vmatrix},~~1\le i,j\le n-1

矩陣 DA 的行列式具有下列關係:

\det D=(a_{nn})^{n-2}\det A

Chiò 行列式計算法即由上式給出,

\det A=\displaystyle\frac{1}{(a_{nn})^{n-2}}\det D

 
考慮下面的四階行列式:

\det A=\left|\!\!\begin{array}{rrcr}    2&-5&4&1\\    1&0&3&-2\\    -4&5&3&0\\    -2&1&1&2    \end{array}\!\!\right|

設軸元 a_{44}=2,將此四階行列式化簡為一個三階行列式,

\begin{aligned}  \det A&=\displaystyle\frac{1}{2^{4-2}}\begin{vmatrix}  \left|\!\!\begin{array}{rc}  2&1\\  -2&2  \end{array}\!\!\right|&\left|\!\!\begin{array}{rc}  -5&1\\  1&2  \end{array}\!\!\right|&  \left|\!\!\begin{array}{cc}  4&1\\  1&2\end{array}\!\!\right|\\  ~&~&~\\  \left|\!\!\begin{array}{rr}  1&-2  \\-2&2\end{array}\!\!\right|  &\left|\!\!\begin{array}{cr}  0&-2\\1  &2  \end{array}\!\!\right|  &\left|\!\!\begin{array}{cr}  3&-2\\  1&2\end{array}\!\!\right|\\  ~&~&~\\  \left|\!\!\begin{array}{rc}  -4&0\\  -2&2  \end{array}\!\!\right|  &\left|\!\!\begin{array}{cc}  5&0\\  1&2\end{array}\!\!\right|  &\left|\!\!\begin{array}{cc}  3&0\\  1&2  \end{array}\!\!\right|\end{vmatrix}=\frac{1}{4}\left|\!\!\begin{array}{rrc}    6&-11&7\\    -2&2&8\\    -8&10&6    \end{array}\!\!\right|\end{aligned}

接著令軸元為 a_{33}=6,對三階行列式化簡,可得

\begin{aligned}  \det A&=\displaystyle\frac{1}{4}\cdot\frac{1}{6^{3-2}}\begin{vmatrix}    \left|\!\!\begin{array}{rc}6&7\\-8&6\end{array}\!\!\right|&\left|\!\!\begin{array}{rc}-11&7\\10&6\end{array}\!\!\right|\\    ~&~\\    \begin{vmatrix}-2&8\\-8&6\end{vmatrix}&\left|\!\!\begin{array}{rc}2&8\\10&6\end{array}\!\!\right|    \end{vmatrix}=\frac{1}{24}\left|\!\!\begin{array}{cr}    92&-136\\    52&-68    \end{array}\!\!\right|=34\end{aligned}

 
Chiò 演算法的證明過程只需運用幾個行列式基本性質,比較奇特的是起頭的第一步,將矩陣 A 的前 n-1 列的每個元都乘以 a_{nn},稱此 n\times n 階矩陣為 B

B=\begin{bmatrix}    a_{11}a_{nn}&a_{12}a_{nn}&\cdots&a_{1n}a_{nn}\\    \vdots&\vdots&\ddots&\vdots\\    a_{n-1,1}a_{nn}&a_{n-1,2}a_{nn}&\cdots&a_{n-1,n}a_{nn}\\    a_{n1}&a_{n2}&\cdots&a_{nn}    \end{bmatrix}

利用行列式對於任一列為線性函數此性質,就有

\det B=(a_{nn})^{n-1}\det A

下一個步驟是執行基本列運算,將矩陣 B 的第 i 列取代為第 i 列減去 a_{in} 與第 n 列的乘積,我們對 i=1,2,\ldots,n-1 都做相同的列運算,得到的矩陣稱為 C,如下:

C=\begin{bmatrix}    a_{11}a_{nn}-a_{1n}a_{n1}&\cdots&a_{1,n-1}a_{nn}-a_{1n}a_{n,n-1}&0\\    \vdots&\ddots&\vdots&\vdots\\    a_{n-1,1}a_{nn}-a_{n-1,n}a_{n1}&\cdots&a_{n-1,n}a_{nn}-a_{n-1,n}a_{n,n-1}&0\\    a_{n1}&\cdots&a_{n,n-1}&a_{nn}    \end{bmatrix}

因為基本列運算的取代運算不改變行列式值,故 \det C=\det B。將 C 寫成下面的分塊矩陣形式:

C=\begin{bmatrix}    D&\mathbf{0}\\    \mathbf{c}^T&a_{nn}    \end{bmatrix}

其中 \mathbf{0}(n-1) 維零向量,\mathbf{c}^T=\begin{bmatrix}    a_{n1}&\cdots&a_{n,n-1}    \end{bmatrix}(n-1) 維列向量。上式中,(n-1)\times(n-1) 階分塊 D 正是我們想要得到的降階矩陣,對 C 的第 n 行以餘因子展開計算行列式,推知 \det C=a_{nn}\det D。綜合以上結果,證得

\displaystyle  \det A=\displaystyle\frac{1}{(a_{nn})^{n-1}}\det B=\frac{1}{(a_{nn})^{n-1}}\det C=\frac{1}{(a_{nn})^{n-2}}\det D

 
Chiò 演算法還有一個問題要解決:萬一 a_{nn}=0 該怎麼辦?事實上,矩陣裡的任何非零元 a_{pq} 都可以當作軸元,我們僅需將第 p 列和第 n 列交換,再將第 q 行和第 n 行交換即可,每交換一次列或行就改變行列式的正負號。以上面的行列式為例,將第三行與第四行交換,

\left|\!\!\begin{array}{rrcr}    2&-5&4&1\\    1&0&3&-2\\    -4&5&3&0\\    -2&1&1&2    \end{array}\!\!\right|=-\left|\!\!\begin{array}{rrrc}    2&-5&1&4\\    1&0&-2&3\\    -4&5&0&3\\    -2&1&2&1    \end{array}\!\!\right|

軸元為 a_{44}=1,上面的行列式等於

-\begin{vmatrix}    \left|\!\!\begin{array}{rc}2&4\\-2&1\end{array}\!\!\right|&\left|\!\!\begin{array}{rc}-5&4\\1&1\end{array}\!\!\right|&\begin{vmatrix}1&4\\2&1\end{vmatrix}\\    ~&~&~\\    \left|\!\!\begin{array}{rc}1&3\\-2&1\end{array}\!\!\right|&\begin{vmatrix}0&3\\1&1\end{vmatrix}&\left|\!\!\begin{array}{rc}-2&3\\2&1\end{array}\!\!\right|\\    ~&~&~\\    \begin{vmatrix}-4&3\\-2&1\end{vmatrix}&\begin{vmatrix}5&3\\1&1\end{vmatrix}&\begin{vmatrix}0&3\\2&1\end{vmatrix}    \end{vmatrix}=-\left|\!\!\begin{array}{rrr}    10&-9&-7\\    7&-3&-8\\    2&2&-6    \end{array}\!\!\right|

 
最後我們討論 Chiò 法使用的計算量,對於 n 階行列式,此法逐次求得一個 (n-1) 階行列式,(n-2) 階行列式,直到二階行列式為止。考慮由 k 階行列式計算 (k-1) 階行列式此步驟,總共必須計算 (k-1)^2 個二階行列式,每個二階行列式又使用 2 次乘法運算,所以乘法運算總量為

\displaystyle  2((n-1)^2+(n-2)^2+\cdots+2^2+1)=2\displaystyle\frac{1}{6}(n-1)n(2n-1)\approx\frac{2}{3}n^3

這比高斯消去法使用的乘法運算量 n^3/3 稍多。Chiò 演算法不像餘因子展開需要使用冗長的簿記抄寫,並且很容易熟悉駕馭,手算時較不容易出錯。但 Chiò 演算法產生的降階行列式可能包含一些數值較大的元,這和高斯消去法碰到的問題相同,縱使我們選擇不同的軸元也不能保證得到包含數值小的降階矩陣。

 
參考來源:
[1] L.E. Fuller and J.D. Logan, On the Evaluation of Determinants by Chiò’s Method, College Mathematics Journal, vol.6, pp 8-10, 1975.

This entry was posted in 線性代數專欄, 行列式 and tagged , , , . Bookmark the permalink.

3 則回應給 Chiò 演算法──另類行列式計算法

  1. 蒋sir 說:

    但是,其实上这个方法并没有给问题带来化简的作用。就上面那个4X4的矩阵而言,Lapalace展开需要计算12个二阶行列式,而这个算法也一样要计算这么多。Lapalace只设计加减乘,而这个方法还具有除与乘方。这或许是他失传的一个很重要的原因吧。

  2. 蔡金龍 說:

    很有用 感謝

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s