Updating the null space of a matrix I am facing a problem where I have to find any (nontrivial) vector x such that Ax=0, where A is a rectangular nxm matrix with m>n, so the problem is underdetermined. I must find this x for A, but also for a new matrix A' = (A with the column j removed), and so on...
It would be very helpful to find a way to obtain the new solution x' for the matrix A' knowing the solution x for A without recomputing a whole null space by SVD or QR at each iteration. I managed to find x' with a Newton Raphson method (as x' is close to x with the element j removed), but I have that problem of inverting the Jacobian matrix at each iteration once again.
 A: There is literature on updating various matrix factorizations under rank-1 modifications (which includes row/column insertions and removals). See for instance Secton 6.5 on Golub--Van Loan 4th edition. In particular, QR updating is already implemented in Matlab and Scipy. I am not familiar with updates of the SVD, but a Google search for "svd update" returns various articles that treat this exact problem.
You will probably want to make sure that the factorization you update is a rank-revealing one; note that QR without column pivoting does not always work: there are counterexamples where all the diagonal entries of $R$ are large, but the matrix is numerically singular. For a specific example, see for instance Golub--Van Loan, 4th ed, sec. 5.4.3: there is an example of a 300x300 upper triangular matrix where the smallest diagonal entry is $\approx 0.05$, and yet the matrix has a singular value $\approx 10^{-19}$.
A: One way to compute a particular vector that solves such an undetermined system is to perform gaussian elimination and compute the row echelon form. If you then eliminate one column from the leading columns - the one's with 0's you can simply update the form with a few more operations and quickly update your solution.
Note that removing a column could require an update in most elements of your solution. For example if you have the following matrix with solution $(1,1,1,-1,0)$ then if you remove the first column the solution becomes $(0,0,0,1,-1)$ which is unique up to multiplication by a non-zero scalar.
$$\left[ \begin{array}{ccccc}
1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1
\end{array} \right]$$
