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?

  • 1
    $\begingroup$ This seems to be a difficult problem... One possibility: solve the polynomial system given by the linear equations $M\cdot x=0$ and by the equations $x_i^3-x_i=0$. $\endgroup$
    – emeu
    Dec 19 '13 at 19:22
  • $\begingroup$ You mean $x \ne 0$, right? $\endgroup$
    – ronno
    Dec 20 '13 at 12:29
  • $\begingroup$ @ronno Thank you for that fix. $\endgroup$
    – user115998
    Dec 20 '13 at 18:08

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.