零空間的快捷算法

本文的閱讀等級:初級

A 為一個 m\times n 階矩陣。齊次方程 A\mathbf{x}=\mathbf{0} 的所有解形成的集合稱為零空間 (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},也就是說 AR 有相同的零空間。下面是多數線性代數教科書採用的解法。令欲解出的未知變數為 \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=\alphax_4=\betax_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)。我們稱 PA 的零空間矩陣 (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 nR 矩陣的軸行置於最左邊,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}

其中 Fr\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,步驟如下:

  1. 觀察可知 R 有3個非軸行:2,4,5,故 P6\times 3 階矩陣。
  2. 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]

  3. 變更 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

相關閱讀:
Advertisements
本篇發表於 線性代數專欄, 向量空間 並標籤為 , , , 。將永久鏈結加入書籤。

12 則回應給 零空間的快捷算法

  1. 陳恩號 說道:

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

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

  2. 陳恩號 說道:

    假如矩陣=
    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

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

  3. 陳恩號 說道:

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

  4. 路人 說道:

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

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

  5. 路人2 說道:

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

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

  6. 路人2 說道:

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

  7. xinyunliu2000 說道:

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s