# Finding a non-negative solution to an integer system of linear equations

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?

• 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
Apr 2, 2020 at 3:45

You can convert each inequality $$a_1 x_1 + \dots + a_n x_n \ge b$$ into an equality using a 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.