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

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.

• Are you ok with numerical methods, i.e. giving a non-proved result? Or do you need a cetified algorithm? In the first case, it seems to me that Householder method (for getting the QR decomposition) would be the way to go. Its nominal complexity is of the order of $n^2 m$, which is $10^{18}$ here; I would expect the sparsity to help at least by a $10^5$ factor, maybe more, which would make it very reasonable. Apr 1, 2015 at 12:26
• QR seems out of question to me. Its result typically is a dense, floating-point number matrix, which would require 800 Terabytes only to store it. Apr 1, 2015 at 13:51
• Also, the numbers given in the question sound strange. If I am not mistaken with the computations, 0.00001% of nonzeros means that there are $10^7$ nonzeros in the matrix overall, one every 1000 rows. Is that the case? Would it make sense to prune out the zero rows first? Apr 1, 2015 at 13:55

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.
• Any goals for finding a $B$ that makes the following computations easier? Apr 2, 2015 at 2:06
• Actually maybe using $A^T$ makes sense here. Since $A^T A$ is positive semi definite, I can calculate and store the Cholesky decomposition $LU = A^T A$. Since $m \approx 10^4$, storing $L$ and $U$ is on the order of 1GB, which is feasible. Then forward-backward substitution lets me solve $A^T A = LU = A^T e_k$ for each value of $k \in 1 \ldots n$. Would still love an answer that lets me know if a solution exists without having to go through the full expense of calculating the exact solution itself. Apr 2, 2015 at 18:54