線性代數/一次聯立方程式的解集合

增廣矩陣有無解的判定

定理

一個階梯形增廣矩陣 $A$ 無解若且唯若 $A$ 有非零列，且 $A$ 的最後一列非零列是 $\left[{\begin{array}{cccc|c}0&0&\dots &0&1\end{array}}\right]$ 。

證明

由於 $\left[{\begin{array}{cccc|c}0&0&\dots &0&1\end{array}}\right]$ 對應到方程式 1 = 0，因此 $A$ 的最後一列非零列是 $\left[{\begin{array}{cccc|c}0&0&\dots &0&1\end{array}}\right]$ 可以推得 $A$ 無解，而定理的另一個方向則是使用反證法：若 $A$ 沒有非零列，則所有 $\mathbb {R} ^{n}$ 中的元素都是 $A$ 的解，若 $A$ 有非零列且 $A$ 的最後一列非零列不是 $\left[{\begin{array}{cccc|c}0&0&\dots &0&1\end{array}}\right]$ ，則直接將 $A$ 的所有解寫出來，具體的做法請見下文。

簡化列階梯形矩陣

將一個增廣矩陣經由列運算化約成階梯形矩陣就已足夠判斷是否有解，但如果要將所有的解找出來，換言之要算出解集合，則需要再進一步的化減。

首先假設 $A=[a_{ij}]$ 已被化成階梯形矩陣，並假設 $A$ 共有 $k$ 列非零列，也就是說，第 $k$ 列是最後一列非零列。接著找到第 $k$ 列的首個非零元素，設為 $a_{kl}$ ，因此有 $a_{kl}=1$ 。下一步將第一列、第二列…至第 $k-1$ 列分別減去 $a_{1l},a_{2l},\dots ,a_{(k-1)l}$ 倍的第 $k$ 列，因此在做完列運算之後，第 $l$ 行除了 $a_{kl}=1$ 之外其他項都等於 0。

做完之後就沒有第 $k$ 列的事了，因此下個步驟就要針對第 $k-1$ 列做運算，假設該列的首個非零元素是 $a_{(k-1)l'}=1$ ，根據階梯形矩陣的定義，有 $l'<l$ 。然後將第一列、第二列…至第 $k-2$ 列分別減去 $a_{1l'},a_{2l'},\dots ,a_{(k-1)l'}$ 倍的第 $k-1$ 列，故做完之後第 $l'$ 行除 $a_{(k-1)l'}=1$ 外其他項皆為 0。接著不斷重複此操作，由下而上，將每列都作完操作，最終會得到一個簡化階梯形矩陣。

定義

一個矩陣 $A$ 被稱作是簡化列階梯形矩陣如果 $A$ 是一個階梯形矩陣且每列的首項非 0 元素是其所在行的唯一的非零元素。

解集合

假設現在增廣矩陣 $A$ 已經被化簡成簡化列階梯形矩陣，並且假設 $A$ 有解，換言之， $A$ 的最後一列非零列不是 $\left[{\begin{array}{cccc|c}0&0&\dots &0&1\end{array}}\right]$ ，下一步要將 $A$ 的解都解出來。

首先舉個例子，如果 $A$ 中有一列是 $\left[{\begin{array}{ccccc|c}0&0&1&-3&4&2\end{array}}\right]$ ，那該列對應到的式子是 $x_{3}-3x_{4}+4x_{5}=2$ ，可以將首個非 0 的項 $x_{3}$ 用其他項表達出來， $x_{3}=3x_{4}-4x_{5}+2$ ，由於 $A$ 是簡化列階梯型矩陣， $x_{3}$ 的表式中不會有其他列的首個非 0 項。