# A tool for finding integer solutions to linear systems

I have a system of linear equations $$A x = 0$$, where $$A$$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common denominator gives a solution where all $$x_i$$ are integers.

I am looking for a software tool (preferrably in Python) that finds exact integer solutions efficiently for large systems. In theory, I can use any tool for integer linear programming, and define that the $$x_i$$ variables must be integers (e.g. in cvxpy I can write x_i = cvxpy.Variable(integer=True)). However, integer programming runs in exponential time, and might take too long when the matrices are large. But there are polynomial-time algorithms, such as some variants of Gaussian elimination, that should be able to more efficiently find rational solutions, and hence also integer solutions. Are there software tools that implement such algorithms?

• This feasibility problem is as hard as integer linear programming, so you should not expect a polynomial-time algorithm. See also these questions: or.stackexchange.com/questions/5167/… or.stackexchange.com/questions/10279/… Commented Apr 3 at 11:40
• @RobPratt thanks for the links! Why does my solution (using Gaussian elimination with rational numbers and then multiplying by the common denominator) not work? Commented Apr 3 at 11:41
• That approach yields an integer feasible solution but is not a polynomial algorithm. Intuitively, the issue is that the number of digits in the denominators can get big. Commented Apr 3 at 11:44
• Why do you need an exact solution? Does your $A$ matrix have any special structure that can be exploited? Commented Apr 3 at 11:46
• @RobPratt Isn't the problem of large coefficients solvable by the Bareiss algorithm? I need exact solutions because it is actually a solution to a combinatorial problem. The matrix $A$ has values in $\{-1,0,1\}$; in fact, all values are in $\{0,1\}$ except the last column of $A$, which contains only $-1$. Commented Apr 3 at 11:52

By scaling invariance, finding a nonzero integer solution to $$Ax = 0$$ is the same as finding any rational solution to $$\begin{bmatrix} A\\ e^T \end{bmatrix} x = \begin{bmatrix} 0\\ 1 \end{bmatrix}$$