Kernel vectors with given number of non-zero entries?

Question

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?

Answer 1

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.