每週問題 May 30, 2016

Posted on 05/30/2016 by ccjou

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

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}

Advertisement
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:

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s