高斯---約當法（Gauss-Jordan method）是線性代數中最常使用的演算法之一，它的功用是將給定矩陣化約至最簡列梯形陣式（reduced row echelon form）。透過最簡列梯形矩陣，不但可以解出線性方程組還能回答許多有關矩陣的基本問題，如矩陣秩、列空間基底、行空間基底以及零空間基底。從高斯---約當法的演算過程，我們憑直覺推斷 $$A$$ 的最簡列梯形矩陣是唯一的，於是理所當然地將它視為事實。本文介紹一個運用排列矩陣和分塊矩陣的代數證明方法，透徹瞭解這整個論證過程對提昇邏輯推理能力有很大的幫助。
在不失一般性的原則下，我們只考慮 $$n$$ 階方陣 $$A$$。倘若 $$A$$ 不為方陣，可以直接在 $$A$$ 的底下或右側加入零列或零行，例如，給出矩陣
$$\begin{bmatrix}
1&3&2\\
2&6&5
\end{bmatrix}$$
增加一零列於最末列之下，
$$\begin{bmatrix}
1&3&2\\
2&6&5\\
0&0&0
\end{bmatrix}$$
十分明顯，增添零列或零行使矩陣方陣化的行為並不會影響原矩陣的結構。
開始證明之前，我們先複習最簡列梯形矩陣的性質。最簡列梯形矩陣由下面四個條件所定義，前二個條件描述梯形，後二個條件使其最簡：
■ 零列置於矩陣的最底部
■ 每列軸元的位置都位於其上方各列軸元的右側
■ 軸元為 $$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$$ 的軸行（包含軸元的行）至方陣左側？很容易辦到，只需要在 $$R$$ 右乘適當的排列矩陣即可。以上例說明，$$R$$ 的軸行指標為 $$1$$，$$3$$，$$4$$，可令行指標按 $$(1,3,4,2,5)$$ 排序，對應的排列矩陣為
$$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}$$
利用以行作為運算單位的矩陣乘法能幫助我們理解 $$RP$$ 的作用不過就是重新排列 $$R$$ 的行向量，如下：
$$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}$$
方陣 $$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$$ 以列向量表示：
$$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}$$
在 $$R$$ 左乘 $$P$$ 的功用是將 $$R$$ 的列向量按 $$(1,4,2,3,5)$$ 排序，而非 $$(1,3,4,2,5)$$。這點很容易造成混淆，讀者務必留意所執行的運算究竟是按行排列（右乘 $$P$$）或列排列（左乘 $$P$$），下圖可以讓我們清楚瞭解排列矩陣 $$P$$ 和轉置矩陣 $$P^T$$ 所對應的行排序和列排序。
再看看 $$R$$ 左乘 $$P$$ 會有什麼結果，利用以列作為運算單位的矩陣乘法可得
$$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}$$
在 $$R$$ 左乘 $$P$$ 的效果是把 $$R$$ 的軸元置於主對角線上，這不是偶然，而是必然。設 $$T=PR$$，排列矩陣是正交矩陣，$$P^T=P^{-1}$$，所以
$$T=PR(PP^{-1})=P(RP)P^T$$
也就有
$$RP=P^TTP$$
上式指出 $$T$$ 為 $$RP$$ 的排列變換，亦即列行指標重新排序的結果。由於 $$RP$$ 的軸元都在左上分塊的主對角線，推論得知這些軸元也都位於 $$T$$ 的主對角線。參考上圖，$$P$$ 的行指標排序和 $$P^T$$ 的列指標排序都為 $$(1,3,4,2,5)$$，所以 $$P^TTP$$ 的作用即是將指標按此順序排列，計算驗證
$$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$$
說了大半天，現在正式開始證明。假設 $$A$$ 有二個不同的最簡列梯形矩陣 $$R_1$$ 和 $$R_2$$，$$A\sim R_1$$，$$A\sim R_2$$，符號 $$\sim$$ 代表列等價，淺白的說法是“經過一序列的基本列運算”。等價關係有對稱性和傳遞性，因此 $$R_1\sim R_2$$。每一個基本矩陣對應一次基本列運算（參閱“特殊矩陣 (十)：基本矩陣”），根據列等價性質必定存在可逆矩陣 $$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$$。運用關係式
$$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$$
計算 $$T_k$$ 平方並化簡：
$$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$$
運算結果指出 $$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$$ 代入上式，就有
$$T_2=FT_1T_1=T_2T_1$$
反過來照樣做一次，得到
$$T_1=F^{-1}T_2=F^{-1}T_2T_2=T_1T_2$$
因為 $$T_k$$ 是上三角形矩陣，對於 $$i>j$$，$$(T_k)_{ij}=0$$，$$(T_k)_{ij}$$ 表示 $$T_k$$ 的 $$(i,j)$$ 元。計算 $$T_1T_2$$ 的主對角元：
$$(T_1T_2)_{ii}=\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}$$
$$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$$，證得最簡列梯形矩陣確實是唯一的。
沒有留言:
張貼留言