The problem of finding the basis for the null space of an $m \times n$ matrix $A$ is a well-known problem of linear algebra. We solve $Ax=0$ by Gaussian elimination. Either the solution is unique and $x=0$ is the only solution, or, there are infinitely many solutions which can be parametrized by the non-pivotal variables. Traditionally, my advice has been to calculate $\text{rref}(A)$ then read from that the dependence of pivotal on non-pivotal variables. Next, I put those linear dependencies into $x = (x_1, \dots , x_n)$ and if $x_{i_1}, \dots , x_{i_k}$ are the non-pivotal variables we can write:
$$ x = x_{i_1}v_1+ \cdots + x_{i_k}v_k \qquad \star$$
where $v_1, \dots, v_k$ are linearly independent solutions of $Ax=0$. In fact, $\text{Null}(A) = \text{span}\{ v_1, \dots, v_k \}$ and $k = \text{nullity}(A) = \text{dim}(\text{Null}(a))$. In contrast, to read off the basis of the column space I need only calculate $\text{rref}(A)$ to identify the pivot columns ( I suppose $\text{ref}(A)$ or less might suffice for this task). Then by the column correspondence property it follows that the pivot columns of $A$ serve as a basis for the column space of $A$. My question is this:
What is the nice way to calculate the basis for the null space of $A$ without need for non-matrix calculation? In particular, I'd like an algorithm where the basis for $\text{Null}(A)$ appears explicitly.
I'd like avoid the step I outline at $\star$. When I took graduate linear algebra the professor gave a handout which explained how to do this, but, I'd like a more standard reference. I'm primarily interested in the characteristic zero case, but, I would be delighted by a more general answer. Thanks in advance for your insight. The ideal answer outlines the method and points to a standard reference on this calculation.
Best Answer
You can literally read a basis for the nullspace of a matrix from its rref form. I describe the procedure in some detail here.
As this process consists of solving a few linear equations, it is easily automated: augment the transpose of the rref matrix with the appropriately-sized identity and row-reduce again, as you might do to compute the inverse of a matrix. The kernel basis will appear as if by magic on the augmented side of the zero rows of the resulting matrix. Taking the two larger examples from the linked answer, $$\begin{align} \pmatrix{1&0&2&-3\\0&1&-1&2\\0&0&0&0} &\to \left(\begin{array}{ccc|cccc}1&0&0&1&0&0&0\\0&1&0&0&1&0&0\\2&-1&0&0&0&1&0\\-3&2&0&0&0&0&1\end{array}\right) \\ &\to \left(\begin{array}{ccc|cccc}1&0&0&1&0&0&0\\0&1&0&0&1&0&0\\0&0&0&-2&1&1&0\\0&0&0&3&-2&0&1\end{array}\right) \end{align}$$ and $$\begin{align} \pmatrix{1&2&0&2\\0&0&1&-1\\0&0&0&0\\0&0&0&0} &\to \left(\begin{array}{cccc|cccc}1&0&0&0&1&0&0&0\\2&0&0&0&0&1&0&0\\0&1&0&0&0&0&1&0\\2&-1&0&0&0&0&0&1\end{array}\right) \\ &\to \left(\begin{array}{cccc|cccc}1&0&0&0&1&0&0&0\\0&1&0&0&0&0&1&0\\0&0&0&0&-2&1&0&0\\0&0&0&0&-2&0&1&1\end{array}\right). \end{align}$$ In fact, if you apply this process to the transpose of the original matrix, you get everything at once: the non-zero rows of the rref side are a basis for the image, while the augmented side of the zero rows are a basis for the kernel. This doesn’t give the nicest form of the kernel basis, however. The vectors you get will be (sometimes large) scalar multiples of the vectors that you would have gotten by computing the kernel separately. Here are a couple of examples: $$ M=\pmatrix{0&4&-4&8\\2&4&0&2\\3&0&6&9} \\ \left(\begin{array}{ccc|cccc}0&2&3&1&0&0&0\\ 4&4&0&0&1&0&0\\ -4&0&6&0&0&1&0\\ 8&2&9&0&0&0&1\end{array}\right) \to \left(\begin{array}{ccc|cccc}1&0&0&\frac14&\frac1{12}&0&\frac1{12}\\ 0&1&0&\frac14&\frac16&0&-\frac1{12}\\ 0&0&1&\frac16&-\frac19&0&\frac1{18}\\ 0&0&0&-288&144&144&0\end{array}\right). $$ Computing the kernel separately yields $(-2,1,1,0)^T$.
$$ A=\pmatrix{2&4&2&2\\1&3&2&0\\3&1&-2&8} \\ \left(\begin{array}{ccc|cccc}2&1&3&1&0&0&0\\ 4&3&1&0&1&0&0\\ 2&2&-2&0&0&1&0\\ 2&0&8&0&0&0&1\end{array}\right) \to \left(\begin{array}{ccc|cccc}1&0&4&\frac32&-\frac12&0&0\\ 0&1&-5&-2&1&0&0\\ 0&0&0&2&-2&2&0\\ 0&0&0&-6&2&0&2\end{array}\right). $$ The separate computation yields $(1,-1,1,0)^T$ and $(-3,1,0,1)^T$ for the kernel. I’ll leave it to you to verify that the rref side of these two examples does indeed hold a basis for the image.