簡約列梯形式的唯一性

本文的閱讀等級:中級

高斯─約當法 (Gauss-Jordan method) 是線性代數中最常使用的演算法之一 (見“高斯─約當法”),它的功用是將給定矩陣 A 化為同階的簡約列梯形式 (reduced row echelon form),記為 \hbox{rref}(A)。透過簡約列梯形式,不但可以解出線性方程組還能回答許多有關矩陣的基本問題,如矩陣秩、列空間基底、行空間基底以及零空間基底 (見“矩陣的四個基本子空間基底算法”)。從高斯—約當法的演算過程,我們憑直覺推斷 A 的簡約列梯形式是唯一的 (否則不會將之命名為 \hbox{rref}(A)),於是理所當然地將它視為事實。本文介紹一個運用排列矩陣與分塊矩陣的代數證明方法,透徹瞭解這整個論證過程對提昇邏輯推理能力有很大的幫助。

 
在不失一般性的原則下,我們只考慮 n\times n 階矩陣 A。倘若 A 不為方陣,可以直接在 A 的底下或右側加入零列或零行,例如,給出矩陣

\begin{bmatrix}  1&2&3\\  4&5&6  \end{bmatrix}

增加一零列於最末列之下,

\begin{bmatrix}  1&2&3\\  4&5&6\\  0&0&0  \end{bmatrix}

十分明顯,增添零列或零行使矩陣方陣化的行為並不會影響原矩陣的結構。

 
開始證明之前,我們先複習簡約列梯形式的性質。簡約列梯形式由下面四個條件所定義,前兩個條件描述梯形,後兩個條件使其最簡:

  1. 零列置於矩陣的最底部;
  2. 每列軸元 (pivot) 的位置都位於其上方各列軸元的右側;
  3. 軸元為 1
  4. 軸元其上方和下方的元皆為零。

底下的 5 階方陣 R 具有簡約列梯形式:

R=\begin{bmatrix}  1&3&0&0&4\\  0&0&1&0&5\\  0&0&0&1&6\\  0&0&0&0&0\\  0&0&0&0&0  \end{bmatrix}

 
簡約列梯形式的性質集中在軸元所處的位置,我們先花點時間研究一下。看這個問題:如何移動 R 的軸行 (pivot column,包含軸元的行) 至方陣左側?很容易辦到,你只需要在 R 右乘一個適當的排列矩陣即可。以上例說明,R 的軸行指標為 134,可令行指標按 (1,3,4,2,5) 排序,對應的排列矩陣為

\begin{aligned} P&=\begin{bmatrix}  \mathbf{e}_1&\mathbf{e}_3&\mathbf{e}_4&\mathbf{e}_2&\mathbf{e}_5  \end{bmatrix}=\begin{bmatrix}  1&0&0&0&0\\  0&0&0&1&0\\  0&1&0&0&0\\  0&0&1&0&0\\  0&0&0&0&1  \end{bmatrix}\end{aligned}

利用以行作為運算單位的矩陣乘法能幫助我們理解 RP 的作用不過就是重新排列 R 的行向量,如下:

\begin{aligned} RP&=\begin{bmatrix}  1&3&0&0&4\\  0&0&1&0&5\\  0&0&0&1&6\\  0&0&0&0&0\\  0&0&0&0&0  \end{bmatrix}\begin{bmatrix}  \mathbf{e}_1&\mathbf{e}_3&\mathbf{e}_4&\mathbf{e}_2&\mathbf{e}_5  \end{bmatrix}=\begin{bmatrix}  1&0&0&3&4\\  0&1&0&0&5\\  0&0&1&0&6\\  0&0&0&0&0\\  0&0&0&0&0  \end{bmatrix}\end{aligned}

方陣 R 的三個軸元集中於 RP 主對角線的左上方,將 RP 以分塊矩陣表示為

RP=\begin{bmatrix}  I_3&J\\  0&0  \end{bmatrix}

其中 J=\begin{bmatrix}  3&4\\  0&5\\  0&6  \end{bmatrix} ,它包含所有非軸行訊息。

 
從列向量角度也可以解讀排列矩陣 P,將 P 以列向量表示:

\begin{aligned} P&=\begin{bmatrix}  1&0&0&0&0\\  0&0&0&1&0\\  0&1&0&0&0\\  0&0&1&0&0\\  0&0&0&0&1  \end{bmatrix}=\begin{bmatrix}  ~&\mathbf{e}_1^T&~\\  ~&\mathbf{e}_4^T&~\\  ~&\mathbf{e}_2^T&~\\  ~&\mathbf{e}_3^T&~\\  ~&\mathbf{e}_5^T&~  \end{bmatrix}\end{aligned}

R 左乘 P 的功用是將 R 的列向量按 (1,4,2,3,5) 排序,而非 (1,3,4,2,5)。這點很容易造成混淆,你務必留意所執行的運算究竟是按行排列 (右乘 P) 或列排列 (左乘 P),下圖可以讓我們清楚瞭解排列矩陣 P 和轉置矩陣 P^T 所對應的行排序和列排序。

Permutation matrices

再看看 R 左乘 P 會有什麼結果,利用以列作為運算單位的矩陣乘法可得

\begin{aligned} PR&=\begin{bmatrix}  ~&\mathbf{e}_1^T&~\\  ~&\mathbf{e}_4^T&~\\  ~&\mathbf{e}_2^T&~\\  ~&\mathbf{e}_3^T&~\\  ~&\mathbf{e}_5^T&~  \end{bmatrix}\begin{bmatrix}  1&3&0&0&4\\  0&0&1&0&5\\  0&0&0&1&6\\  0&0&0&0&0\\  0&0&0&0&0  \end{bmatrix}=\begin{bmatrix}  1&3&0&0&4\\  0&0&0&0&0\\  0&0&1&0&5\\  0&0&0&1&6\\  0&0&0&0&0  \end{bmatrix}\end{aligned}

R 左乘 P 的效果是把 R 的軸元置於主對角線上,這不是偶然,而是必然。設 T=PR,排列矩陣是正交矩陣,P^T=P^{-1},所以

\begin{aligned} T&=PR(PP^{-1})=P(RP)P^T\end{aligned}

也就有

RP=P^TTP

上式指出 TRP 的排列變換,亦即列行指標重新排序的結果。由於 RP 的軸元都在左上分塊的主對角線,推論得知這些軸元也都位於 T 的主對角線。參考上圖,P 的行指標排序和 P^T 的列指標排序都為 (1,3,4,2,5),所以 P^TTP 的作用即是將指標按此順序排列,計算驗證

\begin{aligned} P^TTP&=\begin{bmatrix}  1&0&0&0&0\\  0&0&1&0&0\\  0&0&0&1&0\\  0&1&0&0&0\\  0&0&0&0&1  \end{bmatrix}\begin{bmatrix}  1&3&0&0&4\\  0&0&0&0&0\\  0&0&1&0&5\\  0&0&0&1&6\\  0&0&0&0&0  \end{bmatrix}\begin{bmatrix}  1&0&0&0&0\\  0&0&0&1&0\\  0&1&0&0&0\\  0&0&1&0&0\\  0&0&0&0&1  \end{bmatrix}\\ &=\begin{bmatrix}  1&0&0&3&4\\  0&1&0&0&5\\  0&0&1&0&6\\  0&0&0&0&0\\  0&0&0&0&0  \end{bmatrix}=RP\end{aligned}

 
說了大半天,現在正式開始證明。假設 A 有兩個不同的簡約列梯形式 R_1R_2A\sim R_1A\sim R_2,符號 \sim 代表列等價,淺白的說法是「經過一序列的基本列運算」。等價關係有對稱性和傳遞性,因此 R_1\sim R_2。每一個基本矩陣對應一次基本列運算 (見“特殊矩陣 (10):基本矩陣”),根據列等價性質必定存在可逆矩陣 E 為一序列基本矩陣乘積使得

ER_1=R_2

這個式子將留待稍後使用。

 
默想簡約列梯形式的四個定義條件,我們嘗試運用「矩陣解剖學」來證明 R_1=R_2。簡約列梯形式其軸元的總數就是矩陣秩。設 \mathrm{rank}A=r,基本列運算不改變秩,故 \mathrm{rank}R_1=\mathrm{rank}R_2=r。簡約列梯形式的非零列即為軸列,透露的有用訊息不多,因此從軸行下手。擬定的證明計畫是先推論 R_1R_2 有相同的軸行,下一步再證明 R_1R_2 的非軸行也相同。

 
以下 k 表示 12R_k 的軸元不一定位於主對角線,於是我們重排 R_k 的列,使其軸元置於上三角矩陣 T_k 的主對角線上。使用前述結果,T_k=P_kR_kR_k\sim T_k,又因為交換列不影響軸行的位置,T_k 的軸行也對應 R_k 的軸行。既然知道 R_kT_k 有相同的軸行指標,若能證明 T_1T_2 也有相同的軸行指標,等於宣告 R_1R_2 有相同的軸行指標。要怎麼做呢?想法是以相同的形式表達 T_1T_2。運用關係式

\begin{aligned} T_k&=P_k(R_kP_k)P_k^T=P_k\begin{bmatrix}  I_r&J_k\\  0&0  \end{bmatrix}P_k^T\end{aligned}

計算 T_k 平方並化簡:

\begin{aligned} T_k^2&=P_k\begin{bmatrix}  I_r&J_k\\  0&0  \end{bmatrix}P_k^TP_k\begin{bmatrix}  I_r&J_k\\  0&0  \end{bmatrix}P_k^T\\ &=P_k\begin{bmatrix}  I_r&J_k\\  0&0  \end{bmatrix}P_k^T=T_k\end{aligned}

運算結果指出 T_k 是冪等矩陣 (idempotent matrix)。因為 R_1\sim R_2,且 R_1\sim T_1R_2\sim T_2,可知 T_1\sim T_2,一定存在可逆矩陣 F 使得

T_2=FT_1

T_1=T_1T_1 代入上式,就有

\begin{aligned} T_2&=FT_1T_1=T_2T_1\end{aligned}

反過來照樣做一次,得到

\begin{aligned} T_1&=F^{-1}T_2=F^{-1}T_2T_2=T_1T_2\end{aligned}

因為 T_k 是上三角矩陣,對於 i>j(T_k)_{ij}=0(T_k)_{ij} 表示 T_k(i,j) 元。計算 T_1T_2 的主對角元:

\begin{aligned} (T_1T_2)_{ii}&=\displaystyle\sum_{p=1}^n(T_1)_{ip}(T_2)_{pi}=(T_1)_{ii}(T_2)_{ii}\\ &=(T_2)_{ii}(T_1)_{ii}=(T_2T_1)_{ii}\end{aligned}

T_1T_2T_2T_1 有相同的的主對角元,故 T_1T_2 也有相同的主對角元。又由於軸元都集中在 T_k 的主對角線上,推論 T_1T_2 有相同的軸行指標,於是證出 R_1R_2 也有相同的軸行指標。

 
既然 R_1R_2 的軸行指標相同,便有排列矩陣 P 同時滿足

R_1P=\begin{bmatrix}  I_r&J_1\\  0&0  \end{bmatrix},~R_2P=\begin{bmatrix}  I_r&J_2\\  0&0  \end{bmatrix}

最後的工作是證明 R_1R_2 的非軸行相同,亦即 J_1=J_2。利用前面得到的關係式 ER_1=R_2,等號兩邊右乘 P,就有 ER_1P=R_2P,再將 E 以分塊矩陣表示,如下:

\begin{bmatrix}  E_{11}&E_{12}\\  E_{21}&E_{22}  \end{bmatrix}\begin{bmatrix}  I_r&J_1\\  0&0  \end{bmatrix}=\begin{bmatrix}  I_r&J_2\\  0&0  \end{bmatrix}

乘開上式並比對等號兩端發現 E_{11}=I_rE_{11}J_1=J_2,合併二式得到 J_1=J_2,證得簡約列梯形式確實是唯一的。

廣告
本篇發表於 線性代數專欄, 向量空間 並標籤為 , , , , , , , , 。將永久鏈結加入書籤。

2 Responses to 簡約列梯形式的唯一性

  1. Yufeng 說道:

    周老師,您好。為什麼“由於 RP 的軸元都在左上分塊的主對角線,推論得知這些軸元也都位於 T 的主對角線。”?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s