A tool for finding integer solutions to linear systems

Question

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?

Answer 1

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} $$

Hence, you really only need a software implementation to compute rational solutions to linear equations, and can scale back to what you really want afterwards.

In theory, this can be done in strongly polynomial time as stated in https://en.wikipedia.org/wiki/Gaussian_elimination#Strongly_polynomial-time_algorithm and the references therein, but in practice I am under the impression that people just increase the floating-point precision until they are satisfied with the solution. A websearch for python, linear algebra, and high/extended/arbitrary precision gives many options.