Skip to main content
3 of 5
add an extra constraint that sum of r_i is the same as the sum of c_j

Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that

  1. both M and N are odd numbers
  2. its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).

How do we find M binary numbers $r_i$ and N binary numbers $c_j$, such that $ \sum r_i = \sum c_j $ and $$ r_i + c_j = D_{ij} $$ is satisfied for as many cell $(i,j)$ as possible? (By the way, the "+" is in the $\mathbb{Z}_2$ field, that is the XOR operation.) 1.