I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e., is obtained by deleting one column from Z. Similarly, if one row of A is deleted (resulting in A_d), the basis for A_d will be Z plus one new column. I am willing to compute the Z from scratch each time a row of A is added or deleted, or use an updating method, as long as I achieve the properties stated. You can assume m <= n and A is always of full row rank, i.e., rank(A) = m.
I am not worried about finding the most computationally efficient way of doing this (but all else equal, computational efficiency is good). Note that use of the MATLAB null(A), which is based on SVD, does not achieve this. Picking the last n-m columns of Q in the QR factorization of A' also does not achieve this, even though both of these methods produce a valid nullspace basis Z.
It is doable. How do I know? Because it was figured out more than 40 years ago, and is used in various optimization software. See, for instance, section 5, and in particular, section 5.2 of http://web.stanford.edu/group/SOL/papers/ggms74.pdf ; note that what are referred to as columns of A in that paper correspond to rows in my description, since the A in the paper is A' in my question. However, I've never seen the (a) method for doing this described clearly and understandably (to include that paper), more along the lines of employing a sequence of Householder transformations to annihilate certain elements, thereby updating a previous basis Z. See section 5.2.4.1 on p. 172 of http://www.amazon.com/Practical-Optimization-Philip-E-Gill/dp/0122839528 (the page in question is only available in the hard copy book, unless you get lucky). However, I believe the authors were interested in the most efficient implementation, not the easiest to implement.
I need this in order know how to transform a Quasi-Newton Hessian projected into the nullspace of A, i.e., Z' * Hessian * Z, to be projected into the new nullsapce corresponding to a row being deleted or added to A. That way I don't have to throw out the entirety of my Quasi-Newton approximation when a row goes into or out of A, and can either project my existing projected Hessian into the lower dimensional space when adding a row to A (for instance, by removing the corresponding row and column from my existing projected Hessian), or know where to add a an initialized (e.g., identity) row and column to my existing projected Hessian when deleting a row from A.
This scenario would arise, for instance, when the working set in a nullspace active-set Sequential Quadratic Programming algorithm using Quasi-Newton approximation to the projected (a.k.a. reduced) Hessian, changes. See the bottom half of p. 15 (you may have to read earlier sections to understand this though) of http://web.stanford.edu/class/msande312/restricted/mse312proj2008_3.pdf for the context I am talking about. I.e., updating a projected (a.k.a. reduced) Quasi-Newton Hessian approximation when the nullspace into which the Hessian is being projected, changes due to change in working set.
Thanks.
Note: This is an expanded write up with more references of a question which was asked at https://math.stackexchange.com/questions/1322626/determining-nullspace-basis-such-that-only-one-column-is-deleted-or-added-as-row , but received no responses. Now I realize that this board is more appropriate than the one on which I originally posted for problems which are not homework assignments.
