1
$\begingroup$

Given $m \times n$ real matrix $A$, where $m, we know that the nullity of $A$ is the dimension of the kernel $W=\{w| Aw=0\}$. Also all solutions of linear equation $Ax=b$ for $b\neq 0$ can be described as

$\mathcal{A}(v):=\{v+w | Aw=0\}=v+W$ where $v$ satisfies $Av=b$.

Does the maximum size of linearly independent set in $\mathcal{A}(v)$ always equal to $\dim W$?

in other words:

Does the maximum numbers of independent solutions of the underdetermined system $Ax=b$ always equal to the nullity of $A$?

I can only seeing this by plotting the solutions.

My idea seems naive:

Suppose that $\dim W=r$, and we have $r+1$-linearly independent vectors in $v+W$ say

$v+x_1,v+x_2,\cdots,v+x_{r+1}$

Can we prove that $x_1,x_2,\cdots,x_{r+1}$ are also linearly independent? (in order to get a contradiction)

  • 0
    (Duh to me: $v$, $v+w_1,\ldots,v+w_n$ are all elements of $\mathcal{A}(v)$, and as noted above they are linearly independent. But $0$, $w_1,\ldots,w_n$ are not linearly independent elements of $W$).2012-07-04

3 Answers 3

2

This is an answer to your question "Does the maximum size of linearly independent set in $\mathcal{A}(v)$ always equal to $\dim W$?".

Basically no. Take $A=\begin{bmatrix}1 & 0 & 0\\ 0 & 0 & 1\end{bmatrix}$ and $b=e_1$. Then $\ker A = \mathbb{sp} \{ e_2 \} $, and since $A e_1 = b$, we may take $v = e_1$. However $v+\ker A$ contains $e_1+e_2$ and $e_1-e_2$ which are linearly independent, whereas $\ker A$ has dimension $1$.

(Note however, that the affine dimension of $\mathcal{A}(v)$ always equals that of $\ker A$, as it is just a translate.)

  • 0
    Oops, I completely missed the m. I added a small fix.2012-07-04
2

There is confusion in your question about the use of "linearly independent". With the usual meaning of that term applied to elements of a vector space, namely "no nontrivial linear combination gives $0$", the answer to your question is negative: if $b\neq 0$ then $v\notin W$ and $v+W$ is an affine subspace of dimension $\dim W$, which contains linealrly independent sets of $1+\dim W$ elements, for instance $\{v,v+b_1,v+b_2,\ldots,v+b_d\}$ where $\{b_1,\ldots,b_d\}$ is a basis of $W$. As a concrete example take $A=(1~~1)$ and $b=1$ then you equation is $x+y=1$, the nullity of $A$ is $1$, but there are two solutions $(x,y)=(1,0)$ and $(x,y)=(0,1)$ that are linearly independent as vectors.

However you probably do not want to say these are two linearly independent solutions, since a linear combination of them will in general not be a solution. So you might want to define a set of solutions to be linealrly independent if after subtraction of a particular solution $v$ from all of them they become a linearly independent set of vectors. But then the answer to your question is trivially positive: after subtraction of $v$ from all the elements of $v+W$ one gets $W$, which is of course a vector subspace of dimension $\dim W$

  • 0
    I meant what you've mention in the first paragraph. I don't know how could I missed "$\{v,v+b_1,\cdots,v+b_r\}$ is always linearly independent" .. I've tried to claim/proved it before I post this question, with troubles. But It seems no trouble now: Let $\sum_{i=0}^{r} \alpha_i (v+ b_i) =0$, here $b_0=0$. Then $(\alpha_0+\cdots+\alpha_r)v+\alpha_1 b_1 + \cdots +\alpha_r b_r=0$ If $\alpha_0+\cdots+\alpha_r=0$, then $\alpha_i=0$ since $\{b-1,\cdots,b_r\}$ is a basis. If $\alpha_0+\cdots+\alpha_r\neq 0$ then $v \in W$.2012-07-04
0

OKay...... I'm not sure what you are trying to say by dim W. Do you mean ker A? Also when you say kernel $W=${$w | Aw=0$} I'm pretty sure you mean ker A.

review this: http://en.wikipedia.org/wiki/Kernel_of_a_matrix

Now to answer your linear independence question. Because you are assuming that $v+x_1,...v+x_{r+1}$ are linearly independent what does that mean?

It means:

$\displaystyle \sum_{i=1}^{r+1} a_i(v +x_i) = 0$ if and only if every $a_i=0$. But what is this?

$\displaystyle 0 = \sum_{i=1}^{r+1} a_i(v +x_i) = \sum_{i=1}^{r+1} a_iv + \sum_{i=1}^{r+1} a_ix_i$ We required the $a_i$ to all be identically zero, and so it follows that:

$\displaystyle \sum_{i=1}^{r+1} a_ix_i = 0$

And hence $x_1,...x_{r+1}$ are linearly independent... but again, I'm not really sure what this part has to do with your general question.... could you elaborate, please?

I suppose there would be some for of contradiction if $x_i \in $ ker($A$), as you are assuming $dim(ker(A))=r$. But I'm not sure what you are looking for... sorry

  • 0
    tha t is to say: "we can't have more than $r$ linearly independent vectors in $\mathcal{A}(v)$"2012-07-04