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

-
The constant columns and constant rows span a binary linear code $C$ of length $MN$ and dimension $M+N-1$ (the rank drops by one, because the all ones matrix can be written as a sum of rows as well as columns). It seems to me that you want to find a valid codeword of $C$ at the smallest possible Hamming distance from the received 'vector' $D$. In other words, you want to have a complete decoding algorithm for the code $C$. Need to think about this one ... –  Jyrki Lahtonen May 5 '12 at 13:18
Sorry I forgot to add the constraint that $\sum r_i = \sum c_j$. Thanks for thinking about this problem. –  Chong Luo May 5 '12 at 14:40
What would be a good match for the identity matrix for you? Gerhard "Ask Me About System Design" Paseman, 2012.05.04 –  Gerhard Paseman May 5 '12 at 16:22
Once you answer the above, consider circulant matrices in general. What would be a good match for a circulant matrix? Or a row or column permutation of certain circulant matrices? Gerhard "Ask Me About Binary Matrices" Paseman, 2012.05.05 –  Gerhard Paseman May 5 '12 at 18:20
For the $N \times N$ identity matrix, I suspect that an optimal solution is all $r_i = c_i = 0$, which has $N$ "wrong" cells. –  Robert Israel May 6 '12 at 5:59