# Positive solutions of linear Diophantine equations

Let $A$ be a non-negative integer $k\times n$-matrix (i.e. each entry is non-negative and integer) with $rank(A) = k < n$. Let $b$ be a $k$-dimensional vector with positive integer entries. Consider a system of linear Diophantine equations $Ax = b$ and suppose that there exists an integer solution of these system. I'm interested in the following question. Are there conditions on $b$ that would guarantee the existence of a non-negative integer solution of $Ax = b$? Is it enough to take each entry of $b$ sufficiently large?

I suppose the answer to this question has been known for a long time. Unfortunately, I'm not an expert in this area so I would be thankful for any help or references.

-
I don't think that the problem is specially treated (some time ago I had a related one and nobody could suggest something concrete). You can write a general solution in the form $x_0+Ct$ where $x_0$ is a fixed solution and $Ct$ ($C$ a matrix and $t$ run over $\mathbb Z^l$) is a general solution of $Ax=0$. Then the required nonnegativity poses conditions on components $x_0+Ct$ (linear programming?). Since $x_0$ depends on $b$, you might be able to verify you expectation about large entries of $b$. –  Wadim Zudilin May 9 '10 at 8:11
There is a detailed discussion of your question in Section 6.5 of Alphonsin's book "The Diophantine Frobenius Problem" –  SJR May 9 '10 at 8:57
@SJR: Thanks for the tip, I'll check whether it really covers the general matrix case, not only $k=1$ as in Pete Clark's solution below. –  Wadim Zudilin May 9 '10 at 9:03
It seems to me that the theorem discussed in Section 6.5 of Ramirez-Alfonsin's book is not directly relevant to the question at hand. For instance, the matrix in Sergei Ivanonv's answer below satisfies the determinant condition (6.7) and thus admits a "pseudo-conductor". But this does not mean that every $b$ with sufficiently large coordinates is represented by non-negative integers. –  Pete L. Clark May 9 '10 at 9:44
Right: Thanks to Sergei Ivanov we can forget the "sufficiently large coordinate" idea. BUT -- The relevance of Ramirez-Alfonsin is that under some circumstances, we get a whole cone of representable b's. –  SJR May 9 '10 at 13:25

No, being large component-wise is not enough. Consider the system $$\begin{cases} 2x+y+z = b_1 \\ x+2y+z=b_2 \end{cases}$$ If $x,y,z\ge 0$, then obviously $b_2\le 2b_1$. So, for $b=(N,3N)$ there are no nonnegative solutions. But there are integer solutions, e.g. $x=0$, $y=2N$, $z=-N$.

-
Agreed. My intuition about what was happening over the real numbers was flawed. It should still be true that for a fixed coefficient matrix, there exists a constant $C$ such that if the $n-k$-dimensional volume of the real solution space intersected with the positive orthant is greater than $C$, there exists a positive integer solution. –  Pete L. Clark May 9 '10 at 9:25
@Sergei: +1. Nevertheless the question "Are there conditions on $b$ that would guarantee the existence of a non-negative integer solution of $Ax=b$?" remains. –  Wadim Zudilin May 9 '10 at 9:49

Look at http://arxiv.org/abs/0911.4186 On Feasibility of Integer Knapsacks Authors: Iskander Aliev, Martin Henk

-

Just some comments that are well-known in the theory of toric varieties (and no doubt to other areas as well). What we are asked to determine is membership in a finitely generated submonoid $\Gamma$ of $\mathbb N^k$ with more than $k$ generators. The last condition is is a red herring, we can always replace $\mathbb R^k$ by the vector space spanned by the vectors (and the price of possibly replacing $\mathbb N^k$ by some uglier monoid but as we shall see $\mathbb N^k$ will quickly exit the picture).

The first question (which is part of the assumptions of the question) is whether it lies in the subgroup $N$ generated by the same elements. Provided this has a positive answer the next question is whether it lies in the saturation of $\Gamma$, i.e., the submonoid $\Gamma'$ of elements $x$ of $N$ for which $mx\in\Gamma$ for some integer $m>0$. The point about asking this question is that is much easier to answer: The saturation is the intersection of $N$ with the real (or rational) cone spanned by the original vectors. Duality for cones implies that such a cone is the intersection of a finite number of rational half hyperplanes (which can be reasonably efficiently be determined from the original generators, see for instance Ziegler: Lectures on polytopes) and thus that condition can be checked rather easily.

[[ Correction: I claimed that $\Gamma'\setminus\Gamma$ is finite which is wrong. ]]

The step from $G'$ to $G$ can also be quite tricky. It is a fact that $G'$ is finitely generated as $G$-module, i.e., there are $x_1,x_2,¼,x_mÎG'$ such that $G'=È_i(G+x_i)$ but the complement $\Gamma'\setminus\Gamma$ may be infinite. An example is given by the monoid generated by $(0,2)$, $(0,3)$ and $(1,0)$ where $(m,1)$ is not in the monoid genated by then but $2(m,1)$ always is.

The relation between $G$ and its saturation can be described in terms of commutative algebra as follows. Consider the monoid algebra $k[G]$, where $k$ is some field. The inclusion $GÍG'$ gives an algebra inclusion $k[G]Ík[G']$ and it makes $k[G']$ the normalisation of $k[G]$ (this gives one way of showing that $G'$ is finitely generated as $G$-module as the same is true for the normalisation). The question of whether $\Gamma'\setminus\Gamma$ is finite or not then has the following interpretation. We have a grading $G®\mathbb N$ of $G$ given by $(m_i)e \sum_im_i$ which induces a grading of $k[G]$ allowing to pass to a projective variety $\mathrm{Proj}k[G]$. Then $\Gamma'\setminus\Gamma$ is finite precisely when $\mathrm{Proj}k[G]$ is normal. The example above was constructed using this; $\mathrm{Proj}k[G]$ is $1$-dimensional with a cusp and hence is not normal.

-
Great answer! To summarize: yes if b lies inside the rational cone generated by the columns of A, with finitely many exceptions (cf "Frobenius problem"). Nitpicks: your n and k have been switched viz the original formulation and "fewer than" in line 3 should have been "greater than". –  Victor Protsak May 9 '10 at 19:47
Unfortunately I made a stupid thinko and the picture is not quite as nice, see corrected answer. –  Torsten Ekedahl May 10 '10 at 4:41
Good, because I was worried that I couldn't see why the complement were finite. –  Victor Protsak May 10 '10 at 21:24

"DUALITY AND A FARKAS LEMMA FOR INTEGER PROGRAMS" JEAN B. LASSERRE http://www.optimization-online.org/DB_HTML/2003/04/646.html

This paper considers positive solutions by either computing a Groebner basis or by solving a (continuous) LP

I might add though that there is exponential blowup in the number of variables in the new LP

-