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?