Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1 Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\mathbb{Z}$).  Is this problem NP-hard?

It is clearly in NP as you can give two vectors as witnesses.



Equivalently: Given $M$, is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

Equivalently: Given $n$ vectors $X=\{x_1,\dots,x_n\}$ over $\{0,1\}^m$, are there two different subsets $A,B \subseteq X$ such that $\sum_{x \in A} x = \sum_{x \in B} x$?
EDIT: My original proof had a bug. I now believe that it is fixed.

We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from EQUAL SUM SUBSETS.  I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x  and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.


  ..10.. 11
  ..01.. 10
  ..01.. 01


Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:


  1000  


=


  0101
  0011  


These bit strings give the same sum in binary, but not in vector addition. 

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.


  1000 00 00 00
  0001 00 00 01
  0001 00 00 10
  0010 00 01 00
  0010 00 10 00
  0100 01 00 00
  0100 10 00 00  


=


  0101 00 00 00
  0011 00 00 00
  0010 00 00 11
  0100 00 11 00
  1000 11 00 00  


These sets now have the same sum in vector addition. The sums are:


  1222 11 11 11


in both cases.

This construction works great if there is only one carry per position, but there could potentially be up to $n$ carries per position, and you need to make sure that your construction can handle up to $n$ carries, and that the different carries don't interfere with each other. For instance, if you added two different sets of three vectors for the same pair of adjacent positions (which is what I proposed in my original proof):


  ..01.. 01 00
  ..01.. 10 00
  ..10.. 11 00
  ..01.. 00 01
  ..01.. 00 10
  ..10.. 00 11  


you have the problem that you get two different sets of vectors giving the same sum:


  ..01.. 01 00
  ..01.. 10 00
  ..10.. 00 11


=


  ..01.. 00 01
  ..01.. 00 10
  ..10.. 11 00


How to fix this? Add one set of vectors which lets you carry 1, one set which lets you carry 2, and one set for 4, 8, $\ldots$, 2$^{\lfloor \log n \rfloor}$. I'm not going to go work out the details of this construction right now, but it should be fairly straightforward. Since each number has a unique binary representation, this will let you carry any number up to $n$. For carrying 4, for example, you need find four vectors which have the same sum as two vectors, and for which this is the only linear relation between the two sets. For example, the set


  ..01.. 11000
  ..01.. 00100
  ..01.. 00010
  ..01.. 00001
  ..10.. 10001
  ..10.. 01110  


works. You can easily check that the relation


  11000
  00100
  00010
  00001  


=


  10001
  01110


is the only possible relation among these six vectors because the matrix formed by these six rows has rank 5.