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$.

Improve this question
$\endgroup$
16
  • $\begingroup$ Given a vector space, is it decidable whether it contains a nonzero zero-one vector? $\endgroup$
    – Ville Salo
    Commented Aug 10, 2020 at 7:49
  • 1
    $\begingroup$ Is the condition of nonempty kernel essential? $\endgroup$
    – Max Alekseyev
    Commented 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
    Commented Aug 13, 2020 at 6:52
  • 1
    $\begingroup$ @kodlu: mathoverflow.net/q/16857/9924 $\endgroup$
    – Seva
    Commented 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
    Commented Sep 3, 2020 at 17:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .