Echelon Form

我們已知要探討聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的解, 僅要考慮 $A$ 為 echelon form 的情形. 這一節中我們就是要討論當 $A$ 為 echelon form 時, 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的解集合. 事實上我們很容易理解利用 2.1 節中所提求解的方法所得的結果皆為方程組的一組解. 這裡要探討的是為何利用 2.1 節中所提求解的方法, 就可得所有的解.

如果我們得到 2.1 節 (2)(a) 的情形 (即 $A$ 有一個 row 全為 0 但 $\mathbf{b}$ 在該 row 不為 0), 在該節已說明此時方程組無解. 所以我們只要探討有解的情形. 首先回顧一下在 2.1 所提求解的方法: 首先我們要找到 free variables, 也就是是方程組除了 pivot variable 以外的 variable. 接著給這些 free variable 任意的參數值, 然後再利用由下往上代回的方式找到聯立方成組所有的解. 若無 free variable, 就直接由下往上一步一步求值即可.

由於可以忽略 augmented matrix 全為 0 的 row, 所以我們可假設係數矩陣 $A$ 沒有一個 row 全為 0. 因為 $A$ 為 echelon form, 這也表示 $A$ 每一個 row 皆有 leading entry 且為 pivot. 以下就是 pivot 對聯立方程組的解之重要性.

Lemma 2.3.1   假設 $A$ 為一有 $n$ 個 column 的 echelon form 且 $x_1=c_1,\dots,x_n=c_n$ 和 $x_1=d_1,\dots,x_n=d_n$ 皆為方程組 $A\mathbf{x}=\mathbf{b}$ 的一組解.

1. 假設 $x_n$ 為 $A$ 的一個 pivot variable. 則 $c_n=d_n$.
2. 假設 $x_k$ 為 $A$ 的一個 pivot variable, 其中 $1\le k\le n-1$. 若 $c_{k+1}=d_{k+1},\dots,c_n=d_n$, 則 $c_k=d_k$.

証 明. 假設聯立方程組為

$$\begin{array}{rcccrcl} a_{11}x_1 & + & \cdots & + & a_{1n}x... ...m1}x_1 & + & \cdots & + & a_{mn}x_n & = & b_m \\ \end{array}$$

其中

$$A=\left[ \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ a_... ...& \vdots \\ a_{m1} & \cdots & a_{mn} \\ \end{array}\right]$$

為 echelon form, 且不失一般性我們假設 $A$ 的每一個 row, $a_{i1},\dots,a_{in}$ 皆不全為 0.

1. 若 $x_n$ 為 $A$ 的一個 pivot variable, 表示 $A$ 的最後一個 row 的 leading entry 所在位置為 $x_n$. 也就是說 $a_{m1}=a_{m2}=\cdots=a_{m\,n-1}=0$ 且 $a_{mn}\ne 0$. 這表示此聯立方程組中最後一個式子為 $a_{mn}x_n=b_m$. 故由 $x_1=c_1,\dots,x_n=c_n$ 及 $x_1=d_1,\dots,x_n=d_n$ 皆為此聯立方程組的一組解知 $x_n=c_n$ 和 $x_n=d_n$ 皆需滿足 $a_{mn}x_n=b_m$, 亦即 $a_{mn}c_n=b_m$ 且 $a_{mn}d_n=b_m$. 故由 $a_{mn}\ne 0$ 得知 $c_n=d_n$.

2. 若 $x_k$ 為 $A$ 的一個 pivot variable, 表示 $A$ 有一個 row 的 leading entry 所在位置為 $x_k$. 也就是說若此 row 為 $A$ 的第 $i$ 個 row, 則 $a_{i1}=a_{i2}=\cdots=a_{i\,k-1}=0$ 且 $a_{ik}\ne 0$. 此 row 所對應的式子為 $a_{ik}x_k+\cdots+a_{in}x_n=b_{i}.$ 故由 $x_1=c_1,\dots,x_n=c_n$ 及 $x_1=d_1,\dots,x_n=d_n$ 皆為此聯立方程組的一組解知 $x_k=c_k,x_{k+1}=c_{k+1},\dots,x_n=c_n$ 和 $x_k=d_k,x_{k+1}=d_{k+1},\dots,x_n=d_n$ 皆需滿足 $a_{ik}x_k+\cdots+a_{in}x_n=b_{i}$. 因此由 $c_{k+1}=d_{k+1},\dots,c_n=d_n$ 的假設知
   $$a_{ik}c_k=b_i-(a_{i\,k+1}c_{k+1}+\cdots+a_{in}c_n)=a_{ik}d_k.$$
   再由 $a_{ik}\ne 0$ 得知 $c_k=d_k$.

$\qedsymbol$

相對於 pivot variable 我們知道對於 free variable 我們可以隨意取任何的實數而得到一組解, 所以我們有以下 free variable 對解的影響.

Lemma 2.3.2   假設 $A$ 為一有 $n$ 個 column 的 echelon form 且沒有一個 row 全為 0.

1. 假設 $x_n$ 為 $A$ 的一個 free variable. 則對任意的實數 $r$, 方程組 $A\mathbf{x}=\mathbf{b}$ 皆可找到一組解其 $x_n=r$.

2. 假設 $x_k$ 為 $A$ 的一個 free variable, 其中 $1\le k\le n-1$. 若 $x_1=c_1,\dots,x_n=c_n$ 為方程組 $A\mathbf{x}=\mathbf{b}$ 的一組解, 則對任意實數 $r$ 方程組 $A\mathbf{x}=\mathbf{b}$ 皆可找到一組解其 $x_k=r$ 且 $x_{k+1}=c_{k+1},\dots,x_n=c_n$.

証 明. 在前面所提的求解過程中我們知道可將 free variable 定為任意的實數, 再一步一步由下往上代回得到一組解. 在這個過程中我們了解到若 $x_i$ 是 free variable, 則它的取值可能會影響到的僅有 $x_j$, 其中 $j<i$ 這樣的變數, 而不會影響到其他變數 $x_l$, 其中 $l>i$ 的取值.

現若 $x_n$ 是 free variable, 這表示我們可以設定 $x_n$ 為任意實數, 再一步一步往上代求得聯立方程組的一組解, 所以對任意的實數 $r$, 方程組 $A\mathbf{x}=\mathbf{b}$ 皆可找到一組解其 $x_n$ 為 $r$.

若 $x_k$ 為 $A$ 的一個 free variable, 其中 $1\le k\le n-1$ 且已知 $x_1=c_1,\dots,x_n=c_n$ 為方程組 $A\mathbf{x}=\mathbf{b}$ 的一組解. 換言之, $x_{k+1}=c_{k+1},\dots,x_n=c_n$ 皆滿足方程組 pivot 的位置在 $x_k$ 右方所對應的那些方程式. 由於 $x_k$ 可取任意的實數且不會影響 $x_{k+1},\dots,x_n$ 的取值, 所以我們可令 $x_k=r$ 且 $x_{k+1}=c_{k+1},\dots,x_n=c_n$ 一步一步代回求得聯立方程組的一組解. $\qedsymbol$

Lemma 2.3.1 和 Lemma 2.3.2 有許多應用. 例如當 $A$ 是 echelon form 時若聯立方程組 $A\mathbf{x}=\mathbf{b}$ 已知有一個解 $x_1=-1,\dots,x_n=c_n$ 且 $x_1,\dots,x_n$ 每一個都是 pivot variable, 則由 Lemma 2.3.1 知聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的解僅能是 $x_1=c_1,\dots,x_n=c_n$. 換句話說此方程組的解唯一. 另一方面, 若 若聯立方程組 $A\mathbf{x}=\mathbf{b}$ 已知有解 且 $x_1,\dots,x_n$ 中有 free variable, 則由 Lemma 2.3.2 知聯立方程組 $A\mathbf{x}=\mathbf{b}$ 會有無窮多解.

當我們給一個矩陣時, 有許多種方法將之化為 echelon form, 而且化成的 echelon form 很可能不一樣. 不過利用 Lemma 2.3.1 和 Lemma 2.3.2 我們可以得到這些 echelon form 雖然可能不一樣, 但他們 pivot 的所在位置都會一致.

Proposition 2.3.3   給定一矩陣 $A$, 若 $A_1,A_2$ 均為 $A$ 利用 elementary row operations 化成的 echelon forms. 則 $A_1$ 和 $A_2$ 的 pivot 個數相同, 事實上他們的 pivot variables 是一致的.

証 明. 我們考慮 $A\mathbf{x}=\mathbf{0}$ 這一組聯立方程組, 其中 $A$ 有 $n$ 個 column (即此方程組有 $n$ 個變數). 因為 $A$ 可利用 elementary row operation 化為 $A_1$ 及 $A_2$, 這表示 augmented matrix $[A\mid\mathbf{0}]$ 可以利用 elementary row operation 化為 $[A_1\mid\mathbf{0}]$ 及 $[A_2\mid\mathbf{0}]$. 換句話說聯立方程組 $A_1\mathbf{x}=\mathbf{0}$ 和 $A_2\mathbf{x}=\mathbf{0}$ 皆與聯立方程組 $A\mathbf{x}=\mathbf{0}$ 有同樣的解. 要注意這些聯立方程組都會有解, 因為 $x_1=0,\dots,x_n=0$ 就是一組解.

我們要用反證法處理. 假設 $A_1$ 和 $A_2$ 有 pivot variable 不一致, 不失一般性我們就假設對 $A_1$ 來說 $x_i$ 是 pivot variable 但對 $A_2$ 來說 $x_i$ 不是 pivot variable (故為 free variable). 假設 $i=n$, 這表示方程組 $A_1\mathbf{x}=\mathbf{0}$ 的解中 $x_n$ 的取值是唯一的 (Lemma 2.3.1), 事實上 $x_n$ 一定為 0; 但 $A_2\mathbf{x}=\mathbf{0}$ 的解中 $x_n$ 的取值卻可以是任意的實數 (Lemma 2.3.2). 這和此二方程組有相同的解相矛盾. 現若 $1\le i\le n-1$. 利用 $x_1=0,\dots,x_n=0$ 已是這兩聯立方程組的解, 我們知道方程組 $A_1\mathbf{x}=\mathbf{0}$ 的解中一定找不到一組解其 $x_{i+1},\dots,x_n$ 的取值皆為 0 但 $x_i$ 的取值不是 0 (Lemma 2.3.1); 另一方面 Lemma 2.3.2 告訴我們 $A_2\mathbf{x}=\mathbf{0}$ 的解中一定可找到一組解其 $x_{i+1},\dots,x_n$ 的取值皆為 0 但 $x_i$ 的取值不是 0 (事實上 $x_i$ 可以是任意實數). 這又和 $A_1\mathbf{x}=\mathbf{0},A_2\mathbf{x}=\mathbf{0}$ 此二方程組有相同的解相矛盾. 故由反證法知 $A_1$ 和 $A_2$ 的 pivot variables 是一致的. $\qedsymbol$

現在我們回來說明當 $A$ 是 echelon form 時, 前幾節所述解聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的方法所求得的解就是所有的解. 也就是說若 $x_1=c_1,\dots,x_n=c_n$ 為 $A\mathbf{x}=\mathbf{b}$ 的一組解, 我們要說明這組解確實可由前面 2.1 節所提的方法得到. 為了方便起見我們令前面 2.1 節所提的方法所得的解所成的集合為 $S$. 現若 $x_n$ 為 pivot variable, 則由 Lemma 2.3.1 知, $S$ 的所有解中 $x_n$ 的取值一定也為 $c_n$. 若 $x_n$ 為 free variable, 則因 $S$ 的解中 $x_n$ 可為任意值, 故 $S$ 中一定有一組解其 $x_n$ 的取值為 $c_n$. 也就是說不管 $x_n$ 是否為 pivot variable, $S$ 中必有一組解其 $x_n$ 的取值為 $c_n$. 現若 $x_{n-1}$ 為 pivot variable, 再由 Lemma 2.3.1 知這一組解 $x_{n-1},x_n$ 的取值必為 $x_{n-1}=c_{n-1},x_n=c_n$; 而若 $x_{n-1}$ 為 free variable, 則因 $S$ 的解中 $x_{n-1}$ 可為任意值且其取值不影響到 $x_n$ 的取值, 故知 $S$ 中必有一組解其 $x_{n-1},x_n$ 的取值為 $x_{n-1}=c_{n-1},x_n=c_n$. 如此一直下去我們知道 $S$ 中必有一組解其 $x_1,\dots,x_n$ 的取值為 $x_{1}=c_{1},\dots,x_n=c_n$.

我們已完全了解整個解聯立方程組的步驟與原理了. 在求解的過程中還可以進一步將 echelon form 化為所謂的 reduced echelon form. Reduced echelon form 事實上仍為 echelon form, 不過再加上兩個限制, 第一個限制是每一個 pivot 需為 $1$. 另一個限制為 pivot 的位置上方全為 0. 要注意, 依定義 echelon form 的 pivot 位置下方已全為 0 所以 reduced echelon form 每一個 pivot 所在的 column, 除了自己需為 $1$ 外其他部分皆為 0. 例如

$$A=\left[ \begin{array}{cccc} 1 & 2 & 0 & 0 \\ 0 & 0 & 3 &... ...\ 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & -1 \\ \end{array}\right]$$

都不是 reduced echelon form 但是

$$A'=\left[ \begin{array}{cccc} 1 & 2 & 0 & 0 \\ 0 & 0 & 1 ... ...\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \\ \end{array}\right]$$

就是 reduced echelon form. 每一個 echelon form 皆可利用 elementary row operations 換為 reduced echelon form. 若有一個 row 的 pivot 為 $a$ (注意依定義 $a\ne 0$) 我們只要將該 row 乘上 $1/a$, 則該 row 的 pivot 便是 $1$ 了. 例如上面 $A$ 這一個 echelon form 若將第二個 row 乘上 $1/3$, 就可得 $A'$ 這一個 reduced echelon form. 當我們將每個 pivot 都變為 $1$ 後, 就可利用將該 row 乘上某一實數加到另一個 row 的方法將 pivot 所在的 column 的其他部分化為 0. 例如上面 $B$ 這一個 echelon form 若將第三個 row 乘上 $-1$ 加到第二個 row, 就可得 $B'$ 這一個 reduced echelon form. 既然每一個矩陣都可以經由 elementary row operation 化為 reduced echelon form, 所以我們可以利用這個方法求出聯立方程組的解. 化成 reduced echelon form 後求解可以幫助我們很快地看出解的形式, 例如方程組 $B'\mathbf{x}=\mathbf{0}$ 為

$$\begin{array}{rrrrcl} x_1 & & && = & 0 \\ & x_2 & & +3x_4&= & 0 \\ & & x_3&-x_4&= & 0 \\ \end{array}$$

它的解集合為 $x_1=0,x_2=-3t,x_3=t,x_4=t$ 其中 $t$ 為任意實數. 不過一般來說化為 reduced echelon form 比僅化為 echelon form 所需的步驟多了許多, 所以利用 echelon form 來求解還是比較簡潔.

最後我們說明一下, 雖然一個矩陣化為 echelon form 的情形不唯一, 不過我們可以利用 Proposition 2.3.3 的結果證明一個矩陣化為 reduced echelon form 的結果會唯一. 然而這個事實我們以後不會用到, 這裡就略去不證了.