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$?
Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1
cc.complexity theory;np hardness;linear algebra
I use the user17410 equivalent formulation:Input: $n$ vectors $X = \{ x_1, \dots, x_m \}$ over $\{0,1\}^n$, $n$ is part of the inputQuestion: Are there two different subsets $A,B \subseteq X$ such that$$\sum_{x \in A} x = \sum_{x \in B} x$$The hardness proof involve many intermediate reductions that follow the same chain used to prove the hardness of the standard EQUAL SUBSET SUM problem:X3C $\leq$ SUBSET SUM $\leq$ PARTITION $\leq$  EVEN-ODD PARTITION $\leq$ EQUAL SUBSET SUM(I'm still checking it so it may be wrong :)STEP 1The following problem (0-1 VECTOR SUBSET SUM) is NP-complete: given  $X = \{ x_1, \dots, x_m \}$, $x_i$ vectors over $\{0,1\}^n$ and a target sum vector $t$, decide if there is $A \subseteq X$ such that$$\sum_{x \in A} x = t$$Proof: Direct reduction from EXACT COVER BY 3-SETS (X3C): given a set of $n$ elements $Y = \{y_1,...,y_n\}$ and a collection $C$ of $m$ three elements subsets $C = \{C_1,...,C_m\}$ we build the corresponding 0-1 VECTOR SUM instance setting $x_i[j] = 1$ if and only if element $j$ is included in $C_i$; $t = [1,1,...1]$.STEP 2Finding two equal sum subsets $A,B$ among $m$ 0-1 vectors over $\{0,1\}^n$, is equivalent to finding two equal sum subsets $A,B$ of vectors with element of bounded size $x_1 ... x_m$ where $max\{x_i\} = O((mn)^k)$ for fixed $k$.For example the set of vectors:x1 2 1 0 1x2 1 2 3 1Is equvalent to the 0-1 vectors:x1  1 1 0 1   1 0   0 0 0    1 0 0 0   0 1   0 0 0     0 0 0 0   1 1   0 0 0               ^ ^                +-- 0 elsewherex2  1 1 1 1   0 0   1 0 0    0 1 1 0   0 0   0 1 0    0 0 1 0   0 0   0 0 1    0 0 0 0   0 0   1 1 1                    ^ ^ ^                      +-- 0 elsewhereInformally the 0-1 vectors are grouped (if you select one vector of the x2 group and addit to subset $A$, then you are forced to include in $A$ the other two and put the last in subset $B$) and the sums are done in unary (this is the reason why the corresponding non binary vectors must contain elements that are polynomially bounded with respect to $mn$).So the following problem is NP-complete.STEP 3The following problem (0-1 VECTOR PARTITION) is NP-complete: given  $B = \{ x_1, \dots, x_m \}$, $x_i$ vectors over $\{0,1\}^n$ decide if $X$ can be partitioned in two subsets $B_1, B_2$ such that $$\sum_{x \in B_1} x = \sum_{x \in B_2} x$$Proof: Reduction from 0-1 VECTOR SUM:   given  $X = \{ x_1, \dots, x_m \}$and the target sum vector $t$; let $S = \sum x_i$, we add to $X$ the following vectors: $b' = -t + 2S$ and  $b'' = t + S\;$:  $B = X \cup \{b',b''\}$.($\Rightarrow$) Suppose that there exists $A \subseteq X$ such that $\sum_{x \in A} x= t$;we set $B_1 = A \cup \{b'\}$ and $B_2 =B \setminus B_1 = X \setminus \{A\} \cup \{b''\}$; we have$$\sum_{x \in B_1} = b'+\sum_{x \in A} x = t - t + S = 2S$$$$\sum_{x \in B_2} = b'' + \sum_{x \in X\setminus A} x = b'' + S - \sum_{x \in A} x=2S$$($\Leftarrow$) Suppose that $B_1$ and $B_2$ have equal sum. $b', b''$ cannot both belong to the same set (otherwise their sum is $\geq 3S$ and cannot be balanced by the elements in the other set). Suppose that $b' = -t + 2S \in B_1$; we have:$$-t +2S+ \sum_{x \in B_1 \setminus\{b'\}} x = t + S + \sum_{x \in B_2 \setminus\{b''\}} x$$Hence we must have $\sum_{x \in B_1 \setminus\{b'\}} x = t$ and $B_1 \setminus\{b'\}$ is a valid solution for the 0-1 VECTOR SUM.We only allow 0-1 vectors in the set $B$, so vectors $b', b''$ must be representedin unary as shown in STEP 2.STEP 3The problem is still NP-complete if the vectors are numbered from $x_1,...,x_2n$ and the two subsets $X_1,X_2$ must have equal size and we require that $X_1$ contains exactly one of $x_{2i-1},x_{2i}$ for $1 \leq i \leq n$ (so, by the equal size constraint, the other element of the pair must be included in $X_2$) (0-1 VECTOR EVEN-ODD PARTITION). Proof:: The reduction is from 0-1 VECTOR PARTITION and is similar to the reduction from PARTITION to EVEN-ODD PARTITION. If $X = \{x_1,...,x_m\}$ are $m$ vectors over $\{0,1\}^n$ replace each vector with two vectors over $\{0,1\}^{2n+2m}$:       1   2       n -------------------- x_i  b_1 b_2 ... b_n becomes:           1 2 ... 2i ... 2m  --------------------------  x'_2i-1  0 0 ...  1 ...  0  b_1 b_2 ... b_n   0   0  ...  0    x'_2i    0 0 ...  1 ...  0   0   0  ...  0   b_1 b_2 ... b_n Due to the $2i$ element, the vectors $x'_{2i-1}$ and $x'_{2i}$ cannot be contained in the same subset; and a valid solution to the 0-1 VECTOR EVEN-ODD PARTITION correspond to a valid solution of the original 0-1 VECTOR PARTITION (just pick elements 2m+1..2m+n of each vector of the solution discarding vectors that contain all zeros in those positions).STEP 40-1 VECTOR EQUAL SUBSET SUM (the problem in the question)  is NP-complete: reduction from 0-1 VECTOR EVEN-ODD PARTITION similar to the reduction from EVEN-ODD PARTITION to EQUAL SUM SUBSET, as proved in Gerhard J. Woeginger, Zhongliang Yu, On the equal-subset-sum problem: given an ordered set $A = \{x_1,...,x_{2m}\}$ of $2m$ vectors over $\{0,1\}^n$, we build a set $Y$ of $3m$ vectors over $\{0,1\}^{2m+n}$.For every vector $x_{2i-1}, 1 \leq i \leq m$ we build a vector $y_{2i-1}$ over $\{0,1\}^{2m+n}$ in this way:  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n  ------------------------------------------------------  0 0 ... 2  0  ... 0   0   0       1       0  x_{2i-1}For every vector $x_{2i}, 1 \leq i \leq m-1$ we build a vector $y_{2i}$ over $\{0,1\}^{2m+n}$ in this way:  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n  ------------------------------------------------------  0 0 ... 0  2  ... 0   0   0       1       0  x_{2i}We map element $x_{2m}$ to  1 2 ...       ... m  m+1 m+2 ...  . 2m  2m+1 ... 2m+n  ------------------------------------------------------  2 0 ...       ... 0   0   0          1  x_{2m}Finally we add $m$ dummy elements:  1 2 ...       ... m  m+1 m+2 ...  ... 2m  2m+1 ... 2m+n  ------------------------------------------------------  4 0 ...       ... 0   0   0            0  0    ... 0  0 4 ...       ... 0   0   0            0  0    ... 0  ...  0 0 ...       ... 4   0   0            0  0    ... 0Note again that vectors containing values $> 1$ can be represented in unary using a group of 0-1 vectors like showed in STEP 2. $Y$ has two disjoint $Y_1,Y_2$ subsets having equal sum if and only if $X$ has an even-odd partition.  