線性獨立向量集的判定與算法

本文的閱讀等級:初級

\mathcal{V} 為一個向量空間。給定 \mathcal{V} 的一個向量集合 S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\},若存在唯一數組 c_1=\cdots=c_n=0 使得

\displaystyle c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n=\mathbf{0}

我們稱 S 是線性獨立的或線性無關的 (linearly independent),否則稱之為線性相關的或線性相依的 (linearly dependent)。直白地說,線性獨立集不具有線性相關性,但線性相關集中至少有一個向量可表示為其餘向量的線性組合 (見“線性獨立俱樂部”)。假設 \dim\mathcal{V}=m\boldsymbol{\beta}=\{\mathbf{x}_1,\ldots,\mathbf{x}_m\}\mathcal{V} 的一組基底。任何一個向量 \mathbf{w}\in\mathcal{V} 與其參考基底 \boldsymbol{\beta} 的座標向量 [\mathbf{w}]_{\boldsymbol{\beta}} 有一對一的對應關係 (見“同構的向量空間”)。具體地說,若 \mathbf{w}=c_1\mathbf{x}_1+\cdots+c_m\mathbf{x}_m,則 [\mathbf{w}]_{\boldsymbol{\beta}}=(c_1,\ldots,c_m)。為裨益矩陣運算,我們可以將每一個 \mathbf{w}\in\mathcal{V} 用座標向量 [\mathbf{w}]_{\boldsymbol{\beta}} 表示。底下討論針對座標映射後的幾何向量空間 \mathbb{R}^m。如欲延伸至 \mathbb{C}^m,將轉置 (\cdot)^T 改成共軛轉置 (\cdot)^\ast 即可。

 
對於 S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\},其中 \mathbf{v}_i\in\mathbb{R}^m,本文探討下列三個問題:

  1. 如何判定 S 是否為一個線性獨立集?
  2. 如何從 S 挑選出最大的線性獨立子集?也就是說,該線性獨立子集包含最多的向量?
  3. 如何增添向量至 S 的最大線性獨立子集使之成為 \mathbb{R}^m 的一組基底?

 
問題 1. 給定 S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\},如何判定它是否為一個線性獨立集?

將向量集 Sm\times n 階矩陣表示如下:

\displaystyle A=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}

S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\} 是一個線性獨立集等價於下列陳述:

  1. 矩陣 A 的零空間 (nullspace) 僅含零向量,記為 N(A)=\{\mathbf{0}\}
  2. 矩陣 A 的行秩 (或列秩) 等於 n,即 \hbox{rank} A=\dim C(A)=\dim C(A^T)=n,其中 C(A) 表示 A 的行空間 (column space), C(A^T) 表示 A 的列空間 (row space)。這個情況稱為滿行秩 (full column rank),因為 n 即為矩陣的行數。
  3. 交互乘積 A^T A 是一個可逆矩陣,即 \det(A^T A)\neq 0

(1) 若 S 是線性獨立的,則

\displaystyle A\mathbf{x}=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}\begin{bmatrix} x_1\\ \vdots\\ x_n \end{bmatrix} =x_1\mathbf{v}_1+\cdots+x_n\mathbf{v}_n=\mathbf{0}

蘊含 x_1=\cdots=x_n=0,也就有 N(A)=\{\mathbf{0}\}。相反方向的推論也成立。

(2) 由 (1) \dim N(A)=0,利用秩─零度定理,\hbox{rank}A+\dim N(A)=n (見“線性代數基本定理 (一)”),立得 \hbox{rank}A=n

(3) 使用這個性質:A 的零空間等於 A^TA 的零空間。請注意,N(A)=N(A^TA) 等價於 N(A)\subseteq N(A^TA)N(A^TA)\subseteq N(A)。若 A\mathbf{x}=\mathbf{0},則 A^T A\mathbf{x}=A^T\mathbf{0}=\mathbf{0}。若 A^TA\mathbf{x}=\mathbf{0},則 \mathbf{x}^TA^TA\mathbf{x}=\left(A\mathbf{x}\right)^T\left(A\mathbf{x}\right)=\Vert A\mathbf{x}\Vert^2=0,故 A\mathbf{x}=\mathbf{0}。比較 AA^TA 的秩—零度定理表達式 \hbox{rank}A+\dim N(A)=n\hbox{rank}(A^TA)+\dim N(A^TA)=n,即得 \mathrm{rank}A=\mathrm{rank}(A^TA)。由 (2) 可知 \hbox{rank}(A^TA)=n,故 \det(A^TA)\neq 0。以上推論過程可反向進行。

 
例 1. 下列向量集是否線性獨立?

\displaystyle S=\left\{\begin{bmatrix} 1\\ 1\\ 1\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 1\\ 2 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 3\\ 4 \end{bmatrix}\right\}

基於前述線性獨立的等價性質,我們說明兩個算法:高斯消去法和行列式。寫出向量集 S 的矩陣表達:

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

(a) 高斯消去法:運用基本列運算將 4\times 3 階矩陣 A 化簡至梯形矩陣,如下:

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

最後一個矩陣顯示 3 個軸列 (pivot row,非零列),即知 \hbox{rank}A=3 (見“高斯消去法”,“利用行列式計算矩陣秩”),故 S 是線性獨立的。

(b) 行列式:計算 A^TA 的行列式,可得

\displaystyle \det(A^TA)=\left|\!\!\begin{array}{rrc} 4&6&10\\ 6&10&16\\ 10&16&30 \end{array}\!\!\right|=16\neq 0

故知 S 是線性獨立的。

 
問題 2. 給定 S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\},如何挑選出最大的線性獨立子集?

下面介紹一個採用高斯消去法的算法 (見“左乘還是右乘,這就是問題所在”)。令 A=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}P 為一個 m\times m 階可逆矩陣,且 B=\begin{bmatrix} \mathbf{b}_1&\cdots&\mathbf{b}_n \end{bmatrix}=PA。因此,

\displaystyle \begin{bmatrix}     \mathbf{b}_1&\cdots&\mathbf{b}_n     \end{bmatrix}=P\begin{bmatrix}     \mathbf{v}_1&\cdots&\mathbf{v}_n     \end{bmatrix}=\begin{bmatrix} P\mathbf{v}_1&\cdots&P\mathbf{v}_n \end{bmatrix}

上式可以想像為一組向量 \mathbf{v}_1,\ldots,\mathbf{v}_n 依序經過可逆線性變換 P 後分別映射至 \mathbf{b}_1,\ldots,\mathbf{b}_n,即 \mathbf{b}_j=P\mathbf{v}_jj=1,\ldots,n。下面證明 AB 具有相同的行向量線性關係。因為 A 的每一個行向量 \mathbf{v}_j 屬於行空間 C(A)\mathbf{v}_j 必定可以表示成所有行向量的線性組合,設為 \mathbf{v}_j=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n (但線性組合式未必是唯一的)。計算

\displaystyle P\mathbf{v}_j=P(c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n)=c_1P\mathbf{v}_1+\cdots+c_nP\mathbf{v}_n

上式等同於 \mathbf{b}_j=c_1\mathbf{b}_1+\cdots+c_n\mathbf{b}_n。相反方向的陳述也成立。若 \mathbf{b}_j=d_1\mathbf{b}_1+\cdots+d_n\mathbf{b}_n,等號兩邊同時左乘 P^{-1} 可得 \mathbf{v}_j=d_1\mathbf{v}_1+\cdots+d_n\mathbf{v}_n,也就證明 AB 有相同的行向量線性關係。既然如此,B 的線性獨立行向量指標和 A 的線性獨立行向量指標也就完全相同。

 
上述性質提示了一個從 S 挑選最大的線性獨立子集的算法。利用高斯消去法的基本列運算將 A 化簡至簡約列梯形式 (reduced row echelon form) R=\hbox{rref}(A),由 R 的外表形式立即可判讀行向量的線性關係:R 的所有軸行 (軸所在的行) 指標給出 A 的 (最多) 線性獨立行向量,而且 R 的非軸行數值給出該行向量以軸行表示的線性組合係數。我們用一個例子來說明。

 
例 2. 下列向量集的最大的線性獨立子集為何?

\displaystyle S=\left\{\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix},\begin{bmatrix} 4\\ 4\\ 4 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix},\begin{bmatrix} 5\\ 7\\ 9 \end{bmatrix}\right\}

寫出向量集 S3\times 4 階矩陣

\displaystyle A=\begin{bmatrix} 1&4&1&5\\ 1&4&2&7\\ 1&4&3&9 \end{bmatrix}

因為 \hbox{rank}A\le 3,可知 S 是一線性相關集。以基本列運算將 A 化簡至簡約列梯形式:

\displaystyle \begin{bmatrix} 1&4&1&5\\ 1&4&2&7\\ 1&4&3&9 \end{bmatrix}\to\begin{bmatrix} 1&4&0&3\\ 0&0&1&2\\ 0&0&0&0 \end{bmatrix}=R

R 的行向量為 \mathbf{r}_j1\le j\le 4。觀察可知 \mathbf{r}_1\mathbf{r}_3 是軸行,也就是說,S 的最大線性獨立子集由 1,3 行組成,即

\displaystyle \left\{\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix}\right\}

表明 \hbox{span}\{S\} 的維數等於 2。另外,R 的非軸行和軸行具有線性關係:

\displaystyle\begin{aligned} \mathbf{r}_2&=4\mathbf{r}_1\\ \mathbf{r}_4&=3\mathbf{r}_1+2\mathbf{r}_3 ,\end{aligned}

這說明 A 的對應行向量也有相同的線性關係:

\displaystyle\begin{aligned} \begin{bmatrix} 4\\ 4\\ 4 \end{bmatrix}&=4\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}\\ \begin{bmatrix} 5\\ 7\\ 9 \end{bmatrix}&=3\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}+2\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix}.\end{aligned}

 
問題 3. 如何增添向量至 S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\} 的最大線性獨立子集使之成為 \mathbb{R}^m 的一組基底?

問題 2 的算法稍作修改即可。將給定的向量集 S 擴充為 S'=\{\mathbf{v}_1,\ldots,\mathbf{v}_n,\mathbf{e}_1,\ldots,\mathbf{e}_m\},其中 \mathbf{e}_i\mathbb{R}^m 的第 i 個標準單位向量 (第 i 元為 1,其餘元為 0)。寫出增廣矩陣

\displaystyle [A\vert I_m]=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n\vert\mathbf{e}_1&\cdots&\mathbf{e}_m \end{bmatrix}

以基本列運算將 [A\vert I] 化簡至梯形矩陣 (不需要化簡至簡約列梯形式),其中軸行包含 A 的 (最多) 線性獨立行向量,以及新加入的標準單位向量,合併兩組向量即構成 \mathbb{R}^m 的一組基底。這個過程稱為 Steinitz 替換原則 (substitution principle),因為我們將 \mathbb{R}^m 的部分標準單位向量替換為 S 的最大線性獨立子集。

 
例 3. 如何增添向量至下列向量集的最大的線性獨立子集使之成為 \mathbb{R}^3 的一組基底?

\displaystyle S=\left\{\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix},\begin{bmatrix} 4\\ 4\\ 4 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix},\begin{bmatrix} 5\\ 7\\ 9 \end{bmatrix}\right\}

考慮增廣矩陣

\displaystyle [A\vert I]=\begin{bmatrix} 1&4&1&5&\vline&1&0&0\\ 1&4&2&7&\vline&0&1&0\\ 1&4&3&9&\vline&0&0&1 \end{bmatrix}

使用基本列運算將 [A\vert I] 化簡至梯形矩陣,如下:

\displaystyle \begin{bmatrix} 1&4&1&5&\vline&1&0&0\\ 1&4&2&7&\vline&0&1&0\\ 1&4&3&9&\vline&0&0&1 \end{bmatrix}\to\left[\!\!\begin{array}{cccccrrc} 1&4&1&5&\vline&1&0&0\\ 0&0&1&2&\vline&-1&1&0\\ 0&0&0&0&\vline&1&-2&1 \end{array}\!\!\right]

從梯形矩陣可知第 1, 3, 5 行是軸行,也就是說,

\displaystyle \left\{\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix},\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}\right\}

構成 \mathbb{R}^3 的一組基底。

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s