I have a system of linear equations, in which the unknowns can only take 2 integer values: +1 or -1. The linear system is $$ Ax = 0 $$ Matrix A is shown below with dimension (3 x 14): $$ \begin{pmatrix} 0 & 0 & 0 & 0 & -5 & 10 & -2 & 0 & -3 & 0 & 0 & 0 & 0 & 0 \\ 15 & 17 & 0 & 6 & 0 & 0 & 0 & 1 & 3 & 0 & 0 & 1 & 1 & 0 \\ 15 & 0 & 3 & -6 & 5 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & -1 \\ \end{pmatrix} $$ In my first attempt, I blindly augment them together and throw into Python sympy as $$ \begin{pmatrix} A \\ x_i^2 -1 \\ \end{pmatrix} $$ It is still homogeneous, but it has become quadratic. It takes forever for sympy to get an solution. Therefore, I wonder if there is any good algorithm that I can code up in a python program. It does look simple on the surface I admit.
By looking at matrix A, there seems to be a pattern to explore. For example for row 1: (-5 * 1) + 10 * 1 + (-2 * 1) + (-3 * 1) = 0, but I cannot go too far beyond this observation.
For each row, you could enumerate all the possible $x$ values that work, leaving the 0 columns ambiguous since the $0$s represent a point where $x_i$ doesn't matter. This should be a relatively small number of possibilities.
There are only four columns in $A$ where $x_i$ matters. The set of all $x$ that agree on these columns is the set of possible answers.
You could code the possible $x$ values as strings with three possible characters: 'a' for ambiguous, 'p' for positive, and 'n' for negative. From these strings, you can build a tree of possible full solution values. Each node would be a character in a possible string, and depth would represent the position of the character in the string. Each path of depth 14 would be a solution. The trick would be storing the strings in an efficiently searchable manner.