簡約列梯形式的唯一性

本文的閱讀等級：中級

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

在不失一般性的原則下，我們只考慮 $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}$ 。

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

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

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

底下的 $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$ 的軸行指標為 $1$ ， $3$ ， $4$ ，令行指標按 $(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$ 。

上式指出 $T$ 為 $RP$ 的排列變換，亦即列行指標重新排序的結果。由於 $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_1$ 和 $R_2$ ，記為 $A\sim R_1$ 和 $A\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_1$ 和 $R_2$ 有相同的軸行，下一步再證明 $R_1$ 和 $R_2$ 的非軸行也相同。

以下 $k$ 表示 $1$ 和 $2$ 。 $R_k$ 的軸元不一定位於主對角線，於是我們重排 $R_k$ 的列，使其軸元置於上三角矩陣 $T_k$ 的主對角線上。使用前述結果， $T_k=P_kR_k$ ， $R_k\sim T_k$ ，又因為交換列不影響軸行的位置， $T_k$ 的軸行也對應 $R_k$ 的軸行。既然知道 $R_k$ 和 $T_k$ 有相同的軸行指標，若能證明 $T_1$ 和 $T_2$ 也有相同的軸行指標，等於宣告 $R_1$ 和 $R_2$ 有相同的軸行指標。要怎麼做呢？想法是以相同的形式表達 $T_1$ 和 $T_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_1$ ， $R_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_2$ 和 $T_2T_1$ 有相同的的主對角元，推知 $T_1$ 和 $T_2$ 也有相同的主對角元。又由於軸元都集中在 $T_k$ 的主對角線上，推論 $T_1$ 和 $T_2$ 有相同的軸行指標，於是證出 $R_1$ 和 $R_2$ 也有相同的軸行指標。

既然 $R_1$ 和 $R_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_1$ 和 $R_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_r$ ， $E_{11}J_1=J_2$ ，合併二式得到 $J_1=J_2$ ，證得簡約列梯形式確實是唯一的。

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

Yufeng says:

08/08/2016 at 3:29 pm

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

- ccjou says:
  
  08/09/2016 at 11:45 am
  
  這段陳述後面有一個例子說明。主對角元的列行指標相同 $(i,i)$ ，經過重新排序後其列行指標仍相同但替換為 $(j,j)$ 。請參閱下文
  https://ccjou.wordpress.com/2009/08/04/%E7%9F%A9%E9%99%A3%E8%A6%96%E8%A6%BA%E5%8C%96/
  
curc says:

12/13/2021 at 11:15 pm

T_1T_2 和 T_2T_1 有相同的的主對角元，故 T_1 和 T_2 也有相同的主對角元。这里是否有些多余？T_1T_2=T_1就已经可以推出对角元相同了？

	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨
	jeff85898 on 利用分塊矩陣證明 det(AB)=(det A)(det…