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 0.00001% of the entries are nonzero), with $n \approx 10^{10}, 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.

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.

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 0.00001% of the entries are nonzero), with $n \approx 10^{4}, m \approx 10^{10}$, 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.

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 0.00001% of the entries are nonzero), with $n \approx 10^{10}, 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.