4
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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 ... $\endgroup$
    – Jyrki Lahtonen
    Commented May 5, 2012 at 13:18
  • $\begingroup$ Sorry I forgot to add the constraint that $\sum r_i = \sum c_j$. Thanks for thinking about this problem. $\endgroup$
    – Chong Luo
    Commented May 5, 2012 at 14:40
  • 2
    $\begingroup$ What would be a good match for the identity matrix for you? Gerhard "Ask Me About System Design" Paseman, 2012.05.04 $\endgroup$
    – Gerhard Paseman
    Commented May 5, 2012 at 16:22
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented May 5, 2012 at 18:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented May 6, 2012 at 5:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .