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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 7, 2012 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .