Kernels and reduced row echelon form - explanation

The following text is written in my textbook and I don't really understand it:

If $A = (a_{ij}) \in$ Mat$(m x N, F)$ is a matrix in reduced row echelon form with $r$ nonzero rows and pivots in the columns numbered $j_1 < ... < j_r$, then the kernel ker$(A)$ is generated by the $n-r$ elements $ w_k = e_k - \sum\limits_{1 \le i \le r, j_i \le k} a_{ik}e_{j_i}$ for $k \in {1, \cdots , n} \ {j_1, \cdots, j_r}$, where $e_1, \cdots, e_n$ are the standard generators of $F^n$.

There are no computational examples and the notation is a bit overwhelming so I don't know how I can use it. Can somebody give an example of this in practice?

Solution 1:

What this is telling you is that you can basically read a basis for the kernel directly from the rref matrix by doing the following:

Find the columns that don’t have pivots. You’ll have that many basis vectors, as you can verify by checking the rank of the reduced matrix. For each of these vectors, set one of the components that correspond to these pivotless columns to $1$ and the rest to $0$. The remaining components of the vectors are found by negating the other elements of the column (i.e., those in rows that do have pivots—the non-zero rows) in the rref matrix corresponding to the element that you have set to $1$.

Using Omnomnomnom’s example, we have $$ A=\pmatrix{1&2&0\\0&0&1\\0&0&0}. $$ The kernel is one-dimensional. The second column doesn’t have a pivot, so our basis vector $k_1$ will be of the form $\langle x,1,z\rangle$. We can find $x$ and $z$ by solving $Ak_1=0$, which gives us $x+2=0$ and $z=0$, but that’s precisely the negations of the first and second elements of the second column.

For a slightly larger example, consider the rref matrix $$ \pmatrix{1&0&2&-3\\0&1&-1&2\\0&0&0&0}.$$ The third and fourth columns don’t have pivots, so our two basis vectors will be of the form $$ k_1=\pmatrix{x_1\\x_2\\1\\0}\text{ and }k_2=\pmatrix{y_1\\y_2\\0\\1}.$$ Since we set $k_1$’s third element to $1$, we fill it in from the third column, giving $$k_1=\pmatrix{-2\\1\\1\\0}.$$ Similarly, reading from the fourth column, $$k_2=\pmatrix{3\\-2\\0\\1}.$$

Finally, a somewhat trickier example:$$ A=\pmatrix{1&2&0&2\\0&0&1&-1\\0&0&0&0\\0&0&0&0}.$$ The pivotless columns are now the second and fourth, so you have to be a bit more careful when constructing the kernel basis vectors. They’re going to be of the form $$k_1=\pmatrix{x_1\\1\\x_3\\0}\text{ and }\pmatrix{y_1\\0\\y_3\\1}.$$ The missing elements are filled in from the second and fourth columns of $A$, but we have to take them from the non-zero rows, i.e., the first and second. So, $$k_1=\pmatrix{-2\\1\\0\\0\\}\text{ and }k_2=\pmatrix{-2\\0\\1\\1}.$$ Notice that the $-1$ in the second row and last column ended up as the third element of $k_2$.

Update (Nov. 2016): Keeping track of exactly what goes where in the resulting vectors can be confusing and error-prone. Fortunately, there’s a purely mechanical method available if you’re willing to go beyond the strictures of pure row-reduced echelon form.

Insert rows of zeros to fill in any “gaps” in the pivots and then append or delete all-zero rows at the bottom as necessary to produce a square matrix. (If the matrix was square to begin with, this can be accomplished with elementary row swaps.) Then, just read down the main diagonal: if you encounter a zero, set that element to $-1$ and take the resulting column (or its negation) as one of your kernel basis vectors. Starting with last example above, swap the second and third rows to get $$\pmatrix{\mathbf1&2&0&2\\0&\mathbf0&0&0\\0&0&\mathbf1&-1\\0&0&0&\mathbf0}.$$ With this matrix in hand, you can write down a basis for the kernel without further ado: $(2,\mathbf{-1},0,0)^T$ and $(2,0,-1,\mathbf{-1})^T$, which is obviously equivalent to the one derived above.

In addition, since the rows of the rref have only been rearranged and the columns are still in the same order, the $1$s along the diagonal give you the column and row space bases in the same way that the pivots of the rref do.