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 &amp; 3 &amp; -2 &amp; 0 &amp; 2 &amp; 0 \\ 2 &amp; 6 &amp; -5 &amp; -2 &amp; 4 &amp; -3 \\ 0 &amp; 0 &amp; 5 &amp; 10 &amp; 0 &amp; 15 \\ 2 &amp; 6 &amp; 0 &amp; 8 &amp; 4 &amp; 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


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.
What specific properties of matrices or vector space that I need to be aware of in order to understand why this method works?
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&amp;0&amp;0&amp;0&amp;-1 \cr 0&amp;0&amp;1&amp;1&amp;0 \cr 0&amp;0&amp;0&amp;0&amp;0 \cr  0&amp;0&amp;0&amp;0&amp;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]
&amp;=\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
&amp;=
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).
The software Mathematica can find a null-space spanning set for Matrices given with exact coefficients. It can find exactly the answer your book gives:

NullSpace[{{1, 3, -2, 0, 2, 0}, {2, 6, -5, -2, 4, -3}, {0, 0, 5, 10, 0, 15}, {2, 6, 0, 8, 4, 18}}]


gives

{{-2, 0, 0, 0, 1, 0}, {-4, 0, -2, 1, 0, 0}, {-3, 1, 0, 0, 0, 0}}


I suggest you start here if you are interested in how this is done in a computationally efficient and of course provably correct way. That Wikipedia section for instance points out, that in practice the so called Bareiss algorithm is more useful than Gaussian elimination.