Skip to main content
4 of 5
deleted 3 characters in body

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