3

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.

Léreau
  • 3,015
Joseph Zambrano
  • 1,237
  • All, sorry. I was being an ass. There were enough clues to suspect that my initial interpretation was wrong. For example, the problem would have been a linear system with a simple solution – Jyrki Lahtonen Aug 05 '16 at 22:08

2 Answers2

5

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.

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

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

Alex Ravsky
  • 90,434
1

Theoretically, yes. You just check every pair of vectors in $\{0,1\}^n$.

Try to write a Python code about this computation.

Kaa1el
  • 2,058
  • 1
    Yes but is this the only method? This could be quite computationally expensive for large $m$. – Joseph Zambrano Aug 01 '16 at 22:03
  • There are some optimization: for example, since $x$ and $y$ are fixed, you can only consider these columns where the entry is either $-1$ or $1$. But you still need to scan through every rows (all $1..m$) in order to read them. So at least $O(m^2)$. – Kaa1el Aug 01 '16 at 22:56