Probability of Unique Integer Solution to a System of Linear Equations
Abstract
We consider a system of m linear equations in n variables Ax = d and give necessary and sufficient
conditions for the existence of a unique solution to the system that is integer: x ? {?1,1}n. We achieve this by
reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer
solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear
programming reformulation succeeds for most instances, but if m is less than n/2, the reformulation fails on most
instances. We also demonstrate that these predictions match the empirical performance of the linear programming
formulation to very high accuracy.
Subject
linear programming
linear equations
unique integer solution
Permanent Link
http://digital.library.wisc.edu/1793/64352Citation
09-02