Finding the sparsest solution to a system of linear equations How hard is it to find the sparsest solution to a system of linear equations?

More formally, consider the following decision problem:

Instance: A system of linear equations with integer coefficients and a number $c$.

Question: Does there exist a solution to the system with at least $c$ variables assigned to zero?

I'm also trying to determine what the dependence is on $c$.  That is, maybe the problem is FPT with parameter $c$.

Any ideas or references are really appreciated.
Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$ 

Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn \times (kn+m)$ matrix, $\tilde{x}$ is now a $(kn+m)$ dimensional vector, and $\tilde{b}$ is a $kn$ dimensional vector:

$$\tilde{A} = \begin{bmatrix}
 A &amp; I_n &amp; &amp;  &amp; \\
 &amp; I_n &amp; -I_n &amp; &amp; \\
 &amp; &amp; I_n &amp; -I_n &amp; \\
 &amp; &amp; &amp; \ddots &amp;\ddots  \\
 &amp; &amp; &amp; &amp; I_n &amp; -I_n \\
\end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$
where $I_n$ is the $n \times n$ identity matrix.

Note that this system is always satisfied by the vector $\tilde{x} = \begin{pmatrix} 0 &amp; b &amp; b &amp; \cdots &amp;  b \end{pmatrix}^T$. In fact, the first $m$ entries of $\tilde{x}$ can be arbitrary, and there is some solution vector with that prefix.

I now claim that $\delta$ fraction of equations of $Ax=b$ are satisfiable iff there exists a sparse solution of $\tilde{A}\tilde{x}=\tilde{b}$ which has at least $\delta nk$ zeros. This is because every satisfied row of $Ax=b$ yields $k$ potential zeros when $x$ is extended to $\tilde{x}$

Thus, if we find the sparsity of the sparsest solution to $\tilde{A}\tilde{x}=\tilde{b}$, we have also maximized $\delta$, by dividing the sparsity by $k$. 

Therefore, I believe your problem is NP-hard.