Let $RLS(k)$ be the problem where we try to determine whether a Linear System of $n$ unknown variables and $m$ equations with Rational coefficients, has a $k$-solution which is basically a vector $x= (x_1, x_2, \dots, x_n)$ such that at most $k$ of the $x_i$'s are non-zero.
Prove that $RLS(k)$ is NP-hard
I am trying to reduce Vertex Cover ($VC$) to $RLS(k)$.
My idea was that starting with a graph $G(V,E)$ then one can encode each edge $(x_i, x_j)$ as $x_i + x_j \neq 0$. Reason being, if $x_i = 0$ we want $x_j \neq 0$ (i.e. if we don't "choose" vertex i for our VC then we are forced to "choose" node j for the $VC$).
We conclude, that this System has a $k$-solution iff $G$ has a Vertex Cover of size $\leq k$
Of course, the issue is that the above is NOT a system of equations but rather a system of inequalities.
I also thought about introducing dummy variables but that didn't me lead anywhere either.
Is this even the correct reduction for this type of problem? Are there any other common reductions that could potentially be straightforward? My intuition tells me that (due to the $k$-restriction) Vertex Cover and Independent Set are probably the easiest ones. Thoughts?
Update/Note: I am quite comfortable with this topic, so I am looking for some brainstorming with a fruitful discussion, and not necessarily a solution. So don't be afraid to share even "partial" ideas.