I have a following problem that I am stuck on and not sure how to proceed. Any suggestions are really appreciated.
Given a non-square $m \times n$ matrix $A = [M | I ],$ I order the columns of $A$ with COLAMD and pick the first $m$ columns from the COLAMD ordering to form a basis $m\times m$ matrix $B$.
Often it happens that the $rank(B) < m,$ and I'd like to repair the basis matrix $B$ by replacing the columns of $B$ with columns from $I$ that is part of $A$. When doing so I'd like to replace the minimum number of columns of B to preserve most of the COLAMD ordering to preserve the fill-in reducing properties.
I tried the obvious and computed the null space of B and used the resulting vectors to find out linearly dependent columns and replaced them one by one with columns from the standard basis. However, very often it leads to $B = I$ which is not what I want.
Is there a good and relatively easy to implement method for approaching this kind of problem?
Thank you for reading.