MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.