1
$\begingroup$

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?

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.