Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
2  
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
2  
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
show 5 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.