How to compute null spaces iteratively ?

Assume I have two vectors in . For simplicity I will assume also n = 4 and have the following vectors,

a1 = [1 1 2 -1] and a2 = [2 0 3 -1] .

Then the following matrix will be formed

C = [a1 ; a2];

It is easy to find an orthonormal basis for the null space of C by just having the following code in MATLAB,

null(C)

If I add one more vector such as a3 = [3 5 6 -1] (lin. ind. from a1 and a2) to my C matrix, is there any way to compute the new orthonormal basis for the new C by using the previously found orth. basis ?

I am asking this to find out is there any way to compute the orth. basis for the iteratively expanding C matrix.

Because when n becomes larger, it will be harder to find out the orth. basis for the null space of expanding C matrix.

A QR Decomposition method also be appreciated.

Answer 1

[Shantanu Dixit]

Hi Steve,

You can update the null space iteratively using the previous computed basis. Suppose if there is already a computed orthonormal basis 'Q0' for the null space of the initial matrix C (with rows a1, a2) i.e

Q0 = null(C);

When an additional row is added to the matrix, any vector x in the null space of the new matrix must satisfy both:

• , and
• 

Since , we can express any such 'x' as: , for some vector 'y'. Substituting this into the second condition gives:

Which points that y should lie in null space of ''. Therefor the null space of the updated matrix is given by: ''

You can refer to the below MATLAB snippet to implement this programatically:

C = [1 1 2 -1; 2 0 3 -1];
Q0 = null(C);   % Orthonormal basis for the null space of C

a3 = [3 5 6 -1];
N_update = null(a3 * Q0);

% New null space basis for [C; a3]
Q_new = Q0 * N_update;

Additionally, you can also refer to the self-paced course on Linear algebra using MATLAB by MathWorks:

https://matlabacademy.mathworks.com/details/introduction-to-linear-algebra-with-matlab/linalg

Hope this helps!