## is there a solution to system of linear Diophantine equations?

I have a matrix A \in Z^{n \by m}, where m > n and a vector b \in Z^n. Then, under what conditions does an integer solution exist to the equation

Ax = b.

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

Essentially I want something like Siegel's lemma but for the inhomogeneous 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 at 23:07

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

-
Igor: I don't think this works since the inverse of an integer matrix need not be an integer matrix. Can you elaborate on your solution? – Vidit Nanda Jul 7 at 5:11
Igor, you probably meant Hermite n.f., not Smith n.f. Vel, see my comment for a reference to details on this. – Dima Pasechnik Jul 7 at 5:28
@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 at 13:29

Thanks! This is very helpful. --SAK

-
 Dear SAK, I've merged your accounts. If you register, you won't have to worry about unintentionally creating new accounts. – S. Carnahan♦ Jul 11 at 4:51