Welcome to MathOverflow

Question

2

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!

edited Jul 7 at 4:53

Dima Pasechnik
3,080●3●14

asked Jul 6 at 22:47

SAK
31●2

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 at 23:07

Dima Pasechnik · Answer 1 · 2012-07-07 05:13:35Z UTC

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.

Igor Rivin · Answer 2 · 2012-07-07 02:25:17Z UTC

2

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

answered Jul 7 at 2:25

Igor Rivin
31.1k●3●37●71

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

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 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 at 13:29

SAK · Answer 3 · 2012-07-10 21:04:48Z UTC

1

Thanks! This is very helpful. --SAK

answered Jul 10 at 21:04

SAK
31●2

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

is there a solution to system of linear Diophantine equations?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.