On Binary Solutions to a System of Linear Equations Modulo Three

We consider the problem of finding a binary solution to a system of linear equations modulo three. In the case where the number of equations is less than a sufficiently slowly growing function of the number of variables, a new polynomial-time algorithm is proposed to recognize the existence of a binary solution to such a system. The algorithm is based on the note that, if the coefficient matrix contains nonzero columns proportional to each other, then the elimination of the corresponding variables preserves the property of having no binary solution to the system. In particular, every system of two equations in five variables permits the elimination of some variables that preserves the property of having no binary solution to the system. Based on these results, we propose an errorless heuristic algorithm, which is implemented in the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix of the system. The empirical runtime estimate is calculated using the implementation. It is experimentally shown that the algorithm is more efficient for sparse systems of equations. Obviously, the binary search method can find a binary solution to the system when one exists. This observation opens up the possibility of its practical use, in particular, for solving problems of mathematical biology.