Nullspace
For the equation $Ax = 0$, we often immediately think of the solution $x = 0$. But if that were always the case, this article might end here. However, life is rarely that simple, and neither is math. The solution $x = 0$ is unique if and only if the matrix $A$ is invertible. For non-invertible matrices, there always exist $x \neq 0$ satisfying $Ax = 0$. For each such $x$, we say that $x$ belongs to the nullspace of $A$.
Suppose we have a matrix $A$ of size $m \times n$, the nullspace of $A$ is expressed as follows:
The nullspace $N(A)$ contains all $x$ satisfying $Ax = 0$. These vectors $x$ lie in the space $\mathbf{R}^{n}$.
$N(A)$ is also a subspace. If $N(A)$ contains $x$ and $y$, meaning $Ax = 0$ and $Ay = 0$, then $A(x+y) = Ax + Ay = 0$. Additionally, for some $c$, we also have $A(cx) = c(Ax) = c(0) = 0$. Thus, $x+y$ and $cx$ still lie in the nullspace of $A$, satisfying the conditions for $N(A)$ to be a subspace.
Furthermore, in the article about column space, we have $C(A) \in \mathbf{R}^m$. Now we have $N(A) \in \mathbf{R}^{n}$. Pay attention to avoid confusion.
Suppose we have the equation:
$$ \begin{bmatrix} 1 & 1 & 2 \\ 2 & 2 & 4 \\ 3 & 1 & 4 \\ 2 & 1 & 3 \end{bmatrix} + \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$
First, we notice a rule in all rows: column 1 + column 2 - column 3 = 0.
We can choose any set of numbers satisfying this rule, for example, $(1; 1; -1)$, $(2; 2; -2)$, $(7; 7; -7)$. Generally, we obtain the solution set for the system of equations as vectors of the form $(a, a, -a)$. This is the nullspace $N(A)$. This vector space is a line in $\mathbf{R}^3$, and $(1; 1; -1)$, $(2; 2; -2)$, $(7; 7; -7)$ are points on this line.
Solving $Ax = 0$
The best way to find the nullspace of $A$ is to solve the linear system $Ax = 0$. In this section, I will guide you through the detailed steps to solve a system of equations $Ax = 0$.
Special Solutions, Basic Variables, and Free Variables
Example: let $A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}$
First, we transform $A$ into row echelon form $U = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix}$. The method can be reviewed here.
After converting the matrix to row echelon form, we can use back-substitution to solve the system of equations $Ux = 0$.
$$ \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = 0 $$
The issue here is to substitute numbers into which $x$ values to find the remaining $x$’s. To determine this, we identify basic variables and free variables through pivot columns and free columns.
Continuing with the above example, matrix $U$ has 2 pivots, meaning only columns 1 and 3 contain pivot elements. These are pivot columns of matrix $U$. Columns without pivot elements are called free columns. Pivot columns are also known as independent columns, meaning these columns are linearly independent of the other columns in the matrix. You can verify that the pivot columns are linearly independent (which cannot be written as a linear combination of any other columns in the matrix). Free columns can be written as linear combinations of one or more columns in the matrix.
We assign any value to the $x$ corresponding to the free columns in matrix $U$. These $x$’s are called free variables. Then, we find values for the remaining $x$’s.
In the example above, I assign $x_2 = 1$ and $x_4 = 0$. The equation $Ux = 0$ is then equivalent to:
$$ \begin{align*} & \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ 1 \\ x_3 \\ 0 \end{bmatrix} &&=0 \\ \Leftrightarrow & \begin{cases} x_1 + 2 + 2x_3 &&= 0 \\ 2x_3 &&= 0 \end{cases} \\ \Leftrightarrow & \begin{cases} x_1 + 2 + 2x_3 &&= 0 \\ 2x_3 &&= 0 \end{cases} \\ \end{align*} $$
Thus, we find a special solution $x = (-2; 1; 0; 0)$. This is a special solution because we choose only 1 to assign to the free variables. If there are $n$ free variables, we find $n$ special solutions correspondingly. We assign 1 to each free variable, and the remaining free variables are set to 0. You might wonder why we need to find special solutions. Because we have a definition like this:
The nullspace of $A$ contains every linear combination of the special solutions $Ax = 0$.
It means that if there are no free variables in matrix $A$ (equivalent to all columns of $A$ being pivot columns), then we have $Ax = 0$ having only the trivial solution $x = 0$.
Is it enough to say that the nullspace $N(A)$ is all vectors of the form $cx$, with $x = (a; -0.5a; 0; 0)$? Actually, it’s not. To describe the nullspace most fully, we need to find all the special solutions. We have a $3 \times 4$ matrix with 2 pivot columns. The number of special solutions we have is $4 - 2 = 2$. To find the remaining special solution, we set $x_2 = 0$ and $x_4 = 1$.
$$ \begin{align*} & \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ 0 \\ x_3 \\ 1 \end{bmatrix} &&= 0 \\ \Leftrightarrow & \begin{cases} x_1 + 2x_3 + 2 &&= 0\\ 2x_3 + 4 &&= 0 \end{cases} \\ \Leftrightarrow & \begin{cases} x_1 &&= 2\\ x_3 &&= -2 \end{cases} \end{align*} $$
We find the second special solution $x^{*} = (2; 0; -2; 1)$.
So, the nullspace $N(A) = c\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$.
Reduced Row Echelon Form
With the method of using elimination to transform $A$ to $U$ as above, we have found the nullspace of $A$. However, the problem does not stop here. We can further simplify $U$ to a reduced row echelon form $rref$ by continuing to apply elimination to the rows of $U$.
The reduced row echelon form matrix has basic elements as 1 and the elements above and below the basic element are 0. To transform a row echelon matrix to reduced row echelon form, we have the following 2 steps:
- Generate 0s above the basic element row: We use the basic element’s row to eliminate the rows above
- Transform basic elements to 1s: Divide the row vector containing the basic element by that basic element
Let’s try transforming matrix $U$ in the above example into its reduced row echelon form. The reduced form matrix, denoted as $R$, is:
$$ \begin{aligned} \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 & 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{aligned} = R = rref(A) $$
Instead of solving $Ux=0$, we will find the solution of the system of equations $Rx = 0$. Since the matrix has 2 free variables, we can still set each of these variables to 1 in turn.
$$ \begin{align*} & \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ 1 \\ x_3 \\ 0 \end{bmatrix} &&= 0 \\ \Leftrightarrow & \begin{cases} x_1 + 2 &&= 0\\ x_3 &&= 0 \end{cases} \\ \Leftrightarrow & \begin{cases} x_1 &&= -2\\ x_3 &&= 0 \end{cases} \end{align*} $$
$$ \begin{align*} & \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ 0 \\ x_3 \\ 1 \end{bmatrix} &&= 0 \\ \Leftrightarrow & \begin{cases} x_1 - 2 &&= 0\\ x_3 + 2 &&= 0 \end{cases} \\ \Leftrightarrow & \begin{cases} x_1 &&= 2\\ x_3 &&= -2 \end{cases} \end{align*} $$
We still find 2 solutions: $(-2; 1; 0; 0)$ and $(2; 0; -2; 1)$. When solving $Rx = 0$, the system of equations we need to solve is simpler than $Ux = 0$. We can calculate the value of each basic variable independently, without considering the values of other basic variables. Thus, to solve the linear system $Ax = 0$, we went through 2 steps of transforming $A$ to $U$ and $R$. Since these transformation steps are linear, in essence, $N(A) = N(U) = N(R)$.
Finally, I will summarize some key points about the nullspace as follows:
The elimination from $A$ to $U$ to $R$ does not change the nullspace of $A$.
The reduced row echelon form matrix $rref$ contains all basic elements as 1 and the elements above and below the basic element are 0.
If column $i$ in matrix $R$ has no basic element, we will find a special solution $Ax = 0$ with $x_i =1$.
The rank of the matrix is the number of basic elements of that matrix, which is also the number of non-zero rows of matrix $R$.
Any $m \times n$ matrix where $m < n$ has a nontrivial solution for $Ax = 0$.