how to find null space basis directly by matrix calculation

Question

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.

Answer 1

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.

Answer 2

the procedure suggested by amd is what I was looking for. I will supplement his excellent examples with a brief explanation as to why it works. Some fundamental observations: $$ \text{Col}(A) = \text{Row}(A^T) \ \ \& \ \ [\text{Row}(A)]^T = \text{Col}(A)$$ Also, for any Gaussian elimination there exists a product of elementary matrices for which the row reduction can be implemented as a matrix multiplication. That is, $\text{rref}(M) = EM$ for an invertible square matrix $E$ of the appropriate size. With these standard facts of matrix theory in mind we continue.

Let $A$ be an $m \times n$ matrix. Construct $M = [A^T|I]$ where $I$ is the $n \times n$ identity matrix. Suppose $\text{rref}(M) = EM$. Let $B$ be an $k \times m$ matrix and $C$ be an $(n-k) \times n$ matrix for which $$ \text{rref}(M) = \left[ \begin{array}{c|c} B & W \\ \hline 0 & C \end{array} \right]$$ the $W$ is a $k \times n$ matrix. Here we assume all rows in $B$ are nonzero. One special case deserves some comment: in the case $A^T$ is invertible there is no $0,W$ or $C$ and $k=0$. Otherwise, there is at least one zero row in $\text{rref}(A^T)$ as the usual identities for row reduction reveal that $\text{rref}(A^T) = \left[ \begin{array}{c} B \\ \hline 0 \end{array}\right]$. But, the nonzero rows in the rref of a matrix form a basis for the row space of a matrix. Thus the rows of $B$ form a basis for the row space of $A^T$. It follows the transpose of the rows of $B$ form a basis for the column space of $A$. I derive this again more directly in what follows.

We have $EM = E[A^T|I] = \left[ \begin{array}{c|c} B & W \\ \hline 0 & C \end{array} \right]$ thus $[EA^T|E] = \left[ \begin{array}{c|c} B & W \\ \hline 0 & C \end{array} \right]$. From this we read two lovely equations: $$ EA^T = \left[ \begin{array}{c} B \\ \hline 0 \end{array}\right] \ \ \& \ \ E = \left[ \begin{array}{c} W \\ \hline C \end{array}\right]$$ Transposing these we obtain $$ AE^T = [B^T|0] \ \ \& \ \ E^T = [W^T|C^T]$$ thus $$ AE^T = A[W^T|C^T] = [AW^T|AC^T] = [B^T|0] $$ Once more we obtain two interesting equations: $$ (i.) \ AW^T = B^T \ \ \& \ \ (ii.) \ AC^T = 0 $$ It follows immediately from $(i.)$ that the columns in $B^T$ are in the column space of $A$. Likewise, it follows immediately from $(ii.)$ that the columns in $C^T$ are in the null space of $A$. By construction, the columns of $B^T$ are the rows of $B$ which are linearly independent due to the structure of Gaussian elimination. Furthermore, the rank of $M$ is clearly $n$ by its construction. It follows that there must be $(n-k)$ linearly independent rows in $C$. But, I already argued that the rows of $B$ give a basis for $\text{Row}(A^T)$ hence $k$ is the rank of $A$ and $(n-k)$ is the nullity of $A$. This completes the proof that the columns of $C^T$ form a basis for $\text{Null}(A)$ and the columns of $B^T$ form the basis for $\text{Col}(A)$. In summary, to obtain both the basis for the column and null space at once we can calculate: $$ [\text{rref}[A^T|I]]^T = \left[ \begin{array}{c|c} B^T & 0 \\ \hline W^T & C^T \end{array} \right]$$ Of course, pragmatically, it's faster for small examples to simply follow the usual calculation at $\star$ in my original question. Thanks to amd for the help.