5

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

Seva
  • 22,827
  • Given a vector space, is it decidable whether it contains a nonzero zero-one vector? – Ville Salo Aug 10 '20 at 07:49
  • @VilleSalo If the vector space is given as a subspace of $\Bbb R^n$ by some basis vectors, you can just iterate over all $2^n-1$ non-zero 0-1-vectors an check whether one is in there. – M. Winter Aug 10 '20 at 10:47
  • Heh, good point. Is it in P? – Ville Salo Aug 10 '20 at 11:24
  • 1
    Is the condition of nonempty kernel essential? – Max Alekseyev Aug 10 '20 at 16:53
  • @MaxAlekseyev: If the kernel is trivial, then everything is in the row space of the matrix. I am not sure as to how important is to have the kernel not trapped in a coordinate hyperplane. – Seva Aug 11 '20 at 10:15
  • So, it is inessential. Btw, it may be the case that the existence of a nonzero 01-vector holds even for the lattice spanned by the rows. – Max Alekseyev Aug 11 '20 at 14:39
  • @MaxAlekseyev: 1) Well, we cannot say that the condition "the kernel contains a nowhere-zero vector" is inessential. 2) Absolutely, I am also trying to think in this direction. – Seva Aug 11 '20 at 15:12
  • 2
    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$?) – fedja Aug 13 '20 at 06:52
  • @fedja, do you have a name/reference for the problem when posed the way you have stated it? – kodlu Aug 16 '20 at 02:39
  • 1
    @kodlu: https://mathoverflow.net/q/16857/9924 – Seva Aug 16 '20 at 05:00
  • 1
    @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". – Seva Sep 03 '20 at 17:38
  • You just mean that the numbers can repeat in your formulation? I heard the question with the same assumption (repeated entries allowed), but OK. – fedja Sep 03 '20 at 17:51
  • @fedja: No, this is mostly not about repetitions. If we identify our set with a vector $a$, and $M$ is the associated matrix, then the original problem is to prove that $a^\perp$ contains a nonzero vector $\varepsilon\in{0,1}^n$. This is, in general, not equivalent to "the row space of $M$ contains a nonzero vector $\varepsilon\in{0,1}^n$". – Seva Sep 03 '20 at 17:57
  • But with all quantifiers: "For every $a$ in the kernel of $M$, $a^\perp$ contains a 0-1 vector" it is, isn't it? – fedja Sep 03 '20 at 18:14
  • @fedja: Ok, but this is already not the original question. Anyway, the source of the discrepancy is that the kernel of $M$ can contain vectors other than $a$. – Seva Sep 03 '20 at 18:24
  • "but this is already not the original question": I perceive the original question as "for every $a$ in the kernel of every such $M$", but OK, this discussion is not very interesting; we'd better just try to solve it :-) – fedja Sep 03 '20 at 18:26

1 Answers1

3

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.

Seva
  • 22,827