This is a very fast method for computing the kernel/nullspace and image/column space of a matrix. I learned this from my linear algebra teacher but I haven't seen it mentioned online apart from this reference in wikipedia.

The method is as follows: If $A$ is a m × n matrix, we construct $\displaystyle\left[\frac{I}{A}\right]$, where $I$ is the n × n identity matrix.

We then do elementary column operations until our $A$ is in column echelon form and we get the augmented matrix $\displaystyle\left[\frac{C}{B}\right]$. A basis of the kernel of $A$ consists in the columns of $C$ such that the corresponding column of $B$ is a zero column. A basis for the image of $A$ consist of all the non-zero columns of $B$.

An example:

$A = \begin{pmatrix} 4 & 1 & 3 \\ 2 & -1 & 3 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

$\displaystyle\left[\frac{I}{A}\right] = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline 4 & 1 & 3 \\ 2 & -1 & 3 \\ 2 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ $\to$ $\begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline 4 & 1 & -1 \\ 2 & -1 & 1 \\ 2 & 1 & -1 \\ 1 & 1 & -1 \end{pmatrix}$$\to$ $\begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \hline 4 & 1 & 0 \\ 2 & -1 & 0 \\ 2 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix}$

So a basis for $ Ker(A) = \begin{pmatrix} -1 \\ 1 \\ 1 \end{pmatrix}$

And a basis for $ Im(A) = \begin{pmatrix} 4 \\ 2 \\ 2 \\ 1 \end{pmatrix},\begin{pmatrix} 1 \\ -1 \\ 1 \\ 1 \end{pmatrix}$.

My problem is that I don't understand fully why this method works. From the wikipedia article I learned this derives from Gaussian Elimination, which sort of makes sense to me as it is similar to the method for finding the inverse of a matrix using Gauss-Jordan Elimination. So my question is: Why does this work?

up vote 0 down vote accepted

The image of $A$ is precisely the column space of $A$, that is, the vector space spanned by the columns of $A$. Performing column operations does not change the column space of $A$ (see below), so the nonzero columns in the echelon form are a basis for the column space of $A$ (and, hence, for the image of $A$).

A vector $(b_1,\dots,b_n)$ is in the nullspace of $A$ precisely when $b_1C_1+\cdots+b_nC_n=0$, where $C_1,\dots,C_n$ are the columns of $A$. The column operations you are doing are forming linear combinations of the columns of $A$, and the top part of your augmented matrix is keeping track of the coefficients of those linear combinations. So when you get a zero column, the entries above it are the coefficients of a vanishing linear combination of the columns of $A$; they form an element of the nullspace.

"Performing column operations does not change the column space of $A$." There are three kinds of elementary column operation. You just have to check that for each of these three types, performing it does not change the column space.

  • 1
    Thanks a lot. I found the part about the nullspace especially useful. – Gonate Dec 10 '14 at 8:30
  • It appears that you have unaccepted my answer. Of course it's your perfect right to do so, but if there is something I can do to improve my answer, please let me know. – Gerry Myerson Jan 22 '15 at 14:49
  • I came back to this question and I realized I still didn't understand it completely. I unaccepted with the hope that something else could come out of this thread. If you would like to add further clarifications I'll be very grateful! – Gonate Jan 23 '15 at 11:14
  • Well, you'll have to meet me halfway. What don't you understand? What would you like me to clarify? – Gerry Myerson Jan 23 '15 at 13:53
  • 1
    Hi, sorry for the late reply, I was on break. I was thinking about this thing and I now see that your explanation is pretty spot-on. I think that what confused me the most was the augmented matrix and what role it played, I really didn't understand how it could keep track of the changes. It is quite easy actually. – Gonate Jan 26 '15 at 15:08

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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