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

本文的閱讀等級：初級

令 $\mathcal{V}$ 為一個向量空間。給定向量集合 $S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}$ ， $\mathbf{v}_i\in\mathcal{V}$ ，若僅存在唯一的數組 $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$ ，本文探討底下三個問題：

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

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

將向量集 $S$ 以 $m\times n$ 階矩陣表示，如下：

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

$S=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}$ 是一個線性獨立集等價於下列陳述 (充要條件)：

矩陣 $A$ 的零空間 (nullspace) 僅含零向量，記為 $N(A)=\{\mathbf{0}\}$ 。
矩陣 $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$ 即為矩陣的行數。
交互乘積或稱 Gramian 矩陣 $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}$ 。比較 $A$ 和 $A^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}_j$ ， $j=1,\ldots,n$ 。我們可以證明 $A$ 與 $B$ 具有相同的行向量線性關係。因為 $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$ ，也就證明 $A$ 與 $B$ 有相同的行向量線性關係。既然如此， $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\}$

寫出向量集 $S$ 的 $3\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}_j$ ， $1\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$ 的一組基底。

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

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

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

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

Share this:

Like this:

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱