I have a dense matrix and a set of rows. I would like to check if adding any single row from the set to the original matrix would make the new matrix rank deficient. Right now I am doing a full LU decomposition each time. This feels wasteful, and I have a hunch that I should be able to keep some information between iterations. Does anyone know of a way to speed this up?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I will assume the original matrix has $n-1$ rows, $n$ columns, and the rows are linearly independent (this is easy to check; and if it is not the case, then the problem is trivial).
Adding a new row $r$ will leave the matrix rank-deficient if and only if $r$ can be expressed as a linear combination of the existing $n-1$ rows. So, in a precomputation stage, use Gaussian elimination on the existing matrix. Then, it is easy to test whether any new row can be expressed as a linear combination of the existing rows. This will be much faster than doing one LR decomposition per row.
$\begingroup$
$\endgroup$
It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$.
In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if adding any $x$ to the columns of $A$ would increase its rank. Then compute $P = A(A^T A)^{-1} A^T$ once. Here, $P$ projects any vector $x$ onto the column space of $A$, which is the row space of your original dense matrix $A^T$.
Alternatively, you can factor $A = QR$ using either Gram-Schmidt or Householder, in which case you would have $P = QQ^T$.
Then, for every $x$, concatenating it onto the columns of $A$ would increase its rank if and only if $Px \neq x$.
