零空間的快捷算法

本文的閱讀等級：初級

令 $A$ 為一個 $m\times n$ 階矩陣。齊次方程 $A\mathbf{x}=\mathbf{0}$ 的所有解組成的集合稱為矩陣 $A$ 的零空間 (nullspace) 或核 (kernel)，記作 $N(A)$ 。在線性代數中，零空間的計算主要出現於求線性方程 $A\mathbf{x}=\mathbf{b}$ 的通解，以及方陣 $A$ ( $m=n$ ) 對應特徵值 $\lambda$ 的 (非零) 特徵向量 $\mathbf{x}$ 使得 $(A-\lambda I)\mathbf{x}=\mathbf{0}$ 。本文介紹兩個基於簡約列梯形式 (reduced row echelon form) 的零空間快捷算法。

我用一個例子來說明。考慮下列齊次方程 $A\mathbf{x}=\mathbf{0}$ ，係數矩陣為

$A=\left[\!\!\begin{array}{rrrcrr} 1 &4 &0 &1 &-3 & 2\\ 2 &8 &1 &1 &-4 &6 \\ -1 & -4 &-1 &0 &1 &-2\\ 1 &4 &0 &1 &-3 &1 \end{array}\!\!\right]$ 。

運用高斯消去法化簡 $A$ 可得簡約列梯形式 (見“高斯─約當法”)

$R=\left[\!\!\begin{array}{cccrrc} 1 & 4 & 0 &1& -3 & 0 \\ 0 & 0 & 1 &-1& 2 & 0 \\ 0 & 0 & 0 &0& 0 & 1 \\ 0 & 0 & 0 &0& 0 & 0 \end{array}\!\!\right]$ 。

消去法所執行的基本列運算 (elementary raw operation) 不改變線性方程的解，因此 $A\mathbf{x}=\mathbf{0}$ 等價於 $R\mathbf{x}=\mathbf{0}$ ，也就是說 $A$ 與 $R$ 有相同的零空間。下面是多數線性代數教科書採用的解法。令欲解出的未知變數為 $\mathbf{x}=(x_1,\ldots,x_6)^T$ ，寫出係數矩陣 $R$ 所對應的齊次方程組：

$\displaystyle\begin{aligned} x_1+4x_2+x_4-3x_5=0~~&\Rightarrow~~x_1=-4x_2-x_4+3x_5\\ x_3-x_4+2x_5=0~~&\Rightarrow~~x_3=x_4-2x_5\\ x_6=0~~&\end{aligned}$

在方程組中，等號左邊的領先變數 $x_1, x_3, x_6$ 稱為軸變數 (pivot variable)，等號右邊的 $x_2, x_4,x_5$ 稱為自由變數 (free variable)。每個軸變數都被一個方程式鎖定，自由變數則不受方程式約束。設 $x_2=\alpha$ ， $x_4=\beta$ ， $x_5=\gamma$ ，其中 $\alpha,\beta,\gamma$ 代表任意數。齊次方程 $R\mathbf{x}=\mathbf{0}$ 的完整解可表示為三個特解 (special solution) 的線性組合：

$\displaystyle \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6 \end{bmatrix}=\begin{bmatrix} -4\alpha-\beta+3\gamma\\ \alpha\\ \beta-2\gamma\\ \beta\\ \gamma\\ 0 \end{bmatrix}=\alpha\left[\!\!\begin{array}{r} -4\\ 1\\ 0\\ 0\\ 0\\ 0 \end{array}\!\!\right]+\beta\left[\!\!\begin{array}{r} -1\\ 0\\ 1\\ 1\\ 0\\ 0 \end{array}\!\!\right]+\gamma\left[\!\!\begin{array}{r} 3\\ 0\\ -2\\ 0\\ 1\\ 0 \end{array}\!\!\right]=\alpha\mathbf{p}_1+\beta\mathbf{p}_2+\gamma\mathbf{p}_3$ ，

其中特解 $\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3$ 滿足 $R\mathbf{p}_i=\mathbf{0}$ 。因此， $N(A)=N(R)=\text{span}\{\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3\}$ 。齊次方程 $A\mathbf{x}=\mathbf{0}$ 的每一特解 $\mathbf{p}_i$ 對應一個自由變數，即知 $\{\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3\}$ 是線性獨立的，也就是說，所有的特解構成零空間 $N(A)$ 的一組基底。將特解 $\mathbf{p}_1,\mathbf{p}_2,\mathbf{p}_3$ 合併為一個矩陣，

$\displaystyle P=\begin{bmatrix} \mathbf{p}_1&\mathbf{p}_2&\mathbf{p}_3 \end{bmatrix}=\left[\!\!\begin{array}{rrr} -4 & -1&3 \\ 1&0&0\\ 0 & 1&-2 \\ 0 & 1 &0\\ 0 & 0&1 \\ 0 & 0&0 \end{array}\!\!\right]$ 。

因為 $A\mathbf{p}_i=\mathbf{0}$ ，即 $AP=0$ ，且 $\hbox{rank}P=\dim N(A)$ ，可知 $P$ 的行空間 (column space) 就是 $A$ 的零空間，記作 $C(P)=N(A)$ 。我們稱 $P$ 是 $A$ 的零空間矩陣 (nullspace matrix)。下面介紹兩個不須經過解齊次方程 $R\mathbf{x}=\mathbf{0}$ 過程，直接從簡約列梯形式 $R$ 推得零空間矩陣 $P$ 的算法。

算法 1

上例中，若不考慮 $R$ 的零列與 $P$ 的自由變數列 (即第 2，4，5 列)， $R$ 的非軸行 (對應軸變數的行，即第 2，4，5 行)，除了正負號相反，恰好等於 $P$ 的三個行向量：

$R=\left[\!\!\begin{array}{cccrrc} * & 4 & * &1& -3 & * \\ * & 0 & * &-1& 2 & * \\ * & 0 & * &0& 0 & * \\ * & * & * &*& * & * \end{array}\!\!\right],~~P=\left[\!\!\begin{array}{rrr} -4 & -1&3 \\ *&*&*\\ 0 & 1&-2 \\ *&*&*\\ *&*&*\\ 0 & 0&0 \end{array}\!\!\right]$ 。

這個現象純屬巧合，還是必然如此？令 $r$ 表示 $R$ 的軸行數，非軸行數則為 $n-r$ (非軸行對應自由變數)。為方便說明，設想你將 $m\times n$ 階 $R$ 矩陣的軸行置於最左邊， $n\times (n-r)$ 階 $P$ 矩陣對應自由變數的列置於最底下，就有下面的分塊矩陣形式：

$\displaystyle R=\begin{bmatrix} I_r & F \\ 0 & 0 \end{bmatrix},~ P=\begin{bmatrix} -F \\ I_{n-r} \end{bmatrix}$ ，

其中 $F$ 是 $r\times(n-r)$ 階分塊。直接計算可確認上式恆真：

$\displaystyle RP=\begin{bmatrix} I_r & F \\ 0 & 0 \end{bmatrix} \begin{bmatrix} -F \\ I_{n-r} \end{bmatrix}=\begin{bmatrix} -F+F \\ 0 \end{bmatrix}=0$ 。

從簡約列梯形式 $R$ 的分塊矩陣表達立刻可讀出 $P$ ，步驟如下：

觀察可知 $R$ 有3個非軸行：2，4，5，故 $P$ 是 $6\times 3$ 階矩陣。
將 $I_3$ 填入 $P$ 的第2，4，5列 (填入數字以底線加註)：

$\displaystyle P=\left[\!\!\begin{array}{rrr} & & \\ \underline{1}&\underline{0}&\underline{0}\\ & & \\ \underline{0}&\underline{1}&\underline{0}\\ \underline{0}&\underline{0}&\underline{1}\\ & & \end{array}\!\!\right]$ 。
變更 $R$ 的非軸行正負號 (即 $-F$ )，從上往下依序填入 $P$ 的空白列，填滿為止：

$\displaystyle P=\left[\!\!\begin{array}{rrr} \underline{-4} & \underline{-1}&\underline{3} \\ 1&0&0\\ \underline{0} & \underline{1}&\underline{-2} \\ 0 & 1 &0\\ 0 & 0&1 \\ \underline{0} & \underline{0}&\underline{0} \end{array}\!\!\right]$ 。

算法 2

我們仍用上例說明。透過增加或刪除零列，將簡約列梯形式 $R$ 改寫成 $n\times n$ 階上三角矩陣 $U$ 使得所有的軸元都位於主對角線，如下：

$\displaystyle U=\left[\!\!\begin{array}{cccrrc} 1 & 4 & 0 &1& -3 & 0 \\ 0&0&0&0&0&0\\ 0 & 0 & 1 &-1& 2 & 0 \\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0 & 0 & 0 &0& 0 & 1 \end{array}\!\!\right]$ 。

明顯地，增刪零列不改變 $R$ 的零空間， $N(R)=N(U)$ 。現在問題轉變為尋找 $U$ 的零空間。令 $U=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_6 \end{bmatrix}$ 。矩陣 $U$ 的軸行1，3，6為標準單位向量，即 $\mathbf{u}_1=\mathbf{e}_1$ ， $\mathbf{u}_3=\mathbf{e}_3$ ， $\mathbf{u}_6=\mathbf{e}_6$ ；非軸行2，4，5是軸行的線性組合， $\mathbf{u}_2=4\mathbf{e}_1$ ， $\mathbf{u}_4=\mathbf{e}_1-\mathbf{e}_3$ ， $\mathbf{u}_5=-3\mathbf{e}_1+2\mathbf{e}_3$ 。因此，

$\displaystyle\begin{aligned} U\mathbf{u}_i&=U\mathbf{e}_i=\mathbf{e}_i=\mathbf{u}_i,~~i=1,3,6\\ U\mathbf{u}_2&=U(4\mathbf{e}_1)=4U\mathbf{e}_1=4\mathbf{e}_1=\mathbf{u}_2\\ U\mathbf{u}_4&=U(\mathbf{e}_1-\mathbf{e}_3)=U\mathbf{e}_1-U\mathbf{e}_3=\mathbf{e}_1-\mathbf{e}_3=\mathbf{u}_4\\ U\mathbf{u}_5&=U(-3\mathbf{e}_1+2\mathbf{e}_3)=-3U\mathbf{e}_1+2U\mathbf{e}_3=-3\mathbf{e}_1+2\mathbf{e}_3=\mathbf{u}_5. \end{aligned}$

使用上面結果，

$\displaystyle U^2=U\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_6 \end{bmatrix}=\begin{bmatrix} U\mathbf{u}_1&\cdots &U\mathbf{u}_6 \end{bmatrix}=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_6 \end{bmatrix}=U$ ，

也就是說， $U(I-U)=0$ ，因此 $C(I-U)\subset N(U)$ 。寫出

$\displaystyle I-U=\left[\!\!\begin{array}{crcrrc} 0 & -4 & 0 &-1& 3 & 0 \\ 0&1&0&0&0&0\\ 0 & 0 & 0 &1& -2 & 0 \\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0 & 0 & 0 &0& 0 & 0 \end{array}\!\!\right]$ 。

觀察可知 $\dim C(I-U)=n-r$ ，故 $C(I-U)=N(U)$ 且 $I-U$ 的非零行向量組成零空間矩陣 $P$ 。

13 Responses to 零空間的快捷算法

陳恩號 says:

05/15/2016 at 1:43 pm

老師你好
像上面題目一開始是一個4×6的a矩陣
後來找到出一組基底形成6×3的p矩陣
ap=0

那假如我是3×3 或2×2 這種方形矩陣
有可能算出來的基底形成的矩陣是3×3 或2×2嗎
還是不可能是 square matrix

陳恩號 says:

05/15/2016 at 3:01 pm

假如矩陣=
147
258
367
運用高斯消去法化簡 A得到簡約列梯形式
1 0 -1
0 1 2
0 0 -2
x1-x3=0
x2+2×3=0
-2×3=0
設x3=g
x1 1
x2 = g* -2
x3 1

147 1 0
258 * -2 不等於 0
367 1 0

請問哪裡有算錯 ?
謝謝老師

- 陳恩號 says:
  
  05/15/2016 at 3:02 pm
  
  排版歪了 ..
  
- ccjou says:
  
  05/15/2016 at 4:00 pm
  
  你寫的方陣是可逆的，簡約列梯形式是單位矩陣I。我的blog沒有助教，往後煩請你自己檢查計算步驟，或多利用網路計算器
  http://www.bluebit.gr/matrix-calculator/
  
陳恩號 says:

05/16/2016 at 2:02 am

老師可以舉一個可逆的例子嗎
我想了好久還是想不通..
謝謝老師

路人 says:

05/16/2016 at 11:46 am

樓上同學
可逆的話只能找到唯一解
應該找不到相乘等於0的矩陣

老師不知道我這樣說對不對

- ccjou says:
  
  05/16/2016 at 11:59 am
  
  謝謝，你說的正確。設 $AB=0$ 。
  若 $A$ 可逆，則 $A^{-1}AB=0$ ，即 $B=0$ 。
  若 $A$ 不可逆，很多方法可找出非零矩陣 $B$ 使得 $AB=0$ ，譬如下文的證明2：
  https://ccjou.wordpress.com/2015/08/03/%E6%AF%8F%E9%80%B1%E5%95%8F%E9%A1%8C-august-3-2015/
  
路人2 says:

05/16/2016 at 1:48 pm

之前我也是這樣和同學說
可逆的話只能找到唯一解(我的第一反應)
但他問我為什麼

我該怎麼和她說比較有說服力
老師有哪篇文章可以參考嗎
謝謝

- ccjou says:
  
  05/16/2016 at 3:32 pm
  
  可逆矩陣定理
  https://ccjou.wordpress.com/2010/03/12/%E5%8F%AF%E9%80%86%E7%9F%A9%E9%99%A3%E5%AE%9A%E7%90%86/
  實戰演練
  https://ccjou.wordpress.com/2012/11/05/%E5%8F%AF%E9%80%86%E7%9F%A9%E9%99%A3%E5%AE%9A%E7%90%86%E4%B9%8B%E5%AF%A6%E6%88%B0%E6%BC%94%E7%B7%B4/
  
路人2 says:

05/16/2016 at 1:54 pm

或著說只要說明哪幾點
就可以讓他清楚明白

xinyunliu2000 says:

03/10/2017 at 12:51 am

”因為 AP=0 且 \hbox{rank}P=\dim N(A)，可知 P 的行空間 (column space) 即為 A 的零空間“。
不明白为什么有AP=0

- ccjou says:
  
  03/10/2017 at 5:29 am
  
  我將這一段前後修增說明文字。因為 $A\mathbf{p}_i=\mathbf{0}$ ，可知 $AP=A\begin{bmatrix} \mathbf{p}_1&\mathbf{p}_2&\mathbf{p}_3 \end{bmatrix}=0$ 。
  
劉信傑 says:

05/13/2019 at 11:55 am

老師好， P1 P2 P3 讓RP=0 是不是應該稱為齊次解?

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