# 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 '15 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 '15 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 '15 at 13:55

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.

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

• Any goals for finding a $B$ that makes the following computations easier? Apr 2 '15 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 '15 at 18:54