[Math] Positive solutions of linear Diophantine equations

linear algebramatricesnt.number-theory

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.

Best Answer

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

Related Question