Maximum numbers of underdetermined solution of $Ax=b$ Given $m \times n$ real matrix $A$, where $m<n$, 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)
 A: 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.)
A: 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$
A: 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
