Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

Question

I'm trying to determine whether it is possible to decide if a system of $n$ linear equations with integer coefficients and $n$ variables has a solution in $\{0, 1\}^n$ in polynomial time.

Additionally, all of the coefficients of $A$ are in $\{-1, 0, 1\}$, but I couldn't find a way to use that.

The trivial case is if the (matrix $A$ of the) system is invertible, there is only one solution, it is easy to check whether all of them belong to $\{0,1\}$.

However, if you have infinitely many solutions, and $k$ free variable, I can't find a way to do better than check all the $2^k$ possibilities.

• Do you know any algorithm to do so in polynomial time ?

I also tried to do a reduction from SAT (or some variant with n clauses and n variables in each clause, to show that it is NP complete), but because of the fact that we have $Ax = b$ and not $Ax \geq b$, I couldn't do that either.

• Do you have a reduction to show that this problem is NP complete ?