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?

Solution 1:

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

Solution 2:

There is a mechanical part in the accepted (+1) answer that may possibly need a more step-by-step explanation, namely the process behind

what we can do is take $\mathbf x$ and split it up

Reducing the matrix $A$ to the reduced row echelon (rref) form results in:

$$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)\to\left(\begin{array}{rrrrrr} \bbox[5px,border:2px solid red]1 & 3 & 0 & 4 & 2 & 0 \\ 0 & 0 & \bbox[5px,border:2px solid red]1 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \bbox[5px,border:2px solid red]1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)$$

There are three pivot columns corresponding to the pivot $1$'s in red, and the rank-nullity theorem tells us that there are $n-r=3$ vectors in any basis of the $N(A)$, corresponding to the free variables.

At this point it is worth remembering where all this comes from: the homogeneous system of linear equations $A\vec x = \vec 0,$ which has now been reduced to:

$$\begin{align} 1x_1 + 3x_2+ 0x_3+4x_4+2x_5 +0x_6 &=0\\ 0x_1 + 0x_2+ 1x_3+2x_4+0x_5 +0x_6 &=0\\ 0x_1 + 0x_2+ 0x_3+0x_4+0x_5 +1x_6 &=0\\ 0x_1 + 0x_2+ 0x_3+0x_4+0x_5 +0x_6 &=0\\ \end{align}$$

Expressing the pivot variables in terms of the free variables:

$$\begin{align} 1x_1 &= - 3\;\color{blue}{x_2} - 4\;\color{red}{x_4} - 2\;\color{magenta}{x_5} \\ 1x_3 &= -2\;\color{red}{x_4}\\ 1x_6 &=\;0\\ \end{align}$$

immediately shows the way the basis vectors of the $N(A)$ will be filled in from their "skeleton" form simply indicating the column where the free variable in question is located (i.e. $x_2,x_4,x_5$):

$$\left\{\begin{bmatrix}0\\\color{blue}1\\0\\0\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\0\\\color{red}1\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\0\\0\\\color{magenta}1\\0\end{bmatrix}\right\}\to \color{blue}{x_2}\,\begin{bmatrix}0\\1\\0\\0\\0\\0\end{bmatrix}+\color{red}{x_4}\,\begin{bmatrix}0\\0\\0\\1\\0\\0\end{bmatrix}+\color{magenta}{x_5}\,\begin{bmatrix}0\\0\\0\\0\\1\\0\end{bmatrix}$$

to the final form:

$$\color{blue}{x_2}\,\begin{bmatrix}-3\\1\\0\\0\\0\\0\end{bmatrix}+\color{red}{x_4}\,\begin{bmatrix}-4\\0\\-2\\1\\0\\0\end{bmatrix}+\color{magenta}{x_5}\,\begin{bmatrix}-2\\0\\0\\0\\1\\0\end{bmatrix}\to \text{basis }N(A)= \left\{\begin{bmatrix}-3\\\color{blue}1\\0\\0\\0\\0\end{bmatrix},\begin{bmatrix}-4\\0\\-2\\\color{red}1\\0\\0\end{bmatrix},\begin{bmatrix}-2\\0\\0\\0\\\color{magenta}1\\0\end{bmatrix}\right\}$$

So it boils down to changing the signs of the entries in the rref, and keeping track of the free variables.

require("pracma")
A = matrix(c(1,3,-2,0,2,0,2,6,-5,-2,4,-3,0,0,5,10,0,15,2,6,0,8,4,18), nrow=4, byrow=T)
x2= c(-3,1,0,0,0,0); A %*% x2; x4=c(-4,0,-2,1,0,0); A %*% x4; x5=c(-2,0,0,0,1,0); A %*% x5