Matrix rank only adding single row
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$.