線性代數/高斯-約旦消元

高斯消元法與回代法可以用來解線性方程組，但這並不是唯一可行的方法。這裡介紹了高斯方法的一個擴充套件，它具有一些優勢。

示例 1.1

為了解決

${\begin{array}{*{3}{rc}r}x&+&y&-&2z&=&-2\\&&y&+&3z&=&7\\x&&&-&z&=&-1\end{array}}$

我們可以像往常一樣先進行行階梯形變換。

${\xrightarrow[{}]{-\rho _{1}+\rho _{3}}}\left({\begin{array}{ccc|c}1&1&-2&-2\\0&1&3&7\\0&-1&1&1\end{array}}\right){\xrightarrow[{}]{\rho _{2}+\rho _{3}}}\left({\begin{array}{ccc|c}1&1&-2&-2\\0&1&3&7\\0&0&4&8\end{array}}\right)$

我們可以透過將主元轉換為1來進行第二階段

${\xrightarrow[{}]{(1/4)\rho _{3}}}\left({\begin{array}{ccc|c}1&1&-2&-2\\0&1&3&7\\0&0&1&2\end{array}}\right)$

然後進入第三階段，利用主元透過向上回代消去每列中的所有其他元素。

${\xrightarrow[{2\rho _{3}+\rho _{1}}]{-3\rho _{3}+\rho _{2}}}\left({\begin{array}{ccc|c}1&1&0&2\\0&1&0&1\\0&0&1&2\end{array}}\right){\xrightarrow[{}]{-\rho _{2}+\rho _{1}}}\left({\begin{array}{ccc|c}1&0&0&1\\0&1&0&1\\0&0&1&2\end{array}}\right)$

答案是 $x=1$, $y=1$, 以及 $z=2$.

注意，第一階段的主元操作從第一列進行到第三列，而第三階段的主元操作從第三列進行到第一列。

示例 1.2

我們通常將中間階段的操作組合成一個步驟，即使它們是對不同行的操作。

${\begin{array}{rcl}\left({\begin{array}{cc|c}2&1&7\\4&-2&6\end{array}}\right)&{\xrightarrow[{}]{-2\rho _{1}+\rho _{2}}}&\left({\begin{array}{cc|c}2&1&7\\0&-4&-8\end{array}}\right)\\&{\xrightarrow[{(-1/4)\rho _{2}}]{(1/2)\rho _{1}}}&\left({\begin{array}{cc|c}1&1/2&7/2\\0&1&2\end{array}}\right)\\&{\xrightarrow[{}]{-(1/2)\rho _{2}+\rho _{1}}}&\left({\begin{array}{cc|c}1&0&5/2\\0&1&2\end{array}}\right)\end{array}}$

答案是 $x=5/2$ 和 $y=2$.

高斯方法的這種擴充套件稱為 **高斯-若爾當消元法**。它超越了階梯形，到達一個更精煉、更專業的矩陣形式。

定義 1.3

一個矩陣如果除了是階梯形外，每個主元都是 1，並且是其所在列中唯一的非零元素，則稱為 **簡化階梯形**。

使用高斯-若爾當消元法求解線性方程組的缺點是，額外的行操作意味著額外的算術運算。優點是可以直接從簡化階梯形中讀出解集。

在任何階梯形，無論是普通階梯形還是簡化階梯形，我們都可以根據是否有矛盾方程來判斷方程組是否有解，如果每個變數都是某一行的主元，則方程組只有一個解；如果至少有一個變數是自由變數，則方程組有無窮多個解。

在簡化階梯形中，我們可以讀出方程組解集的型別及其描述。當然，如果方程組無解，無論階梯形是否簡化，我們都能很容易地描述解集。上面的兩個例子表明，如果方程組只有一個解，則解可以從增廣矩陣的最後一列中讀出。在解集為無窮多個解的情況下，解集的引數形式也可以從簡化階梯形中讀出。例如，考慮以下方程組，它被化簡為階梯形，然後又化簡為簡化階梯形。

$\left({\begin{array}{cccc|c}2&6&1&2&5\\0&3&1&4&1\\0&3&1&2&5\end{array}}\right){\xrightarrow[{}]{-\rho _{2}+\rho _{3}}}\left({\begin{array}{cccc|c}2&6&1&2&5\\0&3&1&4&1\\0&0&0&-2&4\end{array}}\right)$

${\xrightarrow[{\begin{array}{c}\\[-19pt]\scriptstyle (1/3)\rho _{2}\\[-5pt]\scriptstyle -(1/2)\rho _{3}\end{array}}]{(1/2)\rho _{1}}}\;{\xrightarrow[{-\rho _{3}+\rho _{1}}]{(4/3)\rho _{3}+\rho _{2}}}\;{\xrightarrow[{}]{-3\rho _{2}+\rho _{1}}}\left({\begin{array}{cccc|c}1&0&-1/2&0&-9/2\\0&1&1/3&0&3\\0&0&0&1&-2\end{array}}\right)$

從中間矩陣（階梯形版本）開始，回代法得到 $-2x_{4}=4$，因此 $x_{4}=-2$，然後另一個回代得到 $3x_{2}+x_{3}+4(-2)=1$，這意味著 $x_{2}=3-(1/3)x_{3}$，最後回代得到 $2x_{1}+6(3-(1/3)x_{3})+x_{3}+2(-2)=5$，這意味著 $x_{1}=-(9/2)+(1/2)x_{3}$。因此解集為：

$S=\{{\begin{pmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{pmatrix}}={\begin{pmatrix}-9/2\\3\\0\\-2\end{pmatrix}}+{\begin{pmatrix}1/2\\-1/3\\1\\0\end{pmatrix}}x_{3}\,{\big |}\,x_{3}\in \mathbb {R} \}$

現在，考慮到最後一個矩陣（簡化階梯形版本），注意透過將 $x_{3}$ 項移到另一邊來調整引數化，確實可以得到這個無限解集的描述。

這其中的部分原因很簡單。雖然一個集合可以有多種引數化描述它，例如，以下兩者也可以描述上述集合 $S$（取 $t$ 為 $x_{3}/6$ 且 $s$ 為 $x_{3}-1$)

$\{{\begin{pmatrix}-9/2\\3\\0\\-2\end{pmatrix}}+{\begin{pmatrix}3\\-2\\6\\0\end{pmatrix}}t\,{\big |}\,t\in \mathbb {R} \}\qquad \{{\begin{pmatrix}-4\\8/3\\1\\-2\end{pmatrix}}+{\begin{pmatrix}1/2\\-1/3\\1\\0\end{pmatrix}}s\,{\big |}\,s\in \mathbb {R} \}$

然而，我們在這本書中堅持使用未修改的自由變數（即 $x_{3}=x_{3}$ 而不是 $x_{3}=6t$）進行引數化。我們可以很容易地看到，一個系統的簡化階梯形式版本等同於一個使用未修改的自由變數進行引數化的版本。例如，

${\begin{array}{rl}x_{1}&=4-2x_{3}\\x_{2}&=3-x_{3}\end{array}}\quad \Longleftrightarrow \quad \left({\begin{array}{ccc|c}1&0&2&4\\0&1&1&3\\0&0&0&0\end{array}}\right)$

（為了從左到右，我們還需要知道系統中包含多少個方程）。因此，用自由變數進行引數化的慣例（透過為每個方程求解其主變數，然後從其他所有方程中消除該主變數）恰好等同於簡化階梯形式條件，即每個主元必須為 1，並且必須是其列中唯一的非零元素。

不那麼直觀的另一部分原因是，簡化階梯形式版本允許我們讀出如果我們在階梯形式停止並進行回代所獲得的引數化。前一段顯示簡化階梯形式對應於某種引數化，但為什麼是相同的引數化呢？一個解集可以用多種方式進行引數化，高斯消元法或高斯-約旦消元法也可以用多種方式進行，所以第一個猜測可能是我們可以推匯出相同起始系統的許多不同的簡化階梯形式版本和許多不同的引數化。但我們從未這樣做過。經驗表明，從同一個系統開始，以許多不同的方式進行行操作，總是會得到相同的簡化階梯形式和相同的引數化（使用未修改的自由變數）。

在本節的剩餘部分，我們將證明矩陣的簡化階梯形式版本是唯一的。因此，線性系統關於其未修改的自由變數的引數化是唯一的，因為兩個不同的引數化將給出兩個不同的簡化階梯形式。

我們將在這本書的其餘部分使用這個結果，以及導致它的結果，但也許以一種更直接地顯得有用的方式重新陳述會令人鼓舞。想象一下，我們求解一個線性系統，引數化，並在書的後面檢查答案。但那裡的引數化看起來不同。我們犯了錯誤，還是這些可能是對同一個集合的不同描述，就像上面對$S$的三個描述一樣？前一段指出，我們將在這裡證明，不同外觀的引數化（使用未修改的自由變數）描述了真正不同的集合。

這裡有一個非正式的論據，即矩陣的簡化行階梯形式是唯一的。再次考慮本節開頭矩陣的例子，它簡化為三個不同的行階梯形式矩陣。三個矩陣中的第一個是自然的行階梯形式版本。第二個矩陣與第一個相同，只是其中一行被減半了。第三個矩陣也是第一個的化妝變體。簡化行階梯形式的定義禁止了這種胡鬧。在簡化行階梯形式中，將一行減半是不可能的，因為這會將該行的首項更改為非 1，並且也不可能組合行，因為這樣一來，首項將不再在它的列中獨一無二。

這個非正式的論證不是證明；我們已經論證了，沒有兩個不同的簡化行階梯形式矩陣可以透過單一的操作步驟相關聯，但我們還沒有排除多個步驟可能會做到的可能性。在我們進行那個證明之前，我們將透過用一種有啟發性的術語來改述我們的工作來結束本小節。

許多不同的矩陣產生相同的簡化行階梯形式矩陣。本節開頭的三個行階梯形式矩陣以及它們派生出的矩陣，都給出了這個簡化行階梯形式矩陣。

${\begin{pmatrix}1&0\\0&1\end{pmatrix}}$

我們認為這些矩陣彼此相關。下一個結果說明了這種關係。

引理 1.4

初等行操作是可逆的。

證明

對於任何矩陣$A$，交換行的效果可以透過交換回來來逆轉，將一行乘以非零的$k$可以透過乘以$1/k$來撤銷，將行 $i$ 的倍數加到行 $j$（其中 $i\neq j$）可以透過從行 $j$ 中減去相同的行 $i$ 的倍數來撤銷。

$A{\xrightarrow[{}]{\rho _{i}\leftrightarrow \rho _{j}}}\;{\xrightarrow[{}]{\rho _{j}\leftrightarrow \rho _{i}}}A\qquad A{\xrightarrow[{}]{k\rho _{i}}}\;{\xrightarrow[{}]{(1/k)\rho _{i}}}A\qquad A{\xrightarrow[{}]{k\rho _{i}+\rho _{j}}}\;{\xrightarrow[{}]{-k\rho _{i}+\rho _{j}}}A$

（$i\neq j$ 條件是必要的。參見問題 7。）

這個引理表明，“化簡為”是誤導性的——當 $A\longrightarrow B$ 時，我們不應該認為 $B$ 是 “在” $A$ 之後” 或 “比” $A$ 更簡單”。相反，我們應該將它們視為相互可約或相互關聯的。下面是這個想法的圖示。本節開頭出現的矩陣及其行最簡形式版本顯示在一個群集中。它們都是相互可約的；這些關係也顯示出來。

我們說，彼此化簡的矩陣是“關於行化簡關係的等價矩陣”。下一個結果使用等價的定義來驗證此語句。

引理 1.5

在矩陣之間，“化簡為”是一種等價關係。

證明

我們必須檢查以下條件：（i）自反性，任何矩陣都化簡為自身；（ii）對稱性，如果 $A$ 化簡為 $B$ ，則 $B$ 化簡為 $A$ ；（iii）傳遞性，如果 $A$ 化簡為 $B$ 並且 $B$ 化簡為 $C$ ，則 $A$ 化簡為 $C$ 。

自反性很簡單；任何矩陣在零次行運算後都化簡為自身。

該關係是對稱的是 引理 1.4——如果 $A$ 透過一些行運算化簡為 $B$ ，則 $B$ 透過逆轉這些運算化簡為 $A$ 。

為了傳遞性，假設$A$ 簡化為 $B$，並且 $B$ 簡化為 $C$。將來自 $A\rightarrow \cdots \rightarrow B$ 的簡化步驟與來自 $B\rightarrow \cdots \rightarrow C$ 的簡化步驟連結起來，就得到了從 $A$ 到 $C$ 的簡化。

定義 1.6

透過初等行操作可以互相簡化的兩個矩陣稱為**行等價**。

下圖顯示所有矩陣的集合作為一個盒子。在該盒子內部，每個矩陣都屬於某個類別。當且僅當兩個矩陣可以互相簡化時，它們屬於同一類別。這些類別是互斥的——沒有矩陣屬於兩個不同的類別。 矩陣的集合被劃分成**行等價類**。

在這個劃分中，其中一個類別是上面顯示的矩陣簇，擴充套件到包括所有非奇異 $2\!\times \!2$ 矩陣。

下一小節證明了矩陣的簡化行階梯形是唯一的；每個矩陣都簡化為一個且僅一個簡化行階梯形矩陣。用行等價關係重新表述，我們將證明每個矩陣都行等價於一個且僅一個簡化行階梯形矩陣。就劃分而言，我們將證明的是：每個等價類包含一個且僅一個簡化行階梯形矩陣。因此，每個簡化行階梯形矩陣都作為其類別的代表。

在證明之後，正如在本節引言中提到的，我們將有辦法判斷一個矩陣是否可以透過行簡化從另一個矩陣推匯出。我們只需對兩個矩陣都應用高斯-約旦過程，然後看看它們是否簡化為同一個簡化行階梯形。

練習

建議所有讀者完成此練習。

問題 1

使用高斯-約旦簡化法解每個方程組。

1. ${\begin{array}{*{2}{rc}r}x&+&y&=&2\\x&-&y&=&0\end{array}}$
2. ${\begin{array}{*{3}{rc}r}x&&&-&z&=&4\\2x&+&2y&&&=&1\end{array}}$
3. ${\begin{array}{*{2}{rc}r}3x&-&2y&=&1\\6x&+&y&=&1/2\end{array}}$
4. ${\begin{array}{*{3}{rc}r}2x&-&y&&&=&-1\\x&+&3y&-&z&=&5\\&&y&+&2z&=&5\end{array}}$

建議所有讀者完成此練習。

問題 2

求每個矩陣的簡化行階梯形。

1. ${\begin{pmatrix}2&1\\1&3\end{pmatrix}}$
2. ${\begin{pmatrix}1&3&1\\2&0&4\\-1&-3&-3\end{pmatrix}}$
3. ${\begin{pmatrix}1&0&3&1&2\\1&4&2&1&5\\3&4&8&1&2\end{pmatrix}}$
4. ${\begin{pmatrix}0&1&3&2\\0&0&5&6\\1&5&1&5\end{pmatrix}}$

建議所有讀者完成此練習。

問題 3

使用高斯-約旦消元法求解每個解集，然後讀出引數化。

1. ${\begin{array}{*{3}{rc}r}2x&+&y&-&z&=&1\\4x&-&y&&&=&3\end{array}}$
2. ${\begin{array}{*{4}{rc}r}x&&&-&z&&&=&1\\&&y&+&2z&-&w&=&3\\x&+&2y&+&3z&-&w&=&7\end{array}}$
3. ${\begin{array}{*{4}{rc}r}x&-&y&+&z&&&=&0\\&&y&&&+&w&=&0\\3x&-&2y&+&3z&+&w&=&0\\&&-y&&&-&w&=&0\end{array}}$
4. ${\begin{array}{*{5}{rc}r}a&+&2b&+&3c&+&d&-&e&=&1\\3a&-&b&+&c&+&d&+&e&=&3\end{array}}$

問題 4

給出此矩陣的兩個不同的階梯形式版本。

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

建議所有讀者完成此練習。

問題 5

列出每個大小可能的簡化階梯形式。

1. $2\!\times \!2$
2. $2\!\times \!3$
3. $3\!\times \!2$
4. $3\!\times \!3$

建議所有讀者完成此練習。

問題 6

對非奇異矩陣應用高斯-若爾當消元法會得到什麼結果？

問題 7

引理 1.4 的證明中包含一個關於行主元操作的 $i\neq j$ 條件的引用。

1. 行操作的定義在交換操作 $\rho _{i}\leftrightarrow \rho _{j}$ 上有一個 $i\neq j$ 條件。證明 $A{\xrightarrow[{}]{\rho _{i}\leftrightarrow \rho _{j}}}\;{\xrightarrow[{}]{\rho _{i}\leftrightarrow \rho _{j}}}A$ 中，這個條件是不必要的。
2. 寫一個 $2\!\times \!2$ 矩陣，該矩陣具有非零項，並證明操作 $-1\cdot \rho _{1}+\rho _{1}$ 不能被操作 $1\cdot \rho _{1}+\rho _{1}$ 逆轉。
3. 擴充套件該引理的證明，明確說明在何處使用了關於主元操作的 $i\neq j$ 條件。

解答