每週問題 May 30, 2016

一個線性方程的解集合所包含的最大線性獨立向量數是多少?

Let A be an m\times n matrix and S be the solution set for a consistent system of linear equations A\mathbf{x}=\mathbf{b} for some \mathbf{b}\neq\mathbf{0}.

(a) If S_{\max} is a maximal independent subset of S and \mathbf{x}_p is any particular solution, show that

\hbox{span}(S_{\max})=\hbox{span}\{\mathbf{x}_p\}+N(A),

where N(A) denotes the nullspace of A.

(b) If \hbox{rank}A=r, show that A\mathbf{x}=\mathbf{b} has at most n-r+1 independent solutions.

 
參考解答:

(a) 假設 S_{\max}=\{\mathbf{y}_1,\ldots,\mathbf{y}_k\}。我們先證明 \hbox{span}(S_{\max})\subseteq\hbox{span}\{\mathbf{x}_p\}+N(A)。因為 \mathbf{y}_i\in S,即 A\mathbf{y}_i=\mathbf{b},存在 \mathbf{n}_i\in N(A) 使得 \mathbf{y}_i=\mathbf{x}_p+\mathbf{n}_i。因此,對於任意 \mathbf{x}\in \hbox{span}(S_{\max})

\displaystyle \mathbf{x}=\sum_{i=1}^kc_i\mathbf{y}_i=\sum_{i=1}^kc_i(\mathbf{x}_p+\mathbf{n}_i)=\left(\sum_{i=1}^kc_i\right)\mathbf{x}_p+\sum_{i=1}^kc_i\mathbf{n}_i

亦即 \mathbf{x}\in\hbox{span}\{\mathbf{x}_p\}+N(A)。欲證明 \hbox{span}\{\mathbf{x}_p\}+N(A)\subseteq \hbox{span}(S_{\max}),我們需要這個性質:若 \mathbf{x}\neq\mathbf{0}\mathbf{x}\in S,則 \mathbf{x}\in\hbox{span}(S_{\max})。原因如下:假設 \mathbf{x}\notin \hbox{span}(S_{\max}),則 \{\mathbf{x}\}\cup S_{\max} 是一個線性獨立集,這與 S_{\max} 是最大線性獨立集矛盾。對於 \mathbf{x}\in \hbox{span}\{\mathbf{x}_p\}+N(A),存在純量 c\mathbf{n}\in N(A) 使得

\displaystyle \mathbf{x}=c\mathbf{x}_p+\mathbf{n}=(c-1)\mathbf{x}_p+(\mathbf{x}_p+\mathbf{n})

但非零向量 \mathbf{x}_p\mathbf{x}_p+\mathbf{n} 屬於 S,兩向量皆屬於子空間 \hbox{span}(S_{\max})。根據封閉性,\mathbf{x}\in\hbox{span}(S_{\max})

(b) 線性獨立集 S_{\max}\hbox{span}(S_{\max}) 的一組基底。使用容斥定理與秩─零度定理,

\displaystyle \begin{aligned} k&=\dim \hbox{span}(S_{\max})=\dim\left(\hbox{span}\{\mathbf{x}_p\}+N(A)\right)\\ &=\dim\hbox{span}\{\mathbf{x}_p\}+\dim N(A)-\dim\left(\hbox{span}\{\mathbf{x}_p\}\cap N(A)\right)\\ &=1+n-r-0=n-r+1. \end{aligned}

Advertisements
This entry was posted in pow 向量空間, 每週問題 and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s