Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
It is easy to see that the maximum number of linearly independent vectors in $\mathcal{A}(v)$ is at least $\dim(W)$: if $w_1,\ldots,w_n$ are linearly independent, and $v$ is not in their span, then $w_1,\ldots,w_n,v$ are linearly independent, and hence $w_1+v,w_2+v,\ldots,w_n+v, v$ are linearly independent, and hence $w_1+v,\ldots,w_n+v$ are linearly independent. I'm not sure about the converse yet. –  Arturo Magidin Jul 4 '12 at 6:42
    
yes, I have that result too. Thank you for confirming :) –  Ajat Adriansyah Jul 4 '12 at 6:46
    
Judging from the plot, for example when $null(A)=2$, then the solution sets is a "plane" (not necessarily a subspace) since it does not through the origin, since it is being shifted by the vector $v$. This "plane" should be 2-dimensional isn't it? –  Ajat Adriansyah Jul 4 '12 at 6:53
    
But that's affine dimension, which is not necessarily the same as the number of linearly independent vectors with "ends" in the plane. See the example by copper.hat below. –  Arturo Magidin Jul 4 '12 at 6:54
    
(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$). –  Arturo Magidin Jul 4 '12 at 7:10

3 Answers 3

up vote 2 down vote accepted

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.)

share|improve this answer
    
ok, thanks for the example. I'm waiting for the example in undetermined system too, before I choose the answer :) –  Ajat Adriansyah Jul 4 '12 at 6:57
    
Take the system $x=0$ as a system in two unknowns, $x$ and $y$... –  Arturo Magidin Jul 4 '12 at 7:03
    
Oops, I completely missed the $m<n$. I added a small fix. –  copper.hat Jul 4 '12 at 7:23

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$

share|improve this answer
    
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$. –  Ajat Adriansyah Jul 4 '12 at 7:23

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

share|improve this answer
    
Your argument that $x_1,\ldots,x_r$ must be linearly independent does not follow; you did not take an arbitrary linear combination of the $x_i$ that was equal to $0$, you took a linear combination of the $v+x_i$. Say $\sum b_i x_i = 0$. How do you use the fact that $v+x_1,\ldots,v+x_r$ are linearly independent to conclude that $b_1=\cdots=b_r=0$? –  Arturo Magidin Jul 4 '12 at 6:40
    
yes, $\dim W = dim (ker A) = null(A)$. I can't follow your argument on "And hence $x_1,\cdots,x_{r+1}$ are linearly independent" I meant: we are given $v+x_1,\cdots,v+x_{r+1}$ vectors such that $$\sum_{i=1}^{r+1} a_i(v+x_i)=0$$ implies $a_i=0$ for all $i$, and we want to prove if $$\sum_{i=1}^{r+1} \alpha_i x_i =0$$ also would implies $\alpha_i=0$ for all $i$. This means we have $r+1$ linearly independent vectors in $W$, but $\dim W =r$, a contradiction, hence $v+x_1,\cdots,v+x_{r+1}$ can't be linearly independent. –  Ajat Adriansyah Jul 4 '12 at 6:43
    
tha t is to say: "we can't have more than $r$ linearly independent vectors in $\mathcal{A}(v)$" –  Ajat Adriansyah Jul 4 '12 at 6:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.