Elementary Row Operations

前一節中我們知道要解一個聯立方程組 $A\mathbf{x}=\mathbf{b}$, 可以先將 augmented matrix $[A\mid\mathbf{b}]$ 經由一系列的 elementary row operations 化成 $[A'\mid\mathbf{b'}]$ 其中 $A'$ 為 echelon form 後 再求解. 在本節中我們要說明為何經由 elementary row operations 我們可以將一個矩陣化為 echelon form 且解釋為何經由 elementary row operations 後所對應的聯立方程組與原方程組會有相同的解集合.

我們利用數學歸納法來說明為何一定可以將一個矩陣化為 echelon form. 或許有些人會對這裡數學歸納法處理的方式覺得奇怪, 不過若能仔細體會其真意, 會發現這是最好的處理方式. 我們是對矩陣的 row 的個數作數學歸納法. 先說明所有只有一個 row 的矩陣一定是 echelon form, 然後利用這件事實證明所有有兩個 row 的矩陣皆可利用 elementary row operations 化為 echelon form. 再利用兩個 row 的矩陣會成立的事實證明有 3 個 row 的矩陣也可利用 elementary row operations 化為 echelon form, 如此一直下去我們可證有 $4, 5, 6,\dots$ 個 row 的矩陣會成立. 不過這樣的方法我們可以證得有特定個數的 row 的矩陣會成立 (例如 10 個 row), 但無法證得一般的情形 (即任意個數的 row). 此時數學歸納法是最好的論證工具了. 若我們能知道有 $k$ 個 row 的矩陣一定能利用 elementary row operations 化為 echelon form 這個事實且利用這個事實證得有 $k+1$ 個 row 的矩陣一定能利用 elementary row operations 化為 echelon form, 這就表示當我們知道有一個 row 的矩陣能利用 elementary row operations 化為 echelon form 就能推得有兩個 row 的矩陣能利用 elementary row operations 化為 echelon form, 也進而推得有 3 個 row 的矩陣亦成立, 再進而推得有 4 個 row 的矩陣亦成立, 如此一直下去當然可知任意的矩陣皆能利用 elementary row operations 化為 echelon form.

由於這裡的論證不容易說明清楚, 我們先由一個例子來說明. 考慮一個有 $3$ 個 row 的矩陣

$$\left[ \begin{array}{rrrrr} 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 & 3 \\ 0 & 2 & 2 & 0 & -1 \\ \end{array}\right]$$

要將之化為 echelon form 首先第一個 row 必需是 leading entry 的位置在最左邊, 所以我們利用將第一,二兩個 row 交換的 elementary row operation 將此矩陣變換為

$$\left[ \begin{array}{rrrrr} 0 & 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 2 & 2 & 0 & -1 \\ \end{array}\right]$$

由於第三個 row 的 leading entry 位置與第一個 row 相同所以須將此位置的數消掉. 利用第一個 row 乘上 $-2$ 加到第三 個 row 的 elementary row operation 將此矩陣變換為

$$\left[ \begin{array}{rrrrr} 0 & 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & -2 & -2 & -7 \\ \end{array}\right]$$

如此一來第一個 row 以下的各 row 的 leading entry 所在位置都在第一個 row 的 leading entry 所在位置的右方. 接下來我們可以不再管第一個 row 而處理第一個 row 以下的部份. 此部份是一個僅有兩個 row 的矩陣

$$\left[ \begin{array}{rrrrr} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & -2 & -2 & -7 \\ \end{array}\right]$$

若我們知道變換兩個 row 的矩陣程 echelon 的方法, 直接套用就可以完成了. 事實上我們就是將上面的方法再處理一遍, 將第一個 row 乘以 $2$ 加到第二個 row 即可得

$$\left[ \begin{array}{rrrrr} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & -5 \\ \end{array}\right]$$

這一個 echelon form. 要注意我們故意忽略原來矩陣的第一個 row 的原因就是餵了能套用歸納法的假設. 事實上前一步是將矩陣

$$\left[ \begin{array}{rrrrr} 0 & 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & -2 & -2 & -7 \\ \end{array}\right]$$

的第二個 row 乘以 $2$ 加到第三個 row 得

$$\left[ \begin{array}{rrrrr} 0 & 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & -5 \\ \end{array}\right]$$

這一個 echelon form.

接下來我們處理一般的情形. 首先我們來看只有一個 row 的矩陣. 此時由於沒有任何的 row 在其下方所以依定義自然是 echelon form. 接著看有兩個 row 的矩陣. 首先注意依定義一個 echelon form 的第一個 row 其 leading entry (若有的話) 必在所有其他 row 的 leading entry 所在位置的左方. 所以我們在此有兩個 row 的矩陣挑出 leading entry 在最左方的一個 row (若兩個 row 的 leading entry 所在位置相同就任取一個 row) 利用 row 交換的 row operation 將之置於第一個 row. 接下來注意依定義下一個 row 的 leading entry 所在位置需在第一個 row 的 leading entry 的右方. 現若第二個 row 的 leading entry 所在位置和第一個 row 不同, 則因已知第一個 row 的 leading entry 所在位置在最左方, 第二個 row 的 leading entry 所在位置一定在第一個 row 的 leading entry 的右方, 故依定義此時已為 echelon form. 而若第二個 row 的 leading entry 所在位置和第一個 row 相同, 我們可將第一個 row 乘以 $-b/a$, 其中 $a$ 為第一個 row 的 leading entry 而 $b$ 為第二個 row 的 leading entry 再加到第二個 row 上. 如此一來第二個 row 原本的 leading entry 所在位置變為 0, 故其 leading entry 所在位置往右移了, 依定義此時為 echelon form.

我們可以如法泡製處理有 $3$ 個 row 的矩陣, 但由於要使用數學歸納法, 此時我們可直接假設我們以處理到有 $k$ 個 row 的矩陣了, 亦即有 $k$ 個 row 的矩陣皆可利用 elementary row operation 化為 echelon form. 現在我們要處理有 $k+1$ 個 row 的矩陣. 如欠面首先我們將 leading entry 的位置在最左邊的那個 row 利用兩 row 互換的 row operation 將之置於第一個 row. 假設此時第一個 row 的 leading entry 為 $a$. 接下來我們將 leading entry 的位置與第一個 row 的 leading entry 位置一樣的 row 挑出, 若該 row 的 leading entry 為 $b$, 我們便將第一個 row 乘上 $-b/a$ 後加到該 row 上. 如此一來該 row 的 leading entry 所在位置便往右移了. 一直重複此步驟, 直到第一個 row 以外的 row 其 leading entry 所在位置皆與第一個 row 的 leading entry 所在位置相異. 注意, 此時第一個 row 以下的各 row 其 leading entry 所在位置皆在第一個 row 的 leading entry 所在位置的右方. 若我們不看第一個 row, 所剩下的是一個有 $k$ 個 row 的矩陣, 所以利用前面已知有 $k$ 個 row 的矩陣皆可利用 elementary row operations 化為 echelon form, 我們可以利用 elementary row operations 將此矩陣第一個 row 以下的部份化為 echelon form. 但此時因各個 row 的 leading entry 所在位置皆在第一個 row 的 leading entry 所在位置的右方, 所以整個矩陣亦為 echelon form. 故得證所有矩陣皆可利用 elementary row operations 化為 echelon form. 大家或許注意到我們在化成 echelon form 的過程皆沒有用到將某個 row 乘上一非 0 實數這一個 elementary row operation. 事實上在化成 echelon form 的過程確實不需要這一種 row operation, 不過它在化為 以後要談的 ``reduced'' echelon form 的過程是需要的, 留待以後再談.

既然每一個矩陣都能用 elementary row operations 化為 echelon form, 接下來我們要說明的是利用 elementary row operation 處理後的聯立方程組其解集合不會改變. 要注意這裡指的是將 augmented matrix 用 elementary row operations 變換後的 augmented matrix 其對應的聯立方程組其解集合不會改變. 亦即聯立方程組 $A\mathbf{x}=\mathbf{b}$ 所對應的 augmented matrix $[A\mid\mathbf{b}]$ 若經一些 elementary row operations 後變換成 $[A'\mid\mathbf{b'}]$, 那麼其對應的聯立方程組 $A'\mathbf{x}=\mathbf{b'}$ 和原方程組 $A\mathbf{x}=\mathbf{b}$ 有相同的解集合. 不要誤以為是將係數矩陣 $A$ 利用 elementary row operations 變換成 $A'$ 後聯立方程組 $A'\mathbf{x}=\mathbf{b}$ 的解集合和原方程組 $A\mathbf{x}=\mathbf{b}$ 的解集合相同.

首先觀察若將一聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的 augmented matrix $[A\mid\mathbf{b}]$ 利用三種 elementary row operation 的任一種變換成 $[A'\mid\mathbf{b'}]$ 表示將原方程組利用加減消去法的三個基本方法之ㄧ將之變成方程組 $A'\mathbf{x}=\mathbf{b'}$. 然而方程組 $A\mathbf{x}=\mathbf{b}$ 若利用加減消去法的三種方法 (即將兩式子對調順序或將某一式乘上某個非 0 實數或將一個式子乘上某個實數加到另一個式子) 變換成方程組 $A'\mathbf{x}=\mathbf{b'}$, 原來滿足 $A\mathbf{x}=\mathbf{b}$ 的一組解仍會滿足 $A'\mathbf{x}=\mathbf{b'}$. 換句話說 $A\mathbf{x}=\mathbf{b}$ 的解集合會包含於 $A'\mathbf{x}=\mathbf{b'}$ 的解集合. 不過 elementary row operations 是可以還原回去的, 也就是說方程組 $A'\mathbf{x}=\mathbf{b'}$ 也可以用 elementary row operations 還原回原方程組 $A\mathbf{x}=\mathbf{b}$. 因此 $A'\mathbf{x}=\mathbf{b'}$ 的解集合也會包含於 $A\mathbf{x}=\mathbf{b}$ 的解集合. 因此得證 $A\mathbf{x}=\mathbf{b}$ 和 $A'\mathbf{x}=\mathbf{b'}$ 會有相同的解集合. 我們證得了 $[A\mid\mathbf{b}]$ 若經由一個 elementary row operation 後得 $[A'\mid\mathbf{b'}]$, 則它們所對應的聯立方程組會有相同的解集合. 因此若 $[A\mid\mathbf{b}]$ 經由好幾次的 elementary row operation 變換成 $[A'\mid\mathbf{b'}]$, 它們所對應的聯立方程組當然也會有相同的解集合.

我們已經了解要解一個聯立方程組 $A\mathbf{x}=\mathbf{b}$ 經要將 augmented matrix $[A\mid\mathbf{b}]$ 利用 elementary row operations 換成 $[A'\mid\mathbf{b'}]$ 其中 $A'$ 為 echelon form 後, 再解聯立方程組 $A'\mathbf{x}=\mathbf{b'}$ 即可. 所以我們僅需探討 $A'\mathbf{x}=\mathbf{b'}$ 其中 $A'$ 為 echelon form 這樣的聯立方程組的解即可. 在下節中 我們要說明此時為何聯立方程組的解就是如上一節所述的情形.