# is there a solution to this linear Diophantine system?

I have a matrix $A \in \mathbb Z^{n \times m}$, where $m > n$, and a vector $b \in \mathbb Z^n$. Under what conditions does

$$Ax = b$$

have an integer solution? Is there a way to bound the norm of the solution vector $x$ in terms of the norms of $A$ and $b$?

Essentially, I want something like Siegel's lemma, but for the non-homogeneous case.

I am not an expert on this and will appreciate any help. Thanks!

• $A$ gives a map from $\mathbb Z^n$ to $\mathbb Z^m$. To check existence of a solution, you first want to know the cokernel of this map. You can compute the size of this cokernel by taking the greatest common divisor of the $m\times m$ minors. To check if there is a solution, you just need to check modulo all the primes dividing this. Since that is over a field you can use standard linear algebra. I don't know how to find out how far away the closest root is from the origin. – Will Sawin Jul 6 '12 at 23:07
• @WillSawin The example of the equation $px=p^2$ shows that congruences modulo primes are not enough to check the existence of a solution. – ACL May 30 '16 at 18:32

This kind of questions arise very often in integer linear optimization. It is well-known that the bitsize of a solution will be polynomially bounded by the sizes of of $A$ and $b$, i.e. by the maximum bitsize of entries of $A$ and $b$, and by $\max(n,m)$. See e.g. Corollary 5.2a in the A.Schrijver's book.
There are many sufficient conditions known for the existence of an integer solution, e.g. $A$ being totally unimodular (i.e. each square submatrix has determinant 0,1,or -1) is one.
Your problem is in fact easier (in optimization one often assumes $x\geq 0$), and Will gives a good suggestion in his comment above. The book in Sect. 5.3 also gives more details on the algorithm Igor described in his answer.
I don't know the answer to the second question (bounding the norm), but for the first, just compute the Smith normal form of A (and transform $b$ appropriately).
• @Vel: I dont understand you comment. The "conjugating" matrices in SNF are invertible over $\mathbb{Z}$. So, if $M D N = A,$ then $A x = b$ can be written as $D (N x) = M^{-1} b,$ from which the existence or lack thereof to the original system is clear. – Igor Rivin Jul 7 '12 at 13:29