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!

  • 2
    $\begingroup$ $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. $\endgroup$ – Will Sawin Jul 6 '12 at 23:07
  • $\begingroup$ @WillSawin The example of the equation $px=p^2$ shows that congruences modulo primes are not enough to check the existence of a solution. $\endgroup$ – 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).

  • $\begingroup$ 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? $\endgroup$ – Vidit Nanda Jul 7 '12 at 5:11
  • 2
    $\begingroup$ Igor, you probably meant Hermite n.f., not Smith n.f. Vel, see my comment for a reference to details on this. $\endgroup$ – Dima Pasechnik Jul 7 '12 at 5:28
  • 3
    $\begingroup$ @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. $\endgroup$ – Igor Rivin Jul 7 '12 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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