7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ May 9, 2010 at 8:11
  • 1
    $\begingroup$ There is a detailed discussion of your question in Section 6.5 of Alphonsin's book "The Diophantine Frobenius Problem" $\endgroup$ May 9, 2010 at 8:57
  • $\begingroup$ @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. $\endgroup$ May 9, 2010 at 9:03
  • $\begingroup$ 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. $\endgroup$ May 9, 2010 at 9:44
  • $\begingroup$ 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. $\endgroup$ May 9, 2010 at 13:25

4 Answers 4

11
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 9, 2010 at 9:25
  • $\begingroup$ @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. $\endgroup$ May 9, 2010 at 9:49
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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". $\endgroup$ May 9, 2010 at 19:47
  • $\begingroup$ Unfortunately I made a stupid thinko and the picture is not quite as nice, see corrected answer. $\endgroup$ May 10, 2010 at 4:41
  • $\begingroup$ Good, because I was worried that I couldn't see why the complement were finite. $\endgroup$ May 10, 2010 at 21:24
0
$\begingroup$

"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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.