1
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ 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/… $\endgroup$
    – RobPratt
    Apr 3 at 11:40
  • $\begingroup$ @RobPratt thanks for the links! Why does my solution (using Gaussian elimination with rational numbers and then multiplying by the common denominator) not work? $\endgroup$ Apr 3 at 11:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Apr 3 at 11:44
  • 1
    $\begingroup$ Why do you need an exact solution? Does your $A$ matrix have any special structure that can be exploited? $\endgroup$
    – RobPratt
    Apr 3 at 11:46
  • $\begingroup$ @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$. $\endgroup$ Apr 3 at 11:52

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.