Rank of a Matrix

從前幾節解聯立方成組的方法來看, 當一聯立方程組其係數矩陣化為 echelon form 後我們很容易判斷其是否有解, 解是否唯一. 其中 pivot 的個數就是影響到聯立方程組解的個數的重要因素. 本節中我們就是要探討 pivot 的個數和解的個數之關係.

Definition 2.4.1   將一矩陣利用 elementary row operations 化為 echelon form 後, 其不全為 0 的 row 的個數 (即 pivot 的個數) 稱為此矩陣的 rank. 若 $A$ 是一個矩陣, 則將 $A$ 的 rank 記為 $\mathrm{rank}(A)$.

我們曾經提醒過, 要給一個定義前需注意這個定義是否 well-defined. 當我們給一個矩陣時, 有許多種方法將之化為 echelon form, 而且化成的 echelon form 很可能不一樣. 所以要確認 rank 是 well-defined 我們就必須要知道給定一個矩陣, 不管用怎樣的 elementary row operations 所得的 echelon form 它們的 pivot 個數都相同. 事實上 Proposition 2.3.3 已經告訴我們這個事實, 所以這裡 rank 的定義沒有問題.

若一個矩陣 $A$ 有 $m$ 個 row 和 $n$ 個 column, 由於每個 row 致多僅有一個 pivot, 而每個 column 也至多僅有一個 pivot, 所以 pivot 的個數不能超過 row 的個數以及 column 的個數, 換言之我們有 $\mathrm{rank}(A)\le m$ 且 $\mathrm{rank}(A)\le n$. 如果 $m\ge n$, 則 $\mathrm{rank}(A)\le n$ 就足以表達這兩個不等式, 反之若 $n\ge m$, 則 $\mathrm{rank}(A)\le m$ 就足以表達這兩個不等式. 所以若我們令 $\min\{m,n\}$ 表示取 $m,n$ 中較小的數, 就會有以下之結果.

Proposition 2.4.2   若矩陣 $A$ 有 $m$ 個 row 和 $n$ 個 column, 則

$$\mathrm{rank}(A)\le\min\{m,n\}.$$

當 proposition 2.4.2 中的不等式其等號成立時, 方程組的解的情形便可以掌握. 事實上我們有以下的結果.

Theorem 2.4.3   假設矩陣 $A$ 有 $m$ 個 row 和 $n$ 個 column.

1. 若 $\mathrm{rank}(A)=m$ 則對任意 $\mathbf{b}\in\mathbb{R}^m$, 方程組 $A\mathbf{x}=\mathbf{b}$ 皆有解; 反之, 若 $\mathrm{rank}(A)\ne m$ 則存在 $\mathbf{b}\in\mathbb{R}^m$ 使得方程組 $A\mathbf{x}=\mathbf{b}$ 無解.

2. 若 $\mathrm{rank}(A)=n$ 則當方程組 $A\mathbf{x}=\mathbf{b}$ 有解時其解唯一; 反之, 若 $\mathrm{rank}(A)\ne n$ 則當方程組 $A\mathbf{x}=\mathbf{b}$ 有解時, 會有無窮多解.

証 明. 首先我們說明一下為何這裡要考慮 $\mathbf{b}\in\mathbb{R}^m$. 依假設係數矩陣 $A$ 有 $m$ 個 row 和 $n$ 個 column 這表示 $A\mathbf{x}=\mathbf{b}$ 是一個有 $n$ 個未知數和 $m$ 個方程式的聯立方程組. 而 $\mathbf{b}$ 代表的是方程組每個式子的常數項, 既然有 $m$ 個方程式自然需要 $m$ 個數字來表示這些常數項, 所以 $\mathbf{b}\in\mathbb{R}^m$.

為了方便起見我們假設聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的 augmented matrix $[A\mid\mathbf{b}]$ 利用 elementary row operations 可化為 $[A'\mid\mathbf{b'}]$ 其中 $A'$ 為 echelon form.

1. 若 $\mathrm{rank}(A)=m$, 表示解聯立方程式將係數矩陣 $A$ 化為 echelon form 後, 每一個 row 皆有 pivot, 亦即每一個 row 不全為 0. 故由 2.1 節的討論我們之此時聯立方程組一定都有解.

   反之, 若 $\mathrm{rank}(A)\ne m$, 因已知 $\mathrm{rank}(A)\le m$, 這表示 $\mathrm{rank}(A)<m$. 也就是說 echelon form $A'$ 的最後一個 row 必全為 0, 因此此時若

   $$\mathbf{b'}=\left[ \begin{array}{c} b_1' \\ \vdots \\ b_m' \\ \end{array}\right]$$
   且 $b_m'\ne 0$, 則 $[A'\mid\mathbf{b'}]$ 所對應的聯立方程組無解, 亦即原方程組無解. 因此我們只要選一組 $\mathbf{b'}$ 其中 $b_m'\ne 0$, 再將 augmented matrix $[A'\mid\mathbf{b'}]$ 利用 elementary row operation 還原為 $[A\mid\mathbf{b}]$, 則此 $\mathbf{b}\in\mathbb{R}^m$ 會使得 $A\mathbf{x}=\mathbf{b}$ 無解.

2. 若 $\mathrm{rank}(A)=n$, 表示解聯立方程式將係數矩陣 $A$ 化為 echelon form 後, 每一個 column 皆有 pivot, 亦即 $x_1,\dots,x_n$ 每一個都是 pivot variable (也就是說沒有 free variable). 因此若聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解依 Lemma 2.3.1 知聯立方程組的解唯一.

   反之, 若 $\mathrm{rank}(A)\ne n$, 這也表示 $\mathrm{rank}(A)<n$, 故知 $x_1,\dots,x_n$ 這 $n$ 個 variable 中必有 free variable. 因此若聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解依 Lemma 2.3.2 知聯立方程組有無窮多解.

$\qedsymbol$

要注意 Theorem 2.4.3 (1) 說的是若 $\mathrm{rank}(A)$ 不等於 row 的個數, 則聯立方程組有可能無解 (注意僅是有可能, 所以也有可能有解). 因此當聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的方程式個數多於未知數的個數時, 即 $A$ 的 row 的個數 $m$ 大於 $A$ 的 column 的個數 $n$. 此時由 Proposition 2.4.2 知 $\mathrm{rank}(A)\le n<m$, 故由 Theorem 2.4.3 (1) 的結果知, 此聯立方程組有可能無解. 不過這並不表示當方程式個數小於或等於未知數的個數時方程組一定有解.

若未知數的個數多於方程式的個數時, 此時 $n>m$, 故由 Proposition 2.4.2 知 $\mathrm{rank}(A)\le m<n$. 因此由 Proposition 2.4.3 (2) 的結果知此聯立方程組若有解的話, 會有無窮多組解. 另一方面 Theorem 2.4.3 (2) 說的是若 $\mathrm{rank}(A)$ 等於 column 的個數時, 則當聯立方程組有解時其解唯一. 注意這並不表示聯立方程組一定有解. 不過當方程組是 $A\mathbf{x}=\mathbf{0}$, 由於此方程組一定有解 (即 $x_1=\cdots=x_n=0$ 為一解), 所以我們有以下之結果.

Corollary 2.4.4   假設矩陣 $A$ 有 $m$ 個 row 和 $n$ 個 column. 則 $A\mathbf{x}=\mathbf{0}$ 有唯一解若且唯若 $\mathrm{rank}(A)=n$.

在數學上一個理論的推廣, 若一個結果可由某定理直接推得我們就稱為 Corollary. 上一個結果由於已知 $A\mathbf{x}=\mathbf{0}$ 一定有解, 所以可以直接由 Theorem 2.4.3 推得, 因此我們用 Corollary 稱之.

當方程式個數等於未知數的個數時 (即 $m=n$), 我們有以下之結果.

Corollary 2.4.5   假設矩陣 $A$ 有 $n$ 個 row 和 $n$ 個 column. 則 $\mathrm{rank}(A)=n$ 若且唯若對任意 $\mathbf{b}\in\mathbb{R}^n$, 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 必有解且其解唯一.

証 明. 假設 $\mathrm{rank}(A)=n$, 因為 $\mathrm{rank}(A)$ 等於 row 的個數, 故由 Theorem 2.4.3 (1) 知對任意 $\mathbf{b}\in\mathbb{R}^n$, 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 必有解. 另一方面, $\mathrm{rank}(A)$ 等於 column 的個數, 故由 Theorem 2.4.3 (2) 此有解之聯立方程組的解唯一.

假設對任意 $\mathbf{b}\in\mathbb{R}^n$, 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 必有解且其解唯一. 特別地當 $\mathbf{b}=\mathbf{0}$ 時 $A\mathbf{x}=\mathbf{0}$ 的解唯一. 故由 Corollary 2.4.4 知 $\mathrm{rank}(A)=n$. $\qedsymbol$

我們已經知道當 $\mathrm{rank}(A)$ 等於 column 的個數或 row 的個數時, 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 的解有一些重要的性質. 而當 $\mathrm{rank}(A)$ 不等於 column 的個數時, 以後我們會知道若聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解時, 它們的解會和 $A\mathbf{x}=\mathbf{0}$ 的無窮多個解有關. 接下來我們要談的是當 $\mathrm{rank}(A)$ 不等於 row 的個數時, 如何判斷哪些 $\mathbf{b}\in\mathbb{R}^m$ 會使得 $A\mathbf{x}=\mathbf{b}$ 有解, 哪些會無解. 首先我們利用一個例子來說明:

Example 2.4.6   我們想找到所有可能的 $b_1,b_2,b_3,b_4\in\mathbb{R}$ 使得以下的聯立方程組有解.

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & b_1 \\ 3x_1& ... ...x_3&= & b_3 \\ 3x_1& -3x_2 &+3 x_3&= & b_4 \\ \end{array}$$

首先我們考慮 augmented matrix

$$\left[ \begin{array}{rrr\vert c} 1 & -1 & 1 & b_1 \\ 3 & ... ...1 & 4 & -3 & b_3 \\ 3 & -3 & 3 & b_4 \\ \end{array}\right]$$

將第一個 row 分別乘上 $-3,-1,-3$ 加到第二,三,四個 row 得

$$\left[ \begin{array}{rrr\vert c} 1 & -1 & 1 & b_1 \\ 0 & ... ...4 & b_3-b_1 \\ 0 & 0 & 0 & b_4-3b_1 \\ \end{array}\right].$$

再將此 augmented matrix 的第二個 row 乘上 $-1$ 加到第三個 row, 得

$$\left[ \begin{array}{rrr\vert c} 1 & -1 & 1 & b_1 \\ 0 & ... ...4 & b_3-b_1 \\ 0 & 0 & 0 & b_4-3b_1 \\ \end{array}\right].$$

換言之, 我們經由 elementary row operations 將係數矩陣化為 echelon form 得到以下有相同解的聯立方程組

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & b_1 \\ & 5x_2... ...2+2b_1 \\ 0x_1& +0x_2 &+0 x_3&= & b_4-3b_1 \\ \end{array}$$

要注意, 這裡我們將係數矩陣全為 0 的 row (即第三,四 row) 所對應的方程式係數用 0 標出, 主要是呼應 2.1 節 (2)(a) 的情形 (即 $A$ 有一個 row 全為 0 但 $\mathbf{b}$ 在該 row 不為 0). 由此知, 若 $b_3-b_2+2b_1\ne 0$ 或 $b_4-3b_1\ne 0$ 則不管 $x_1,x_2,x_3$ 代任何實數皆無法滿足方程式 $0x_1 +0x_2 +0 x_3= b_3-b_2+2b_1$ 以及 $0x_1 +0x_2 +0 x_3= b_4-3b_1$, 亦即此聯立方程組無解. 反之若 $b_3-b_2+2b_1=0$ 且 $b_4-3b_1= 0$, 此時原方程組的解等同於方程組

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & b_1 \\ & 5x_2 & -4x_3&= & b_2-3b_1 \\ \end{array}$$

的解, 由 2.1 節的討論之此時必有解. 也就是說原方程組有沒有解, 完全取決於 $b_3-b_2+2b_1$ 以及 $b_4-3b_1$ 是否皆為 0. 若 $b_3-b_2+2b_1=0$ 且 $b_4-3b_1= 0$, 則聯立方程組必有解. 若 $b_3-b_2+2b_1\ne 0$ 或 $b_4-3b_1\ne 0$ 則聯立方程組必無解. 例如當 $b_1=1, b_2=1,b_3=-1,b_4=3$ 時我們得 $b_1,b_2,b_3,b_4$ 皆滿足 $b_3-b_2+2b_1=0$ 且 $b_4-3b_1= 0$, 所以聯立方程組

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & 1 \\ 3x_1& +2... ...-3 x_3&= & -1 \\ 3x_1& -3x_2 &+3 x_3&= & 3 \\ \end{array}$$

有解. 但若 $b_1=1, b_2=1,b_3=-1,b_4=2$, 此時 $b_4-3b_1\ne 0$, 故知聯立方程組

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & 1 \\ 3x_1& +2... ...-3 x_3&= & -1 \\ 3x_1& -3x_2 &+3 x_3&= & 2 \\ \end{array}$$

無解.

由 Example 2.4.6 的說明, 我們可以理解一般來說若給定一個有 $m$ 個 row 的係數矩陣 $A$, 我們要找到 $\mathbf{b}$ 使得聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解. 首先我們將 $\mathbf{b}$ 寫成

$$\mathbf{b}=\left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_m \\ \end{array}\right]$$

然後利用 elementary row operations 將 augmented matrix $[A\mid\mathbf{b}]$ 化成 $[A'\mid\mathbf{b'}]$ 其中 $A'$ 為 echelon form. 注意這裡因為 $\mathbf{b}$ 是由 $b_i$ 這樣的變數來表示, 所以 $\mathbf{b'}$ 每一個位置是一些由 $b_i$ 所組成的(一次)多項式. 挑出 $A'$ 中全為 0 的 row, 令 $\mathbf{b'}$ 在這些 row 所對應的多項式為 0 的方程式稱為此聯立方程組的 constrain equations. 使得 constrain equations 皆為 0 的 $\mathbf{b}$ 就是使得聯立方程組有解的 $\mathbf{b}$. 例如在 Example 2.4.6 中,

$$b_3-b_2+2b_1=0,\,b_4-3b_1=0$$

就是聯立方程組

$$\begin{array}{rrrcl} x_1 & -x_2 & +x_3& = & b_1 \\ 3x_1& ... ...x_3&= & b_3 \\ 3x_1& -3x_2 &+3 x_3&= & b_4 \\ \end{array}$$

的 constrain equations. 寫下 constrain equations 的意義就是使得聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解的那些 $\mathbf{b}$ 的``限制''. 亦即, 滿足 constrain equations 的 $\mathbf{b}$ 就會使得聯立方程組 $A\mathbf{x}=\mathbf{b}$ 有解; 而不滿足 constrain equations 的 $\mathbf{b}$ 就會使得聯立方程組 $A\mathbf{x}=\mathbf{b}$ 無解. 特別地, 當 $\mathrm{rank}(A)$ 等於 $A$ 的 row 的個數 $m$ 時, 由於沒有 constrain equation, 也就是說 $\mathbf{b}$ 沒有限制, 所以對任意的 $\mathbf{b}\in\mathbb{R}^m$ 聯立方程組 $A\mathbf{x}=\mathbf{b}$ 皆有解. 這和 Theorem 2.4.3 (1) 的結果是一致的.