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 case 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 non-zero 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 allows 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 using the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix. An empirical running time estimate has been calculated using the implementation. It has been experimentally shown that the algorithm is more efficient for sparse systems of equations. Obviously, the binary search method allows finding a binary solution to the system when one exists. This observation opens up the possibility of practical use, in particular, for solving problems of mathematical biology.