6
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 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, 2012 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, 2016 at 18:32

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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, 2012 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, 2012 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, 2012 at 13:29

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.