Sufficient condition for solvability of linear diophantine system

Question

I would like to know under what conditions does an integer solution exist to the under-determined linear system:

Ax = b. (without constraints)

Where A is m x n matrix with positive integers entries (m < n) and b is a positive integer vector.

I'm not interested in finding any solution, i would only to know if there is a fast algorithm that tells if an integer solution exists (with fast i mean faster than calculating the Hermite normal form or Smith normal form that allow to find the solution of the system).

I have found some methods based on the g.c.d. of the determinants of the mxm subsquare matricies of A but i think that they are too computational expensive (m=50 , n=100 means 100!/(50!*50!) number of mxm subsquare matricies).

Any help would be appreciated. Thanks.

Answer 1

This can certainly be done in polynomial time using the Smith normal form (SNF) of $A$, which is a diagonal matrix $D = SAT$ for some integer matrices $S,T$ of determinant $\pm 1$ (and thus whose inverses $S^{-1}, T^{-1}$ also have integer entries). Once we've computed $S$ and $T$, and thus $D$, we have $Ax=b$ iff $D(T^{-1}x) = (SAT)(T^{-1}x) = SAx = Sb$. So there's a solution iff each entry of $Sb$ is a multiple of the corresponding diagonal entry of $D$. While polynomial-time, this technique is still cumbersome for your values $(m,n)=(50,100)$, but GP-Pari's matsolvemod (which includes $Ax=b$ as the special case $D=0$) still solves such equations routinely (assuming $A$ and $b$ have reasonably-sized entries); I'm told that it uses not the generic SNF algorithm but a nontrivial improvement involving the LLL algorithm for lattice basis reduction.