Given an $m$ by $n$ matrix $M$ whose elements are $0$ or $1$, is there an efficient way of finding a vector $x \ne 0$ whose are elements are from $-1,0,1$ such that $Mx = 0$, or even determining if one exists?
You can apply Gauss-Jordan elimination. Since right hand side is zero, when you apply the elimination, it is still zero. Hence, we can either determine the value of one variable exactly (if M is invertible and m = n), or determine a relation between n - m + 1 variables. In the first case, you can back substitute to get other variables' values. In the second case, you can try all combination of these n - m + 1 variables that satisfy the relation and do back substitution. In the second case, the time complexity may be exponential when n is far larger than m.