5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well done ${}{}{}$ $\endgroup$ – Omnomnomnom Nov 9 '15 at 21:28
  • $\begingroup$ can you give an example of the process when the diagonal eleemnts in rref are not necesarily $1$? This case for example arises when having integer matrices and want the results of operations to still be in integers (not rationals) so I have a weak rref matrix where diagonal elements are not necessarily $1$. $\endgroup$ – Nikos M. Jun 24 at 11:21
  • $\begingroup$ check this quertion $\endgroup$ – Nikos M. Jun 24 at 16:31
  • 1
    $\begingroup$ @NikosM. A “weak rref” is not an RREF. You need to at least clear the other entries from the pivot columns, which should always be possible even with integer arithmetic. From there you can pick off basis vectors much as above, but with an extra scale factor given by the pivot. Or, solve the system of diophantine linear equations that your reduced matrix represents. That’s essentially what’s going on here, as mentioned near the top. $\endgroup$ – amd Jun 24 at 16:54
  • 1
    $\begingroup$ @NikosM. Great! Scale all of the rows so that the pivots are all equal to $m$, the LCM of the pivots in your integer rref. You can then read off the basis vectors in the same way as above, but using $-m$ instead of $-1$ (or $m$ instead of $1$, depending on which version of the method you’re using). Per the third paragraph, you’re essentially solving a system of equations of the form $mx_i+b_i=0$. Reduce each vector thus produced to “lowest terms” by dividing through by the GCD of its element afterwards, if you like. I’ll leave optimizing these computations to you. $\endgroup$ – amd Jun 24 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.