<p>This is NP-hard, by reduction from ILP feasibility.  Deciding feasibility of an ILP instance is NP-hard, so your problem is, too.</p>

<p>You can convert each inequality <span class="math-container">$a_1 x_1 + \dots + a_n x_n \ge b$</span> into an equality using a <a href="https://en.wikipedia.org/wiki/Slack_variable" rel="nofollow noreferrer">slack variable</a> <span class="math-container">$s \ge 0$</span>:</p>

<p><span class="math-container">$$a_1 x_1 + \dots + a_n x_n - s = b.$$</span></p>

<p>You can arrange for all variables to be non-negative by defining <span class="math-container">$x_i = x_i^+ - x_i^-$</span> where the variables <span class="math-container">$x_i^+,x_i^-$</span> are non-negative and replacing each <span class="math-container">$x_i$</span> with <span class="math-container">$x_i^+ - x_i^-$</span>.</p>

<p>This transformation turns a system of <span class="math-container">$m$</span> linear inequalities in <span class="math-container">$n$</span> integer variables into a system of <span class="math-container">$m+n$</span> linear inequalities in <span class="math-container">$2n+m$</span> non-negative integer variables.  Thus the result has exactly the form of your problem.</p>

CC BY-SA 4.0
2020-04-02T05:40:51.780Z
2020-04-02T05:40:51.780Z
D.W.
<p>Let <span class="math-container">$A$</span> be an <span class="math-container">$n \times m$</span> integer matrix and consider the system of equations <span class="math-container">$Ax = b$</span> where <span class="math-container">$b$</span> is an integer vector. I want to find a solution <span class="math-container">$x$</span>, assuming one exists, such that the components of <span class="math-container">$x$</span> are non-negative integers.</p>

<p>What is the complexity of this problem? Is there a known algorithm that finds such a solution, or returns false if none exist?</p>

CC BY-SA 4.0
2020-04-02T03:45:31.407Z
It came up studying another problem on simplicial complexes. In this case $A$ is the boundary matrix and I am looking for a chain with non-negative coefficients whose boundary is $b$. It didn't seem straightforward to me, could you elaborate on why you think it is?
Will
<ds.algorithms><linear-algebra><matrices>
Finding a non-negative solution to an integer system of linear equations
Will
# Finding a non-negative solution to an integer system of linear equations

(Asked by: username_0 on 2020-04-02)

Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $x$ are non-negative integers.

What is the complexity of this problem? Is there a known algorithm that finds such a solution, or returns false if none exist?

**Tags:** ds.algorithms, linear-algebra, matrices
> **Comments:**
> **username_0**: It came up studying another problem on simplicial complexes. In this case $A$ is the boundary matrix and I am looking for a chain with non-negative coefficients whose boundary is $b$. It didn't seem straightforward to me, could you elaborate on why you think it is?  

---

## 1 answers

### Answer by username_1 on 2020-04-02. Score: 1

This is NP-hard, by reduction from ILP feasibility. Deciding feasibility of an ILP instance is NP-hard, so your problem is, too.

You can convert each inequality $a\_1 x\_1 + \dots + a\_n x\_n \ge b$ into an equality using a [slack variable](https://en.wikipedia.org/wiki/Slack_variable) $s \ge 0$:

$$a\_1 x\_1 + \dots + a\_n x\_n - s = b.$$

You can arrange for all variables to be non-negative by defining $x\_i = x\_i^+ - x\_i^-$ where the variables $x\_i^+,x\_i^-$ are non-negative and replacing each $x\_i$ with $x\_i^+ - x\_i^-$.

This transformation turns a system of $m$ linear inequalities in $n$ integer variables into a system of $m+n$ linear inequalities in $2n+m$ non-negative integer variables. Thus the result has exactly the form of your problem.


---

