子空間之和與交集的算法

本文的閱讀等級:初級

給定 \mathbb{R}^n 中任兩個子空間 \mathcal{X}\mathcal{Y},如何計算子空間和 \mathcal{X}+\mathcal{Y} 與子空間交集 \mathcal{X}\cap\mathcal{Y}?子空間有兩種常用的描述方式:一是建構式,例如矩陣的行空間 (column space) 是行向量的生成 (span);二是限制式,例如矩陣的零空間 (nullspace) 是矩陣所表示的齊次方程的解集合。本文介紹針對這兩種描述方式的子空間和與交集的演算法,往下閱讀之前,讀者務必先掌握建構式與限制式的轉換技術 (見“行空間與零空間的互換表達”)。

 
子空間 \mathcal{X}\mathcal{Y} 之和定義如下:

\mathcal{X}+\mathcal{Y}\overset{\underset{\mathrm{def}}{}}{=}\{\mathbf{x}+\mathbf{y}\vert\mathbf{x}\in\mathcal{X}, \mathbf{y}\in\mathcal{Y}\}

很容易確認 \mathcal{X}+\mathcal{Y} 也是 \mathbb{R}^n 的一個子空間 (見“補子空間與直和”)。若 \mathcal{X}\mathcal{Y} 分別以建構式表示為 \mathcal{X}=\mathrm{span}\{\mathbf{x}_1,\ldots,\mathbf{x}_p\}\mathcal{Y}=\mathrm{span}\{\mathbf{y}_1,\ldots,\mathbf{y}_q\},子空間和即為 \{\mathbf{x}_i\}\{\mathbf{y}_j\} 聯集的生成:

\mathcal{X}+\mathcal{Y}=\mathrm{span}\{\mathbf{x}_1,\ldots,\mathbf{x}_p,\mathbf{y}_1,\ldots,\mathbf{y}_q\}

我們知道矩陣的行向量生成行空間,所以 \mathcal{X}\mathcal{Y} 也可以用矩陣行空間來表示。令 X=\begin{bmatrix}    \mathbf{x}_1&\cdots&\mathbf{x}_p    \end{bmatrix}Y=\begin{bmatrix}    \mathbf{y}_1&\cdots&\mathbf{y}_q    \end{bmatrix},就有 \mathcal{X}=C(X)\mathcal{Y}=C(Y)\mathcal{X}+\mathcal{Y} 則為分塊矩陣 \begin{bmatrix}    X&Y    \end{bmatrix} 的行空間,即

\mathcal{X}+\mathcal{Y}=C\left(\begin{bmatrix}    X&Y    \end{bmatrix}\right)

使用矩陣行空間表達子空間的好處是立刻能夠判斷子空間的包容關係。因為 C(X)\subseteq C\left(\begin{bmatrix}    X&Y    \end{bmatrix}\right)C(Y)\subseteq C\left(\begin{bmatrix}    X&Y    \end{bmatrix}\right),由此可推論 \mathcal{X}\subseteq\mathcal{X}+\mathcal{Y}\mathcal{Y}\subseteq\mathcal{X}+\mathcal{Y}

 
如果給出的子空間以限制式描述,亦即矩陣零空間,那該如何計算子空間和?用一個例子來說明,考慮 \mathcal{X}=N(A)\mathcal{Y}=N(B),其中

A=\left[\!\!\begin{array}{crcr}    1 & -1 & 1 & -1 \\    2 & -1 & 3 & -4 \\    0 & 1 & 1 & -2    \end{array}\!\!\right],~~~B=\left[\!\!\begin{array}{crcr}    1 & 0 & 2 & -3 \\    1 & 0 & 0 & 0 \\    3 & -2 & 4 & -5    \end{array}\!\!\right]

最直接的作法是解出零空間 N(A)N(B),並改以建構式表示:求出矩陣 XY 使得 N(A)=C(X)N(B)=C(Y),下面詳述計算過程。

(1) 分別將 AB 化簡至簡約列梯形式:

A\to\left[\!\!\begin{array}{cccr}    1 & 0 & 2 & -3 \\    0 & 1 & 1 & -2 \\    0 & 0 & 0 & 0    \end{array}\!\!\right],~B\to\left[\!\!\begin{array}{cccr}    1 & 0 & 0 & 0 \\    0 & 1 & 0 & -\frac{1}{2} \\[0.3em]    0 & 0 & 1 & -\frac{3}{2}    \end{array}\!\!\right]

(2) 寫出對應 AB 的簡約列梯形式的零空間矩陣 XY,滿足 AX=0BY=0,如下:

X=\left[\!\!\begin{array}{rc}    -2 & 3 \\    -1 & 2 \\    1 & 0 \\    0 & 1    \end{array}\!\!\right],~~~Y=\left[\!\!\begin{array}{c}    0 \\    \frac{1}{2} \\[0.3em]    \frac{3}{2} \\    1    \end{array}\!\!\right]

由此得知 \mathrm{dim}N(A)=\mathrm{rank}X=2\mathrm{dim}N(B)=\mathrm{rank}Y=1

(3) 子空間 \mathcal{X}+\mathcal{Y}XY 的行向量共同生成,即

\mathcal{X}+\mathcal{Y}=\mathrm{span}\left\{\left[\!\!\begin{array}{r}    -2\\    -1\\    1\\    0    \end{array}\!\!\right],\begin{bmatrix}    3\\    2\\    0\\    1    \end{bmatrix},\left[\!\!\begin{array}{c}    0\\    \frac{1}{2} \\[0.3em]    \frac{3}{2} \\    1    \end{array}\!\!\right]\right\}

 
子空間交集不像子空間和具有視覺化的建構意象,我們可以想像「逆向操作」,假設已知子空間交集,然後往回問它是哪些子空間的交集。考慮齊次方程式 A\mathbf{x}=\mathbf{0},如下:

\left[\!\!\begin{array}{crc}    2 & -1 & 1 \\    1 & 3 & 2    \end{array}\!\!\right]\begin{bmatrix}    x_1 \\    x_2 \\    x_3    \end{bmatrix}=\begin{bmatrix}    0 \\    0    \end{bmatrix}

矩陣 A 的零空間 N(A)A\mathbf{x}=\mathbf{0} 的所有解構成, 故同時滿足 2 個方程式:

\begin{aligned}  2x_1-x_2+x_3&=0\\  x_1+3x_2+2x_3&=0.\end{aligned}

換句話說,N(A) 即為這兩個方程式解的交集。從幾何面來解釋,上面兩個方程式的解分別是 \mathbb{R}^3 空間的兩個平面,而此兩平面的交集則為一條穿越原點直線,這也說明了子空間交集也是一個子空間。推廣至一般情況,若子空間 \mathcal{X}\mathcal{Y} 以限制式表示為 \mathcal{X}=N(A)\mathcal{Y}=N(B),則 \mathcal{X}\cap\mathcal{Y} 中任一向量 \mathbf{x} 必同時滿足 A\mathbf{x}=\mathbf{0}B\mathbf{x}=\mathbf{0},合併兩式可得 \begin{bmatrix}    A \\    B    \end{bmatrix}\mathbf{x}=\mathbf{0},子空間交集 \mathcal{X}\cap\mathcal{Y} 即為分塊矩陣 \begin{bmatrix}    A \\    B    \end{bmatrix} 的零空間:

\mathcal{X}\cap\mathcal{Y}=N\left(\begin{bmatrix}    A \\    B    \end{bmatrix}\right)

 
若給出的子空間以矩陣行空間表示,\mathcal{X}=C(X)\mathcal{Y}=C(Y),如下例,

X=\begin{bmatrix}    1&1&0\\    1&2&0\\    2&0&1\\    1&1&0    \end{bmatrix},~Y=\begin{bmatrix}    2&0&3\\    3&1&6\\    4&0&7\\    2&1&5    \end{bmatrix}

我們可以先將個別行空間轉換為另一個矩陣的零空間,亦即求矩陣 AB 使得 C(X)=N(A)C(Y)=N(B),然後再解 \begin{bmatrix}    A\\    B    \end{bmatrix} 的零空間,過程如下。

(1) 分別將 X^TY^T 化簡至簡約列梯形式:

X^T\to\begin{bmatrix}    1&0&0&1\\    0&1&0&0\\    0&0&1&0    \end{bmatrix},~Y^T\to\left[\!\!\begin{array}{cccr}    1&0&0&-\frac{3}{2}\\    0&1&0&1\\    0&0&1&\frac{1}{2}    \end{array}\!\!\right]

(2) 寫出對應 X^TY^T 的零空間矩陣,AB 即為零空間矩陣的轉置:

A=\begin{bmatrix}    -1&0&0&1    \end{bmatrix},~B=\begin{bmatrix}    \frac{3}{2}&-1&-\frac{1}{2}&1    \end{bmatrix}

注意,AB 滿足 AX=0BY=0

(3) 最後將 \begin{bmatrix}    A\\    B    \end{bmatrix} 至簡約列梯形式:

\begin{bmatrix}    A\\    B    \end{bmatrix}=\left[\!\!\begin{array}{rrrc}    -1&0&0&1\\    \frac{3}{2}&-1&-\frac{1}{2}&1    \end{array}\!\!\right]\to\left[\!\!\begin{array}{cccr}    1&0&0&-1\\    0&1&\frac{1}{2}&-\frac{5}{2}    \end{array}\!\!\right]

由上面的簡約列梯形式即得零空間矩陣,亦即 P 滿足 \begin{bmatrix}    A\\    B    \end{bmatrix}P=0,解得

P=\left[\!\!\begin{array}{rc}    0&1\\    -\frac{1}{2}&\frac{5}{2}\\    1&0\\    0&1    \end{array}\!\!\right]

子空間交集 \mathcal{X}\cap\mathcal{Y}P 的行向量生成,

\mathcal{X}\cap\mathcal{Y}=\mathrm{span}\left\{\left[\!\!\begin{array}{r}    0\\    -\frac{1}{2}\\    1\\    0    \end{array}\!\!\right],\left[\!\!\begin{array}{c}    1\\    \frac{5}{2}\\    0\\    1    \end{array}\!\!\right]\right\}

 
下面補充另一個較便捷的子空間交集算法 (見“每週問題 September 14, 2009”)。若 \mathbf{w}\in\mathcal{X}\cap\mathcal{Y},則 \mathbf{w} 不僅可表示為 X=\begin{bmatrix}    \mathbf{x}_1&\cdots&\mathbf{x}_p    \end{bmatrix} 的行向量線性組合,也可表示為 Y=\begin{bmatrix}    \mathbf{y}_1&\cdots&\mathbf{y}_q    \end{bmatrix} 的行向量線性組合,故設

\mathbf{w}=c_1\mathbf{x}_1+\cdots+c_p\mathbf{x}_p=d_1\mathbf{y}_1+\cdots+d_q\mathbf{y}_q

將上式改寫成

c_1\mathbf{x}_1+\cdots+c_p\mathbf{x}_p-d_1\mathbf{y}_1-\cdots-d_q\mathbf{y}_q=\mathbf{0}

\mathbf{c}=(c_1,\ldots,c_p)^T\mathbf{d}=(d_1,\ldots,d_q)^T,只要解出齊次方程

\begin{bmatrix}    X&-Y    \end{bmatrix}\begin{bmatrix}    \mathbf{c}\\    \mathbf{d}    \end{bmatrix}=\mathbf{0}

從其中抽出 \mathbf{x}_i 的係數 c_i (或 \mathbf{y}_j 的係數 d_j), \mathcal{X}\cap\mathcal{Y} 就是所有 X\mathbf{c} (或 Y\mathbf{d}) 的生成。用前例展示計算過程:

(1) 先將 \begin{bmatrix}    X&-Y    \end{bmatrix} 化簡至簡約列梯形式:

\begin{bmatrix}    X&-Y    \end{bmatrix}\to\left[\!\!\begin{array}{cccrcr}    1&0&0&-1&0&-2\\    0&1&0&-1&0&-1\\    0&0&1&-2&0&-3\\    0&0&0&0&1&2    \end{array}\!\!\right]

(2) 寫出 \begin{bmatrix}    X&-Y    \end{bmatrix} 的零空間矩陣:

P=\left[\!\!\begin{array}{cr}    1&2\\    1&1\\    2&3\\    1&0\\    0&-2\\    0&1    \end{array}\!\!\right]

從中抽出線性組合係數 \mathbf{c}\in\mathrm{span}\left\{\begin{bmatrix}    1\\    1\\    2    \end{bmatrix},\begin{bmatrix}    2\\    1\\    3    \end{bmatrix}\right\}

(3) 子空間交集 \mathcal{X}\cap\mathcal{Y} 由下列兩向量生成:

\begin{bmatrix}    1&1&0\\    1&2&0\\    2&0&1\\    1&1&0    \end{bmatrix}\begin{bmatrix}    1\\    1\\    2    \end{bmatrix}=\begin{bmatrix}    2\\    3\\    4\\    2    \end{bmatrix}

\begin{bmatrix}    1&1&0\\    1&2&0\\    2&0&1\\    1&1&0    \end{bmatrix}\begin{bmatrix}    2\\    1\\    3    \end{bmatrix}=\begin{bmatrix}    3\\    4\\    7\\    3    \end{bmatrix}

與前面結果比較,不難確認

\mathrm{span}\left\{\left[\!\!\begin{array}{r}    0\\    -\frac{1}{2}\\    1\\    0    \end{array}\!\!\right],\left[\!\!\begin{array}{c}    1\\    \frac{5}{2}\\    0\\    1    \end{array}\!\!\right]\right\}=\mathrm{span}\left\{\begin{bmatrix}    2\\    3\\    4\\    2    \end{bmatrix},\begin{bmatrix}    3\\    4\\    7\\    3    \end{bmatrix}\right\}

This entry was posted in 線性代數專欄, 向量空間 and tagged , , , . Bookmark the permalink.

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s