Let $A$ be a $n\times n$ real matrix. Is there a vector $\vec x \in \mathbb{R}^n$ with exactly $0 \le k < n$ zero entries such that $A \vec x = 0$?


Is there an efficient algorithm to tackle this question?



Kernel vectors with given number of non-zero entries?
A first step would be to find a (nice) basis of the null space of $A$. That is easy if the matrix is in RREF. Once that is done (which would take about $n^3$ steps with a lazy algorithm), answering your question would seem easy in practice for reasonable size $n.$ However the problem is NP-complete: As $n$ grows to be enormous the number of steps required in the worst case (it is suspected) can not be be bounded by any power of $n.$


One version of the subset-sum problem is



> 
> given a set $S$ of $m$ positive integers and an integer $k$, is there a subset $T$ whose sum is exactly $k?$
> 
> 
> 


This is known to be NP-complete, there is (almost certainly) no method which ALWAYS gives the correct answer in a reasonable amount of time.


Let $S=\{s\_1,s\_2,\cdots,s\_m\}$ and the sum of the $s\_i$ be $n.$ Unless both $m$ and $n$ are quite large the problem should be easy.


To translate subset sum to your problem, let $A$ be a matrix made of $m$ square blocks along the diagonal. Block $i$ is $s \times s$ for $s=s\_i$ with $1$’s everywhere except diagonal entries $1-s.$ Then a vector is in the null space of $A$ exactly if the first $s\_1$ entries are equal to each other and the next $s\_2$ are equal to each other. Etc.


Actually, the subset-sum result might be in terms of $m.$ However, this shows that even in a case where $A$ is extremely simple and the null space is obvious, your question might be difficult to answer.


