5
$\begingroup$

Suppose that $M$ is a square matrix with all elements on its main diagonal equal to $1$, and every row containing exactly two off-diagonal elements equal to $-1$; all other elements are equal to $0$. The kernel of $M$ is nonzero and, indeed, contains a vector with all its coordinates nonzero. Does it follow that the row space of $M$ contains a (nonzero) zero-one vector?

In case it matters, the sum of all elements in every column of $M$ is nonpositive, and $M_{ij}M_{ji}=0$ whenever $i\ne j$.

$\endgroup$
16
  • $\begingroup$ Given a vector space, is it decidable whether it contains a nonzero zero-one vector? $\endgroup$
    – Ville Salo
    Aug 10, 2020 at 7:49
  • 1
    $\begingroup$ Is the condition of nonempty kernel essential? $\endgroup$ Aug 10, 2020 at 16:53
  • 2
    $\begingroup$ Why don't you just ask a very well known open question the way it has been initially posed (in a finite set of numbers each number is a sum of some other two; does it follow that there is a subset with sum $0$?) $\endgroup$
    – fedja
    Aug 13, 2020 at 6:52
  • 1
    $\begingroup$ @kodlu: mathoverflow.net/q/16857/9924 $\endgroup$
    – Seva
    Aug 16, 2020 at 5:00
  • 1
    $\begingroup$ @fedja: Because it is not equivalent. My question concerns with a stronger statement, with the goal is to evaluate a certain direction in solving the "very well known open question". $\endgroup$
    – Seva
    Sep 3, 2020 at 17:38

1 Answer 1

3
$\begingroup$

This is true:

For any square matrix $M$ with all elements on its main diagonal equal to 1, and every row containing exactly two off-diagonal elements equal to −1 (with all other elements are equal to 0), the row space of $M$ contains a nonzero zero-one vector. Moreover, there is a linear combination of the rows with the coefficients $0$ and $-1$ only which yields such a vector.

This is in fact the main lemma of this preprint; see, on the other hand, this MO problem for the explanations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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