線性方程 Ax=b 的通解與矩陣 A 的四個基本子空間整合算法

本文的閱讀等級：初級

令 $A$ 為一 $m\times n$ 階實矩陣。矩陣 $A$ 的行空間 (column space) 記為 $C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\}$ ，零空間 (nullspace) 記為 $N(A)=\{\mathbf{x}\in\mathbb{R}^n\vert A\mathbf{x}=\mathbf{0}\}$ 。對於 $n\times m$ 階轉置矩陣 $A^T$ ， $C(A^T)$ 稱為 $A$ 的列空間 (row space)， $N(A^T)$ 稱為 $A$ 的左零空間 (left nullspace)^[1]。以上是實矩陣 $A$ 的四個基本子空間，其中列空間 $C(A^T)$ 和零空間 $N(A)$ 是 $\mathbb{R}^n$ 的子空間，行空間 $C(A)$ 和左零空間 $N(A^T)$ 是 $\mathbb{R}^m$ 的子空間。考慮下面兩個計算問題：

給定一 $m$ 維向量 $\mathbf{b}$ ，求線性方程 $A\mathbf{x}=\mathbf{b}$ 的通解 $\mathbf{x}_g=\mathbf{x}_p+\mathbf{x}_h$ ，其中 $\mathbf{x}_p$ 為一特解，滿足 $A\mathbf{x}_p=\mathbf{b}$ ， $\mathbf{x}_h$ 稱為齊次解，滿足 $A\mathbf{x}_h=\mathbf{0}$ ，即 $\mathbf{x}_h\in N(A)$ 。
求矩陣 $A$ 的四個基本子空間基底。

高斯消去法是求線性方程 $A\mathbf{x}=\mathbf{b}$ 的通解的通用算法 (見“高斯消去法”)，消去法所執行的基本列運算亦可用來尋找矩陣 $A$ 的四個基本子空間基底 (見“矩陣的四個基本子空間基底算法”)。本文介紹一個採行基本列運算，一併解決上述兩個問題的整合算法。

我們先推演這個整合算法，之後再舉一例說明計算程序。傳統的線性方程解法直接化簡增廣矩陣 $\begin{bmatrix} A&\mathbf{b} \end{bmatrix}$ ，整合算法則將轉置矩陣 $A^T$ 、常數向量 $-\mathbf{b}^T$ 和單位矩陣 $I_n$ 合併為一個 $(n+1)\times(m+n)$ 階增廣矩陣，如下：

$\displaystyle \begin{bmatrix} A^T&I_n\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}$ 。

整合算法包含兩個步驟：

利用基本列運算化簡 $A^T$ 直到產生簡約列梯形式 (reduced row echelon form)；
以基本列運算的取代運算設法消去 $-\mathbf{b}^T$ ，但最底列不得與其他列交換或乘以任何常數 (乘以 $1$ 不發生作用)。

列運算過程可表示為一連串的矩陣乘積，引入 $\begin{bmatrix} I_n\\ \mathbf{0}^T \end{bmatrix}$ 的目的即在記錄所執行過的淨運算。令 $n\times n$ 階矩陣 $E$ 代表步驟 (1) 的列運算所對應的基本矩陣乘積 (見“特殊矩陣 (10)：基本矩陣”)。步驟 (1) 不改變最底列，故可表示為下列分塊矩陣乘法運算：

$\displaystyle \begin{bmatrix} E&\mathbf{0}\\ \mathbf{0}^T&1 \end{bmatrix}\begin{bmatrix} A^T&I_n\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}=\begin{bmatrix} EA^T&EI_n\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}=\begin{bmatrix} R&E\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}$ ，

其中 $n\times m$ 階矩陣 $R=EA^T$ 代表 $A^T$ 的簡約列梯形式。步驟 (2) 將 $\begin{bmatrix} R&E \end{bmatrix}$ 各列通乘一常數再加進最末列以期消滅 $-\mathbf{b}^T$ 。設 $\mathbf{w}=(w_1,\ldots,w_n)^T$ 的第 $i$ 元 $w_i$ 為乘入 $\begin{bmatrix} R&E \end{bmatrix}$ 的第 $i$ 列的常數，則

$\displaystyle \begin{bmatrix} I_n&\mathbf{0}\\ \mathbf{w}^T&1 \end{bmatrix}\begin{bmatrix} R&E\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}=\begin{bmatrix} I_nR&I_nE\\ \mathbf{w}^TR-\mathbf{b}^T&\mathbf{w}^TE \end{bmatrix}=\begin{bmatrix} R&E\\ \mathbf{w}^TEA^T-\mathbf{b}^T&\mathbf{w}^TE \end{bmatrix}$ 。

設簡約列梯形式 $R$ 的軸列 (pivot row，包含軸的列) 總數為 $r$ ，則 $\text{rank}A^T=r$ 。因為矩陣的列秩等於行秩， $\text{rank}A=r$ 。明顯地， $r\le\min\{m,n\}$ 。矩陣秩 $r$ 給出 $A$ 的四個基本子空間維數 (基底向量數)： $\dim C(A)=\dim C(A^T)=r$ ， $\dim N(A)=n-r$ ， $\dim N(A^T)=m-r$ 。令 $R=\begin{bmatrix} R_1\\ 0 \end{bmatrix}$ ，其中 $R_1$ 是軸列構成的 $r\times m$ 階分塊， $0$ 是 $(n-r)\times m$ 階分塊，且 $E=\begin{bmatrix} E_1\\ E_2 \end{bmatrix}$ ，其中 $E_1$ 是 $r\times n$ 階， $E_2$ 是 $(n-r)\times n$ 階。整合算法的化簡結果可表示為

$\begin{bmatrix} R_1&E_1\\ 0&E_2\\ \mathbf{w}^TEA^T-\mathbf{b}^T&\mathbf{w}^TE \end{bmatrix}$ 。

下面解說如何從化約後的增廣矩陣推導 $A$ 的四個基本子空間基底，以及線性方程 $A\mathbf{x}=\mathbf{b}$ 的通解。

行空間 $C(A)$

基本列運算是列的線性組合，因此 $A^T$ 和 $R$ 有相同的列空間，即 $C(A)=C(R^T)$ 。簡約列梯形式 $R$ 的 $r$ 個軸列形成一線性獨立集，故 $R_1$ 的所有列向量構成 $A$ 的行空間基底。

零空間 $N(A)$

使用 $E$ 和 $R$ 的分塊表達式，

$EA^T=\begin{bmatrix} E_1\\ E_2 \end{bmatrix}A^T=\begin{bmatrix} E_1A^T\\ E_2A^T \end{bmatrix}=\begin{bmatrix} R_1\\ 0 \end{bmatrix}=R$ ，

可得 $E_2A^T=0$ 。等號兩邊取轉置可得 $AE_2^T=0$ ，表明 $E_2$ 的列向量屬於 $N(A)$ 。基本矩陣乘積 $E$ 是可逆矩陣，必有線性獨立的列向量，故 $E_2$ 的列向量集構成 $A$ 的零空間基底。

列空間 $C(A^T)$

基本列運算改變了 $A^T$ 的行空間，即 $A$ 的列空間，可知 $C(A^T)\neq C(R)$ 。雖然由簡約列梯形式 $R$ 無法推知 $A$ 的列空間，但基本列運算不改變行向量之間的線性組合關係 (見“左乘還是右乘，這就是問題所在”)，因為這個緣故， $R$ 的軸行指標就是 $A^T$ 的線性獨立行向量指標，推知 $A^T$ 的所有線性獨立行向量構成 $A$ 的列空間基底。

左零空間 $N(A^T)$

基本列運算非但不改變 $A^T$ 的列空間，也不破壞 $A^T$ 的零空間，即 $N(A^T)=N(R)$ 。簡約列梯形式 $R$ 唯一決定 $m\times (m-r)$ 階零空間矩陣 (nullspace matrix) $P$ 使得 $RP=0$ (定義及推導見“零空間的快捷算法”)。因為 $P$ 的行向量是一線性獨立集，它們構成 $A$ 的左零空間基底。

通解 $\mathbf{x}_g$

如果存在 $\mathbf{w}$ 使得 $\mathbf{w}^TEA^T-\mathbf{b}^T=\mathbf{0}^T$ ，則線性方程 $A\mathbf{x}=\mathbf{b}$ 存在至少一解，否則無解 (因為 $-\mathbf{b}^T$ 無法表示為 $A^T$ 的列向量的線性組合)。等號兩邊取轉置可得 $AE^T\mathbf{w}=\mathbf{b}$ ，故 $E^T\mathbf{w}$ 為一特解，由增廣矩陣的底列分塊 $\mathbf{w}^TE$ 給出。使用 $N(A)=C(E_2^T)$ ，通解可表示為 $\mathbf{x}_g=\mathbf{x}_p+\mathbf{x}_h$ ，其中 $\mathbf{x}_p=E^T\mathbf{w}$ 且 $\mathbf{x}_h\in C(E_2^T)$ 。

我們用一個例子來展示矩陣的四個基本子空間基底與線性方程的通解的整合算法。考慮 $4\times 5$ 階矩陣

$A=\begin{bmatrix} 2&6&2&2&2\\ 1&3&1&1&1\\ 3&9&3&4&5\\ 1&3&1&2&3 \end{bmatrix}$ ，

求 $C(A)$ ， $N(A)$ ， $C(A^T)$ 和 $N(A^T)$ 的基底，以及 $A\mathbf{x}=\mathbf{b}$ 的通解，其中 $\mathbf{b}=(4,2,4,0)^T$ 。

步驟一：利用基本列運算將 $\begin{bmatrix} A^T&I_5\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}$ 的 $A^T$ 化簡至簡約列梯形式，得到 $\begin{bmatrix} R&E\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}$ ，接著執行取代運算設法消去 $-\mathbf{b}^T$ ，結果表示為 $\begin{bmatrix} R_1&E_1\\ 0&E_2\\ \mathbf{w}^TEA^T-\mathbf{b}^T&\mathbf{w}^TE \end{bmatrix}$ ，如下：

$\displaystyle\begin{aligned} \left[\!\!\begin{array}{rrrccccccc} 2&1&3&1&\vline&1&0&0&0&0\\ 6&3&9&3&\vline&0&1&0&0&0\\ 2&1&3&1&\vline&0&0&1&0&0\\ 2&1&4&2&\vline&0&0&0&1&0\\ 2&1&5&3&\vline&0&0&0&0&1\\\hline -4&-2&-4&0&\vline&0&0&0&0&0 \end{array}\!\!\right]&\to \left[\!\!\begin{array}{rrrrcrccrc} 1&\frac{1}{2}&0&-1&\vline&2&0&0&-\frac{3}{2}&0\\ 0&0&1&1&\vline&-1&0&0&1&0\\\hline 0&0&0&0&\vline&-3&1&0&0&0\\ 0&0&0&0&\vline&-1&0&1&0&0\\ 0&0&0&0&\vline&1&0&0&-2&1\\\hline -4&-2&-4&0&\vline&0&0&0&0&0 \end{array}\!\!\right]\\ &\to \left[\!\!\begin{array}{rrrrcrccrc} 1&\frac{1}{2}&0&-1&\vline&2&0&0&-\frac{3}{2}&0\\ 0&0&1&1&\vline&-1&0&0&1&0\\\hline 0&0&0&0&\vline&-3&1&0&0&0\\ 0&0&0&0&\vline&-1&0&1&0&0\\ 0&0&0&0&\vline&1&0&0&-2&1\\\hline 0&0&0&0&\vline&4&0&0&-2&0 \end{array}\!\!\right] \end{aligned}$

步驟二：將重要的結果整理出來。簡約列梯形式 $R$ 的1，3行是軸行，故 $r=2$ 。分塊 $-\mathbf{b}^T$ 成功地被消去，可知 $A\mathbf{x}=\mathbf{b}$ 有解， $\mathbf{x}_p=(4,0,0,-2,0)^T$ 為一特解。提取主要的分塊並列出零空間矩陣：

$\displaystyle R_1=\left[\!\!\begin{array}{crcr} 1&\frac{1}{2}&0&-1\\ 0&0&1&1 \end{array}\!\!\right],~~E_2=\left[\!\!\begin{array}{rccrc} -3&1&0&0&0\\ -1&0&1&0&0\\ 1&0&0&-2&1 \end{array}\!\!\right],~~P=\left[\!\!\begin{array}{rr} -\frac{1}{2}&1\\ 1&0\\ 0&-1\\ 0&1 \end{array}\!\!\right]$ 。

步驟三：寫出四個基本子空間基底。

行空間 $C(A)$ 的基底由 $R_1$ 的列向量組成：

$\left[\!\!\begin{array}{r} 1\\ \frac{1}{2}\\ 0\\ -1 \end{array}\!\!\right],~~\left[\!\!\begin{array}{c} 0\\ 0\\ 1\\ 1 \end{array}\!\!\right]$ 。

零空間 $N(A)$ 的基底由 $E_2$ 的列向量組成：

$\left[\!\!\begin{array}{r} -3\\ 1\\ 0\\ 0\\ 0 \end{array}\!\!\right],~~\left[\!\!\begin{array}{r} -1\\ 0\\ 1\\ 0\\ 0 \end{array}\!\!\right],~~\left[\!\!\begin{array}{r} 1\\ 0\\ 0\\ -2\\ 1 \end{array}\!\!\right]$ 。

列空間 $C(A^T)$ 的基底是 $A^T$ 的軸行，即第1，3行：

$\left[\!\!\begin{array}{c} 2\\ 6\\ 2\\ 2\\ 2 \end{array}\!\!\right],~~\left[\!\!\begin{array}{c} 3\\ 9\\ 3\\ 4\\ 5 \end{array}\!\!\right]$ 。

左零空間 $N(A^T)$ 的基底由 $P$ 的行向量組成：

$\displaystyle \left[\!\!\begin{array}{r} -\frac{1}{2}\\ 1\\ 0\\ 0 \end{array}\!\!\right],~~\left[\!\!\begin{array}{r} 1\\ 0\\ -1\\ 1 \end{array}\!\!\right]$ 。

步驟四：寫出通解

$\displaystyle \mathbf{x}_g=\left[\!\!\begin{array}{r} 4\\ 0\\ 0\\ -2\\ 0 \end{array}\!\!\right]+\alpha\left[\!\!\begin{array}{r} -3\\ 1\\ 0\\ 0\\ 0 \end{array}\!\!\right]+\beta\left[\!\!\begin{array}{r} -1\\ 0\\ 1\\ 0\\ 0 \end{array}\!\!\right]+\gamma\left[\!\!\begin{array}{r} 1\\ 0\\ 0\\ -2\\ 1 \end{array}\!\!\right]$ ，

其中 $\alpha,\beta,\gamma$ 是任意數。

如果我們只要計算 $A\mathbf{x}=\mathbf{b}$ 的通解，一旦 $A^T$ 約化至列梯形式，便可開始消去 $-\mathbf{b}^T$ 。與高斯消去法的化簡過程 $\begin{bmatrix} A&\mathbf{b} \end{bmatrix}\to\begin{bmatrix} U&\mathbf{c} \end{bmatrix}$ 相比較 (這裡 $U$ 是列梯形式)，此法的優點是不必經過反向代入程序解開 $U\mathbf{x}=\mathbf{c}$ 。不過，天下沒有白吃的午餐，此法的缺點是加大的增廣矩陣 $\begin{bmatrix} A^T&I_n\\ -\mathbf{b}^T&\mathbf{0}^T \end{bmatrix}$ 耗用較多的簿記和計算。

註解：
[1] 在台灣，橫向稱為列，縱向稱為行。在中國大陸，橫向稱為行，縱向稱為列。

2 Responses to 線性方程 Ax=b 的通解與矩陣 A 的四個基本子空間整合算法

老羅 says:

11/20/2014 at 5:24 pm

您好:
這篇看了好幾遍，
文中的 $\mathbf{w}^{T}$ , 到底怎麼算呢?

用高斯-約當法，就可以算出 $\begin{bmatrix} 4 & 0 & 0 & -2 & 0 \end{bmatrix}$ ,
也想用 $\mathbf{w}^{T}E$ 來算一下。

謝謝!!

- ccjou says:
  
  11/20/2014 at 9:09 pm
  
  這個算法的主旨是運用基本列運算求線性方程的通解和係數矩陣的基本子空間基底， $\mathbf{w}$ 只是為了推導算法而生的向量。
  
  上文說了，步驟 (2) 將 $\begin{bmatrix} R&E \end{bmatrix}$ 各列通乘一常數再加進最末列以期消滅 $-\mathbf{b}^T$ 。設 $\mathbf{w}=(w_1,\ldots,w_n)^T$ 的第 $i$ 元 $w_i$ 為乘入 $\begin{bmatrix} R&E \end{bmatrix}$ 的第 $i$ 列的常數。

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨