Nullspace of a Matrix
From bio-physics-wiki
The Nullspace is formed by the set of vectors that satisfy the equation \begin{align} \mathbf{Ax} &=\mathbf{0}\\ \end{align} What is the Nullspace for the system \begin{align} \begin{bmatrix} 1 & 1 & 2 \\ 2 & 1 &3 \\ 3 & 1 & 4 \\ 4 & 1 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}&= \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \quad ? \end{align} Using the column picture, we see that one vector in the Nullspace is simply the zero vector \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}&= \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align} Also the third vector is a combination of vector one and two, so \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}&= \begin{bmatrix} 1 \\ 1 \\ -1 \end{bmatrix} \end{align} is a vector in the Null space as well. In fact every multiple of this vector solves the above equation. \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}&= c \cdot \begin{bmatrix} 1 \\ 1 \\ -1 \end{bmatrix} \end{align} For $c=0$ this includes the zero vector. So in this case the Nullspace is one dimensional and spanned by the vector $(1,1,-1)$.
Finding the Vectors spanning the Nullspace
To find the vectors that span the Nullspace in general not so easy as in the above example. Here an algorithm to solve for the vectors in the Nullspace is discussed. The method is shown at the following example
\begin{align} \begin{bmatrix} 1 & 2 & 2 &2\\ 2 & 4 &6 &8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{align}
Notice, the third row is the sum of row one and two. We start with Matrix Elimination and clean out the entries below the pivots. \begin{align} \begin{bmatrix} 1 & 2 & 2 &2\\ 2 & 4 &6 &8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 2 &2\\ 0 & 0 &2 &4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \end{align} we find that after the first step of elimination the third row equals the second row. The next step gives \begin{align} \begin{bmatrix} {1} & {2} & 2 &2\\ 0 & 0 &{2} &4 \\ 0 & 0 & 2 & {4} \end{bmatrix} \rightarrow \begin{bmatrix} \color{red}{1} & \color{green}{2} & 2 &2\\ 0 & 0 &\color{red}{2} &\color{green}{4} \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} Now the matrix is in so called echelon form (staircase form). The pivots are marked red, and the green entries belong to the so called free column, we can choose their variables freely. However, a good choice is to set one of the free variables one and the other zero. \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= \begin{bmatrix} * \\ 1 \\ * \\ 0 \end{bmatrix} \end{align} Then we can calculate what the other pivot variables (marked with $*$) must be, that the equation is satisfied. We find the answer by backsubstitution \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= c \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} \end{align} This is the first vector in the Nullspace. No we choose the free variables \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= \begin{bmatrix} * \\ 0 \\ * \\ 1 \end{bmatrix} \end{align} and find the vector \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= d \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align} The number of pivots is called the rank of a matrix. In our example the $rank(\mathbf{A})=2$. The number of vectors in the Nullspace is $n=dim(\mathbf{A})-rank(\mathbf{A})$. In our case this is $n=4-2=2$, so we found all vectors in the Nullspace. We can bring the matrix in the so called reduced row echelon form if we continue to clean out the entries above the pivots. \begin{align} \begin{bmatrix} 1 & 2 & 2 &2\\ 0 & 0 &2 &4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 0 &-2\\ 0 & 0 &1 &2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} Let us call this matrix $\mathbf{R}$ \begin{align} \mathbf{R} = \begin{bmatrix} 1 & 2 & 0 &-2\\ 0 & 0 &1 &2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align} If we exchange column two and three $\mathbf{R}$ can be written as a block matrix \begin{align} \mathbf{R} = \begin{bmatrix} \mathbf{I} & \mathbf{F}\\ \mathbf{0} & \mathbf{0} \end{bmatrix} \end{align} where $I$ stands for the identity matrix and $F$ for the free variables. If we solve for the Nullspace in this form \begin{align} \mathbf{RN}&=\mathbf{0}\\ \begin{bmatrix} \mathbf{I} & \mathbf{F}\\ \mathbf{0} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{X_1}\\ \mathbf{X_2} \end{bmatrix}&=\begin{bmatrix} \mathbf{0}\\ \mathbf{0} \end{bmatrix} \end{align} where $\mathbf{N}=\begin{bmatrix} \mathbf{X_1}\\ \mathbf{X_2} \end{bmatrix}$ contains all the vectors in the Nullspace with the solution \begin{align} \begin{bmatrix} \mathbf{X_1}\\ \mathbf{X_2} \end{bmatrix}=\begin{bmatrix} -\mathbf{F}\\ \mathbf{I} \end{bmatrix} \end{align}
Video Lectures:
