Finding the basis of a null space

I am trying to understand why the method used in my linear algebra textbook to find the basis of the null space works. The textbook is 'Elementary Linear Algebra' by Anton.

According to the textbook, the basis of the null space for the following matrix:

$A=\left(\begin{array}{rrrrrr} 1 & 3 & -2 & 0 & 2 & 0 \\ 2 & 6 & -5 & -2 & 4 & -3 \\ 0 & 0 & 5 & 10 & 0 & 15 \\ 2 & 6 & 0 & 8 & 4 & 18 \end{array}\right)$

is found by first finding the reduced row echelon form, which leads to the following:

$(x_1,x_2,x_3,x_4,x_5,x_6)=(-3r-4s-2t,r,-2s,s,t,0)$

or, alternatively as

$(x_1,x_2,x_3,x_4,x_5,x_6)=r(-3,1,0,0,0,0)+s(-4,0,-2,1,0,0)+t(-2,0,0,0,1,0)$

This shows that the vectors

${\bf v_1}=(-3,1,0,0,0,0),\hspace{0.5in} {\bf v_2}=(-4,0,-2,1,0,0),\hspace{0.5in} {\bf v_3}=(-2,0,0,0,1,0)$

span the solution space.

It can be shown that for a homogenous linear system, this method always produces a basis for the solution space of the system.

Question

1. I don't understand why this method will always produce a basis for $Ax=0$. Could someone please explain to me why this method will always work? If it helps to explain, I already understand the process of finding the basis of a column space and row space. I also understand why elementary row operations do not alter the null space of a matrix.

2. What specific properties of matrices or vector space that I need to be aware of in order to understand why this method works?

-

1 Answer

The null space of $A$ is the set of solutions to $A{\bf x}={\bf 0}$. To find this, you may take the augmented matrix $[A|0]$ and row reduce to an echelon form. Note that every entry in the rightmost column of this matrix will always be 0 in the row reduction steps. So, we may as well just row reduce $A$, and when finding solutions to $A{\bf x}={\bf 0}$, just keep in mind that the missing column is all 0's.

Suppose after doing this, you obtain $$\left[\matrix{1&0&0&0&-1 \cr 0&0&1&1&0 \cr 0&0&0&0&0 \cr 0&0&0&0&0 \cr }\right]$$

Now, look at the columns that do not contain any of the leading row entries. These columns correspond to the free variables of the solution set to $A{\bf x}={\bf 0}$ Note that at this point, we know the dimension of the null space is 3, since there are three free variables. That the null space has dimension 3 (and thus the solution set to $A{\bf x}={\bf 0}$ has three free variables) could have also been obtained by knowing that the dimension of the column space is 2 from the rank-nullity theorem.

The "free columns" in question are 2,4, and 5. We may assign any value to their corresponding variable.

So, we set $x_2=a$, $x_4=b$, and $x_5=c$, where $a$, $b$, and $c$ are arbitrary.

Now solve for $x_1$ and $x_3$:

The second row tells us $x_3=-x_4=-b$ and the first row tells us $x_1=x_5=c$.

So, the general solution to $A{\bf x}={\bf 0}$ is $${\bf x}=\left[\matrix{c\cr a\cr -b\cr b\cr c}\right]$$

Let's pause for a second. We know:

1) The null space of $A$ consists of all vectors of the form $\bf x$ above.

2) The dimension of the null space is 3.

3) We need three independent vectors for our basis for the null space.

So what we can do is take $\bf x$ and split it up as follows:

\eqalign{ {\bf x}=\left[\matrix{c\cr a\cr -b\cr b\cr c}\right] &=\left[ \matrix{0\cr a\cr 0\cr 0\cr 0}\right]+ \left[\matrix{c\cr 0\cr 0\cr 0\cr c}\right]+ \left[\matrix{0\cr 0\cr -b\cr b\cr 0}\right]\cr &= a\left[ \matrix{0\cr1\cr0\cr 0\cr 0}\right]+ c\left[ \matrix{1\cr 0\cr 0\cr 0\cr 1}\right]+ b\left[ \matrix{0\cr 0\cr -1\cr 1\cr 0}\right]\cr } Each of the column vectors above are in the null space of $A$. Moreover, they are independent. Thus, they form a basis.

I'm not sure that this answers your question. I did a bit of "hand waving" here. What I glossed over were the facts:

1)The columns of the echelon form of $A$ that do not contain leading row entries correspond to the "free variables" to $A{\bf x}={\bf 0}$. If the number of these columns is $r$, then the dimension of the null space is $r$ (again, if you know the dimension of the column space, you can see that the dimension of the null space must be the number of these columns from the rank-nullity theorem).

2) If you split up the general solution to $A{\bf x}={\bf 0}$ as done above, then these vectors will be independent (and span of course since you'll have $r$ of them).

-
:Thank you for explaining the procedure of finding the basis of the null space. I find it to be much clearer than how the textbook explained it. However, I am still not clear why splitting the general solution will produce a set of vectors that will span the null space. Also, the set of vectors are independent because splitting $\bf x$ will always produce non-zero vectors, hence $a_1{\bf v_1}+a_2{\bf v_2}+...+a_n{\bf v_n}$ will have the trivial solution only. Is this right? – Sara Dec 5 '11 at 16:31
@sara Sorry for the last comment. When you split $\bf x$ up, you split it into vectors with disjoint supports, so you'll have independence. For spanning: Splitting the general solution up as above will give the necessary number of vectors for a basis of the null space, since you decompose $x$ into a linear combination of as many vectors as you have free variables (and the number of free variables is the number of "free columns", which in turn is the dimension of the null space by the rank-nullity theorem). – David Mitra Dec 5 '11 at 18:34
Thank you very much for your clarification – Sara Dec 9 '11 at 16:49
nicely explained (+1) – SHOBHIT GAUTAM Nov 16 '14 at 5:04
Sorry but I think, you should check the calculations again.. maybe because I'm getting the basis for your example as {[0 1 0 0 0],[0 0 -1 1 0],[1 0 0 0 1]} – ADG 2 days ago