Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
2  
$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
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
    
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 '12 at 5:11
2  
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 '12 at 5:28
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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