Finding the basis of a null space

Question

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?

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

Answer 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

Answer 3

Solution

The matrix $\mathbb{C}^{m\times n}_{\rho}$ is map between $\mathbb{C}^{n}$ and $\mathbb{C}^{m}$.

Consider the vectors $x\in\mathbb{C}^{n}$, $y\in\mathbb{C}^{m}$. The matrix $\mathbf{A}$ maps $\mathbb{C}^{n}$ to $\mathbb{C}^{m}$; $\mathbf{A}^{*}$ maps $\mathbb{C}^{m}$ to $\mathbb{C}^{n}$.

The Fundamental Theorem of Linear Algebra appears in the guise of a map.

$$ % \begin{align} % \mathbf{A} x = y \qquad \mathbb{C}^{n} &\mapsto \mathbb{C}^{m} \\ % \mathbf{A}^{*} y = x \qquad \mathbb{C}^{m} &\mapsto \mathbb{C}^{n} \\ % \end{align} % $$

---

I already understand the process of finding the basis of a column space and row space

Since the machinations are clear, we choose a simpler matrix which caters to mental manipulation: $$ \mathbf{A} = \left[ \begin{array}{ccr} 1 & 3 & -2 \\ 2 & 6 & -5 \\ \end{array} \right] \in \mathbb{C}^{3\times 2}_{2} $$

The only nontrivial null space is $\mathcal{N}\left( \mathbf{A} \right)$.

The augmented matrix is $$ % \left[ \begin{array}{c|c} \mathbf{A}^{*} & \mathbf{I}_{3} \\ \end{array} \right] % = % \left[ \begin{array}{rr|ccc} 1 & 2 & 1 & 0 & 0 \\ 3 & 6 & 0 & 1 & 0 \\ -2 & -5 & 0 & 0 & 1 \\ \end{array} \right] $$ You perform a sequence of elementary row operations to reduce the left-hand component to row echelon form. Call the first operation which clears the first column $\mathbf{E}_{1}.$

$$ \mathbf{E}_{1} \left[ \begin{array}{c|c} \mathbf{A}^{*} & \mathbf{I}_{3} \\ \end{array} \right] = \left[ \begin{array}{c|c} \mathbf{E}_{1} \mathbf{A}^{*} & \mathbf{E}_{1} \mathbf{I}_{3} \\ \end{array} \right] $$ The second step clears the second column: $$ \mathbf{E}_{2} \left[ \begin{array}{c|c} \mathbf{E}_{1} \mathbf{A}^{*} & \mathbf{E}_{1} \mathbf{I}_{3} \\ \end{array} \right] = \left[ \begin{array}{c|c} \mathbf{E}_{2} \mathbf{E}_{1} \mathbf{A}^{*} & \mathbf{E}_{2} \mathbf{E}_{1} \mathbf{I}_{3} \\ \end{array} \right] = \left[ \begin{array}{cr|rcc} 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & \color{red}{-3} & \color{red}{1} & \color{red}{0} \\ 0 & -1 & 2 & 0 & 1 \\ \end{array} \right] $$

Your question is how the null space vector appeared: $$ % \left[ \begin{array}{ccr} 1 & 3 & -2 \\ 2 & 6 & -5 \\ \end{array} \right] % \left[ \begin{array}{r} \color{red}{-3} \\ \color{red}{1} \\ \color{red}{0} \end{array} \right] % = % \left[ \begin{array}{r} 0 \\ 0 \end{array} \right] % $$

---

The answer involves a change of perspective.

The elementary operations are sculpted to sweep through the matrix and clear successive rows. This much is clear. The perspective change involves looking at the augmented matrix as collection of row vectors: $$ % \left[ \begin{array}{c|c} \mathbf{A}^{*} & \mathbf{I}_{3} \\ \end{array} \right] % = % \left[ \begin{array}{c|c} u^{*}_{1} & v^{*}_{1} \\ u^{*}_{2} & v^{*}_{2} \\ u^{*}_{3} & v^{*}_{3} \\ \end{array} \right] % $$

By construction, the $u$ vectors in $\mathbf{C}^{3}$ are linked to the $v$ vectors in $\mathbf{C}^{2}$ via $$ \boxed{ v^{*}_{k} \mathbf{A}^{*} = u^{*}_{k}, \quad k = 1, 2, 3 } $$ The final form we seek is given by $$ \begin{align} % \left( v^{*}_{k} \mathbf{A}^{*} \right)^{*} &= \left( u^{*}_{k} \right)^{*} \\ % \mathbf{A} v_{k} &= u_{k} % \end{align} $$ The mapping action of the matrix $\mathbf{A}$ defines the augmented matrix. When manipulation creates a $u=\mathbf{0}$ vector, the corresponding $v$ vector must be in the null space.

---

Colloquial mathematics

The augmented matrix is a tool to study the mapping action of a matrix between the vector spaces $\mathbf{C}^{m}$ and $\mathbf{C}^{n}$. To find null space vectors, manipulate the left-hand side to create a zero row. A null space vector appears as a row vector on the right-hand side.

Answer 4

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.