Solutions to Binary Equations Let $A \in \mathrm{Mat}(m,n,\{0,1\})$ (i.e. $m \times n$ matrices with entries in $\{0,1\}$ ) and $x,y\in \{0,1\}^n$. We will denote the $i$-th row of $A$ as $\mathrm{row}_i(A)\in \{0,1\}^n$. Define,
$$
 z_i := 
     \begin{cases}
       1~: & (x-y)\cdot \mathrm{row}_i(A) = \sum_{j=1}^n x_j\\
       0~: & \text{otherwise}\\
\end{cases}
$$
where $x_j$ is the $j$-th component of $x$ and $\cdot$ denotes the dot product. Is there an algorithm to determine all $x,y$ given a vector $z=(z_1,...,z_m)$?
Example: Let
$$A=
        \begin{bmatrix}
        0 & 0 & 1\\
        1 & 1 & 0\\
        1 & 0 & 1\\
        \end{bmatrix}
$$
and $z=(1, 0, 1)$. Then $x=(0,0,1)$ and $y=(0,1,0)$ would satisfy the conditions described.
 A: A triple $(x,y,z)$ of vectors ($x,y\in\{0,1\}^n$, $z\in\{0,1\}^m$) is a solution of the equation iff for each $i=1,\dots, m$ the following holds:
if $z_i=1$ then for each $j$ holds (*): if $a_{ij}=0$ then $x_j=0$ and if $a_{ij}=1$ then $y_j=0$.
if $z_i=0$ then Condition (*) is violated for at least one index $j$.
For two subsets $X$ and $Y$ of $\{1,\dots, n\}$ put 
$$[X,Y]=\{x\in \{0,1\}^n: x_j=0 \mbox{ for each }j\in X\}\times \{y\in \{0,1\}^n: y_j=0 \mbox{ for each }j\in Y\}.$$  
For an algorithmic applications remark that the set $[X,Y]$ of pairs $(x,y)$ is a Cartesian product of some subsets of $\{0,1\}^n$, which can be determined  independently. 
Now suppose that the vector $z$ is given. Given also the index $i$, Condition (*) is equivalent to say that $(x,y)\in [A_{i0},A_{i1}]$, where $A_{ik}=\{j:a_{ij}=k\}$. The above arguments yield an structural description of the set $S$ of solutions $(x,y)$: 
$$S=\left[\bigcup_{z_i=1} A_{i0},  \bigcup_{z_i=1} A_{i1}\right]\setminus \bigcup_{z_i=0} [A_{i0}, A_{i1}].$$
The structural description of the set $S$ produces a trivial two step algorithm to determine it. 


*

*Determine the sets $A_0=\bigcup_{z_i=1} A_{i0}$,  $A_1=\bigcup_{z_i=1} A_{i1}$, and the set $S'=[A_0,  A_1]$.

*Remove from the set $S'$ all sets $[A_{i0}, A_{i1}]$ for $z_i=0$.
The set of all pairs $(x,y)$ which remain after Step 2 is the set $S$ of all solutions $(x,y)$.
A: Theoretically, yes. You just check every pair of vectors in $\{0,1\}^n$.
Try to write a Python code about this computation.
