Solving $Ax=e_k$ for standard basis vector $e_k$, sparse $A$

Question

Given a sparse matrix $A \in \mathbb{R}^{n \times m}$, are there any efficient methods for determining whether there exists an $x \in \mathbb{R}^m$ such that

$Ax=e_k$,

the $k^{th}$ standard basis vector? I do not need to know what $x$ is, only if such an $x$ exists for a particular $k$. I will test for every $k$, so bonus points if your method can test all values of $k$ at once. (To be clear, I do not need to know $x$, but I would like to know which $k$ admit such an $x$.)

In my application, $A$ contains only binary values, and thus $A \in \{0,1\}^{n \times m}$. $A$ is sparse (perhaps 1 ~ 10% of the entries are nonzero), with $n \approx 10^{7}, m \approx 10^{4}$, so by "efficient methods" I really mean methods that can handle this scale of matrix. That being said, even if you have a solution that doesn't seem to scale to this size, I'm still interested.

---

EDIT: Thank you @Federico for pointing out that I needed to re-examine the dimensions and sparsity of $A$. I've updated the question to correct my mistake.

Answer 1

Since m is much smaller than n, and since you have m columns, you will have at most m many values of k for which the answer is yes, there is an x for e_k. It might behoove you to go figure out the rank of A to give an upper bound. You could sort the rows by Hamming weight, remove duplicates and zero out those columns for which you have a row with only one in that column, and do partial Gram-Schmidt reductions to try to speed up the rank computation. Even after this, you only have an upper bound; the answer could be zero because every column has an even number of ones, or something similar. The main reason to have an upper bound is to help determine when to stop searching.

The problem sounds close enough to SAT that I expect no fast and complete algorithm to solve your problem.

Answer 2

Solve $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$ first, it is small enough to handle by dense methods. If there is no solution, there is also none for the original. Otherwise get an (affine) basis of the solution space of $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$; any solution of $A \boldsymbol{x}=\boldsymbol{e_k}$ is in that space. By calculating $A\boldsymbol{y}$ for each basis vector $\boldsymbol{y}$, I think you get another small set of equations for finding the coefficients for writing $\boldsymbol{x}$ in terms of the basis (maybe this part is wrong; I'm going to bed).

Actually you don't need to use $A^T$, you can use $B^T A \boldsymbol{x}=B^T\boldsymbol{e_k}$ for any convenient $B$, such as one of full rank.

This isn't very much thought out; someone will help to streamline it (or tell us it is rubbish).