Can you direct get the Basis of the Null Space just from rref

linear algebra

https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-7-solving-ax-0-pivot-variables-special-solutions/

In this lecture, from 29:45 to 34:00. Gilbert describes a way used by Matlab to form the Null Space from the rref for any matrix.

all matrix can be reduced to $$ R =\begin {bmatrix} I&F \\0&0 \end{bmatrix}$$ thus RN =0： $$ N =\begin {bmatrix} -F\\I \end{bmatrix}$$ but in practice, R is mixed with I and F, the above is the re-ordered form.

I find out that unless when matrix are exactly in the form of (no re-ordering occurs)
$$ R =\begin {bmatrix} I&F \\0&0 \end{bmatrix} $$

I cannot get the N directly from RREF.

The questions is how can this algorithm be applied to general problems, or am I understanding Prof Gilbert in a wrong way.

Best Answer

You are correct in stating that the formula given only (directly) applies in the case that the pivot columns are all to the left and the free columns are to the right, which is to say that "$R$ is mixed with $I$ and $F$".

Of course, it is possible to find the nullspace by solving the system $Rx = 0$. However, for a generalization of Strang's block-matrix approach, we could proceed as follows:

It is possible to rearrange the columns of $R$ so that the pivot columns are on the left and the free columns are on the right. Accordingly, there is a permutation matrix $P$ such that $$ RP = \pmatrix{I & F\\0 & 0}. $$ Let $N_1$ denote the matrix $$ N_1 = \pmatrix{-F\\I}. $$ The columns of $N_1$ form a basis for the nullspace of $RP$. It follows that the columns of $N = PN_1$ forms a basis of the nullspace of $R$. I suspect that matlab does something similar to this.

Here is an implementation of this method written in Matlab, with Matlab's built-in process called for comparison.

% enter matrix here
A = [1,2;3,4;5,6]*[1,-1,0,1;0,0,1,-1];

[m,n] = size(A);
[R,p] = rref(A);
r = length(p);
f = setdiff(1:n,p);
N = zeros(n,n-r);
N(p,:) = -R(1:r,f);
N(f,:) = eye(n-r);

disp('starting matrix:')
disp(A)
disp('RREF:')
disp(R)
disp('nullspace matrix:')
disp(N)
disp('null(A,''r''):')
disp(null(A,'r'))

And the resulting output:

starting matrix:
     1    -1     2    -1
     3    -3     4    -1
     5    -5     6    -1

RREF:
     1    -1     0     1
     0     0     1    -1
     0     0     0     0

nullspace matrix:
     1    -1
     1     0
     0     1
     0     1

null(A,'r'):
     1    -1
     1     0
     0     1
     0     1
Related Question