每週問題 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$

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

(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}