5.1 Algorithm for solving $Ax=0$
The idea behind this exercise is to come up with an algorithm to find the nullspace of a matrix $A$. Let us start by taking a matrix $A$.
$$\begin{align} A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \end{align}$$
One of the first thing to notice in $A$ is that $row_3$ is a linear combination of $row_1$ and $row_2$ ($row_3 = row_1 + row_2$). The way to solve a system of linear equations is by elimination. Different row elimination steps can be used to transform $A$ into an upper triangular matrix with the same steps repeated on the right hand side. As the right hand side is $0$ here, the elimination steps can be skipped for it.
$$\begin{align} A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \xrightarrow{\text{S1}} \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \xrightarrow{\text{S3}} \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} = U \end{align}$$
The resultant matrix after the elimination steps is $U$ which is in the echelon form. Now, instead of solving $Ax=0$, $Ux=0$ can be solved. There are two pivots: $U_{11} = 1,U_{23} = 2$. The number of pivots is also called as the rank of the matrix. Here, the rank is $2$. The columns in which pivots are there ($col_1, col_3$) are called as pivot columns. Remaining columns ($col_2, col_4$) are called as free columns. The equation $Ux=0$ can be written as follows.
$$\begin{align} x_1\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + x_2\begin{bmatrix} 2 \\ 0 \\ 0 \end{bmatrix} + x_3\begin{bmatrix} 2 \\ 2 \\ 0 \end{bmatrix} + x_4\begin{bmatrix} 2 \\ 4 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align}$$
The values in $x$ corresponding to the free columns (here they are $x_2,x_4$) can be assigned any values and then we can find the values of $x_1,x_3$ to complete the solution. We can systematically assign values to the multipliers corresponding to the free columns. Let $x_2=1,x_4=0$, this gives $x_1=-2,x_3=0$ and hence $\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$ is a solution (or any multiple of this vector), a vector in the null space. Another choice for free variables can be $x_2=0,x_4=1$, which gives $x_1=2,x_3=-2$ and hence $\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$ is another solution (or any multiple of this vector), another vector in the null space. Hence, the general solution can be given as:
$$\begin{align} x = c\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align}$$
Another thing to note is the number of individual solutions is equal to the number of free variables or free columns. For a $m \times n$ matrix whose rank is $r$, the number of free columns/variables( individual solutions) will be $n-r$.
5.2 Reduced Row-Echelon Form
The row-echelon matrix $U$ can be further simplified by elimination steps. The idea is to get a matrix which have $0$ in the cells above and below pivot. Furthermore, the pivot values can be reduced to $1$. The reduced matrix $R$ is called as the matrix in reduced row-echelon form.
$$\begin{align} U = \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} = R \end{align}$$
If we further examine the matrix $R$, it can be noticed that an identity matrix $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$ sits in the pivot rows and columns ($row_1, row_2, col_1, col_2$). Corresponding entries in the free columns are $\begin{bmatrix} 2 & -2 \\ 0 & 2 \end{bmatrix} = F$. If we look at $I$ and $F$, they are nothing but the rearranged individual solutions with sign switched for $F$. Let us just rearrnage the reduced row-echelon matrix $R$ as follows, where the last matrix is nothing but matrix represented in the block form. We have to find $x$ such that $Rx=0$.
$$\begin{align} R = \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 2 & -2 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} \end{align}$$
For the given R in the block form, the solution can be given as:
$$\begin{align} \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}\begin{bmatrix} -F \\ I \end{bmatrix} = 0 \end{align}$$
Hence, the final solution in the rearranged form is:
$$\begin{align} \begin{bmatrix} -F \\ I \end{bmatrix} = \begin{bmatrix} -2 & 0 \\ 2 & -2 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \end{align}$$
5.3 Example
Let us look at one more example. The system of equations which we have to solve is $Bx=0$ where $B=A^T$ for the above matrix $A$.
$$\begin{align} B = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} \end{align}$$
The transformation of $B$ into row-reduced echelon form can be given as follows:
$$\begin{align} B = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 2 & 2 \\ 0 & 4 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \end{align}$$
$$\begin{align} I = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}; F = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{align}$$
Hence the null space can be given as $$\begin{align} c\begin{bmatrix} -F \\ I \end{bmatrix} = c\begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} \end{align}$$