利用行列式計算矩陣秩

本文的閱讀等級:初級

知識的創新需要不斷地擺脫教條與偏見。研習教科書可以讓我們累積知識,但照單全收前人遺留的資產反而可能阻礙知識的創新,所以康德 (Immanuel Kant) 強調:「我不是敎哲學,而是敎人們哲學地思考。」本文就以每一位線性代數學者必須掌握的基本技能──計算矩陣的秩──為例說明,縱使是公認的標準作法也仍存在改進的可能。

 
A 為一個 m\times n 階矩陣。矩陣秩或簡稱秩,記為 \mathrm{rank}A,是矩陣的一個重要度量值。多數線性代數課本建議以高斯消去法計算矩陣秩,即運用基本列運算 (elementary row operation) 化簡 A 直到得出梯形矩陣 (echelon form) 為止。梯形矩陣的非零列稱為軸列 (pivot row),軸列的集合組成 A 的列空間的基底,矩陣秩即為軸列數,也就是 A 的列空間的維數。

 
下例說明高斯消去法計算矩陣秩的過程,符號 \sim 代表基本列運算過程,或者說 \sim 兩側的矩陣是列等價的 (row equivalent)。消去法的第一個任務是以基本列運算消去第一列軸元 (pivot) 3 底下的元,即 25。最直接的算法是將第二列以該列減去第一列通乘 \frac{2}{3} 的結果取代,同樣地,將第三列取代為第三列減去第一列通乘 \frac{5}{3} 的結果,如下:

\left[\!\!\begin{array}{ccrr}  3&4&-5&6\\  2&2&8&7\\  5&5&-3&-1  \end{array}\!\!\right]\sim\left[\!\!\begin{array}{rrrr}  3&4&-5&6\\[0.3em]  0&-\frac{2}{3}&\frac{34}{3}&3\\[0.3em]  0&-\frac{5}{3}&\frac{16}{3}&-11  \end{array}\!\!\right]

縱使最初給定的是一個包含整數的矩陣,在一般情況下,列取代運算常會產生非整數元。為了降低分數運算出錯的機率,你可以將新誕生的第二列和第三列通乘軸元 3 以消除分母,之後再繼續下一級的消去步驟:將第三列取代為第三列減去第二列通乘 \frac{5}{2},如下:

\left[\!\!\begin{array}{crrr}  3&4&-5&6\\  0&-2&34&9\\  0&-5&16&-33  \end{array}\!\!\right]\sim\left[\!\!\begin{array}{crrr}  3&4&-5&6\\  0&-2&34&9\\[0.3em]  0&0&-69&-\frac{111}{2}  \end{array}\!\!\right]

演算程序於得到梯形矩陣後終止,得知 A 有3個軸元 (即 3, -2, -69),因此 \mathrm{rank}A=3

 
如果你跟我一樣患有算術恐懼症,上述算法的缺點是牽涉了分數運算。有甚麼辦法能避開分數運算呢?回頭看看到底基本列運算的取代運算是如何進行的。考慮 m\times n 階矩陣

A=\begin{bmatrix}  a_{11}&a_{12}&\cdots&a_{1n}\\  a_{21}&a_{22}&\cdots&a_{2n}\\  \vdots&\vdots&\ddots&\vdots\\  a_{m1}&a_{m2}&\cdots&a_{mn}  \end{bmatrix}

由於矩陣列可隨意排列,在不失一般性原則下,假設軸元 a_{11}\neq 0。要消去 a_{11} 底下的每個元 a_{i1}2\le i\le m,我們對列 i 執行取代運算,以符號表示為

\mathrm{row}_i\leftarrow\mathrm{row}_i-\displaystyle\frac{a_{i1}}{a_{11}}\times\mathrm{row}_1

既然我們厭惡分數運算,可將列 i 通乘 a_{11},也就是上式箭號右邊乘以 a_{11},就有

\mathrm{row}_i\leftarrow a_{11}\times\mathrm{row}_i-a_{i1}\times\mathrm{row}_1

請注意,我們實際執行了二次基本列運算,對於 2\le i\le m,先將列 i 乘以 a_{11},再從列 i 減去 a_{i1} 和第一列的乘積,過程如下:

\begin{aligned} A&\sim\begin{bmatrix}  a_{11}&a_{12}&\cdots&a_{1n}\\  a_{11}a_{21}&a_{11}a_{22}&\cdots&a_{11}a_{2n}\\  \vdots&\vdots&\ddots&\vdots\\  a_{11}a_{m1}&a_{11}a_{m2}&\cdots&a_{11}a_{mn}  \end{bmatrix}\\  &\sim\begin{bmatrix}  a_{11}&a_{12}&\cdots&a_{1n}\\  0&a_{11}a_{22}-a_{21}a_{12}&\cdots&a_{11}a_{2n}-a_{21}a_{1n}\\  \vdots&\vdots&\ddots&\vdots\\  0&a_{11}a_{m2}-a_{m1}a_{12}&\cdots&a_{11}a_{mn}-a_{m1}a_{1n}  \end{bmatrix}=B\end{aligned}

B=[b_{ij}] 為基本列運算化簡得到的列等價矩陣。不難觀察出 B 的右下 (m-1)\times(n-1) 階子陣的每個元都是一個二階行列式:

\displaystyle  B=\begin{bmatrix}  a_{11}&a_{12}&\cdots&a_{1n}\\  0&\begin{vmatrix} a_{11}&a_{12}\\ a_{21}&a_{22} \end{vmatrix}&\cdots&\begin{vmatrix} a_{11}&a_{1n}\\ a_{21}&a_{2n} \end{vmatrix}\\  \vdots&\vdots&\ddots&\vdots\\  0&\begin{vmatrix} a_{11}&a_{12}\\ a_{m1}&a_{m2} \end{vmatrix}&\cdots&\begin{vmatrix} a_{11}&a_{1n}\\ a_{m1}&a_{mn} \end{vmatrix}  \end{bmatrix}

因此,對於 2\le i\le m2\le j\le n

b_{ij}=\begin{vmatrix}  a_{11}&a_{1j}\\  a_{i1}&a_{ij}  \end{vmatrix}=a_{11}a_{ij}-a_{i1}a_{1j}

此即為以二階行列式實現高斯消去法的演算式。

 
下面我用之前的例子展示利用行列式計算矩陣秩的完整過程。先確定軸元 a_{11}=3\neq 0,計算右下 2\times 3 階子陣:

\begin{aligned} \left[\!\!\begin{array}{ccrr}  3&4&-5&6\\  2&2&8&7\\  5&5&-3&-1  \end{array}\!\!\right]&\sim\begin{bmatrix}  3&4&-5&6\\  0&\begin{vmatrix}  3&4\\2&2  \end{vmatrix}&\left|\!\!\begin{array}{cr}  3&-5\\2&8  \end{array}\!\!\right|&\begin{vmatrix}  3&6\\2&7  \end{vmatrix}\\[0.8em]  0&\begin{vmatrix}  3&4\\5&5  \end{vmatrix}&\begin{vmatrix}  3&-5\\5&-3  \end{vmatrix}&\left|\!\!\begin{array}{cr}  3&6\\5&-1  \end{array}\!\!\right|  \end{bmatrix}=\left[\!\!\begin{array}{crrr}  3&4&-5&6\\  0&-2&34&9\\  0&-5&16&-33  \end{array}\!\!\right]\end{aligned}

下一級的化簡工作只需要針對右下 2\times 3 階子陣進行,選定軸元 -2\neq 0,再計算 1\times 2 階子陣,如下:

\left[\!\!\begin{array}{crrr}  3&4&-5&6\\  0&-2&34&9\\  0&-5&16&-33  \end{array}\!\!\right]\sim\begin{bmatrix}  3&4&-5&6\\  0&-2&34&9\\  0&0&\begin{vmatrix}  -2&34\\-5&16  \end{vmatrix}&\left|\!\!\begin{array}{rr}  -2&9\\-5&-33  \end{array}\!\!\right|  \end{bmatrix}=\left[\!\!\begin{array}{crrr}  3&4&-5&6\\  0&-2&34&9\\  0&0&138&111  \end{array}\!\!\right]

 
最後我們比較新演算法和傳統演算法所需的計算量。在新演算法中,每一個元對應一個二階行列式,因此需要兩個乘法與一個加法,傳統的演算法則需要一個乘法與一個加法。就 n\times n 階矩陣而言,傳統演算法使用 \frac{n^3}{3} 個乘法運算,而新演算法則使用 \frac{2n^3}{3} 個乘法運算。付出多一倍的乘法運算量,我們得到了什麼?純粹從手算的角度來看,這有兩個好處:其一是避免分數運算 (至少對我個人而言,這是一件好事),只要給定的矩陣包含整數元,消去法產生的列等價矩陣絕不會出現分數;其二是每一個元所對應的二階行列式排列整齊,計算抄寫時較不容易出錯。

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

12 Responses to 利用行列式計算矩陣秩

  1. aocwind 說道:

    推獨立思考的重要性!!

  2. ccjou 說道:

    說起獨立思考,我想起台積電董事長張忠謀引述《邱吉爾傳》裡的話:沒有獨立思考,就像留著別人屁股印的坐墊。

  3. levinc417 說道:

    剛好逛到這篇…突然有個感覺…
    如果考試(在台灣)這麼操作,也許拿不到分數…即使答案正確 orz

  4. levinc417 說道:

    嗯~~也許是"看不懂", 也許是"我沒教", 或是"助教改的",…etc…可能會給個"問號" XD

  5. ya 說道:

    分數運算讓我超頭痛
    這方法快好多
    學校都沒教過這麼好用的算法

    • ccjou 說道:

      可能編書的作者們認為這個算法只不過是雕蟲小技。

      另外,如果要應用此法消去上三角位置的元 (i,j)i<j,會發生問題。大家看出來問題所在吧?

  6. 老羅 說道:

    請問老師所謂,"應用此法消去上三角位置的元",是指
    \begin{bmatrix} -3 & 0 & 0 & \frac{1227}{46}\\  46 & 46 & 0 & 13\\  5 & 5 & -3 & -1 \end{bmatrix}
    化成這形式嗎?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s