In response to this question Kernels and reduced row echelon form - explanation, a very clear method is given for how to read a basis for the kernel of a matrix directly from that matrix in reduced row echelon form. However, there's one step which I don't quite understand the reasoning behind, and I was wondering if anyone could shed some light on the matter.

The user AMD says: "...For each of these vectors, set one of the components that correspond to these pivotless columns to 1 and the rest to 0." I understand what this means and once this step is taken the reasoning for everything else done is completely clear. I just don't understand why we know that this is the right step to take despite extended consideration of the matter.

Thanks in advance!


Computing the RREF $B=SA$ of the $m\times n$ coefficient matrix $A$ transforms the system of equations into an equivalent one in which $r=\operatorname{rank}(A)$ of the variables $x_i$—those that correspond to pivot columns—appear in a unique equation, so their values are completely determined by the non-pivot variables that appear in the corresponding equation. We therefore choose those non-pivot variables as the free variables of the system. Setting all of the free variables to zero forces the pivot variables to zero as well, so any non-trivial solution of this homogeneous system must have at least one non-zero value among the free variables. We need $m-r$ linearly independent solutions, and there just happen to be exactly that many free variables available, so by setting each of these variables in turn to $1$ and holding the rest at $0$, we can produce $m-r$ elements of $\mathbb R^m$ that are guaranteed to be linearly independent. The equations that result from doing this are all of the form $x_i+b=0$, where $x_i$ is one of the pivot variables, which give us the values of the remaining components of the vector.

Taking the second example from the answer to the linked question, the reduced system is $$\begin{align} x_1+2x_3-3x_4 &= 0 \\ x_2-x_3+2x_4 &= 0.\end{align}$$ The first and second columns have pivots and sure enough $x_1$ and $x_2$ each appear in a unique equation. If we try a solution with $x_3=1$ and $x_4=0$, the equations become $x_1+2=0$ and $x_2-1=0$, and for a solution with $x_3=0$ and $x_4=1$, the equations are $x_1-3=0$ and $x_2+2=0$.

Another way to look at this is in terms of completing a basis for $\mathbb R^m$. The nonzero rows of the RREF are a basis for $A$’s row space. Each of these vectors has a $1$ in a unique position that corresponds to a pivot column and zeros in all of the other pivot positions. If we extend this to a complete basis of $\mathbb R^m$, this means that the coefficients of these row space basis vectors in the expression of an arbitrary vector $\mathbf v$ in this basis are completely determined. This likely doesn’t produce the required values for the other elements of $\mathbf v$, though, but an easy way to adjust those values is to complete the basis with the standard basis vectors $\mathbf e_i$ that correspond to non-pivot positions. That is, set one of the non-pivot positions to $1$ and the rest to $0$. We also want all of these additional basis vectors to be orthogonal to all of the row space basis vectors, which we can do by filling in the pivot positions of each additional basis vector with suitable values. This doesn’t affect the linear independence of the set, so the adjusted extra vectors are a basis for the orthogonal complement of the row space, i.e., of the null space.


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.