# Let R L S ( k ) be the problem where we try to determine whether a Linear Syste

Let $RLS\left(k\right)$ 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=\left({x}_{1},{x}_{2},\dots ,{x}_{n}\right)$ such that at most $k$ of the ${x}_{i}$'s are non-zero.
Prove that $RLS\left(k\right)$ is NP-hard
You can still ask an expert for help

## Want to know more about Inequalities systems and graphs?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

We can reduce 1-IN-3SAT to $RLS\left(k\right)$ as follows:
Suppose that we have a 1-IN-3SAT formula in $n$ variables $\left\{{b}_{1},\dots ,{b}_{n}\right\}$.
- For each boolean variable ${b}_{i}$, define two rational variables ${x}_{i}$ and ${x}_{i}^{\prime }$ and add the constraint ${x}_{i}+{x}_{i}^{\prime }=1$.
- For a clause with positive literals $\left\{{b}_{i},{b}_{j},{b}_{k}\right\}$, add the constraint ${x}_{i}+{x}_{j}+{x}_{k}=1$.
- When a negative literal $\mathrm{¬}{b}_{i}$ occurs in a clause, use ${x}_{i}^{\prime }$ instead of ${x}_{i}$.
- Require that at most $n$ rational variables (out of $2n$) can be nonzero.
From the constraint ${x}_{i}+{x}_{i}^{\prime }=1$, we know that at least one of ${x}_{i}$ and ${x}_{i}^{\prime }$ has to be nonzero for every $i,$ which is already $n$ nonzero variables. That means exactly one of ${x}_{i}$ and ${x}_{i}^{\prime }$ can be nonzero, which means either ${x}_{i}=1$ and ${x}_{i}^{\prime }=0$, or ${x}_{i}=0$ and ${x}_{i}^{\prime }=1$. Interpret this as a truth assignment for ${b}_{i}$: ${x}_{i}=1\phantom{\rule{thickmathspace}{0ex}}⟺\phantom{\rule{thickmathspace}{0ex}}{b}_{i}$ and ${x}_{i}^{\prime }=1\phantom{\rule{thickmathspace}{0ex}}⟺\phantom{\rule{thickmathspace}{0ex}}\mathrm{¬}{b}_{i}$. Then the constraint we use for each clause is equivalent to saying that exactly one literal in the clause is true.
Therefore a solution to the rational linear system produces a satisfying assignment to the 1-IN-3SAT formula.