Timeline for Matching a binary matrix
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2012 at 0:56 | comment | added | Kevin P. Costello | Let $A$ be the $(M+N) \times (M+N)$ matrix which is $0$ in the upper left $M \times M$ and lower right $N \times N$ submatrix, and elsewhere has two copies of a matrix with entries $(-1)^{D_{ij}}$. If we ignore the "equal sums" constraint, the problem is essentially asking you to find a $\pm 1$ vector $x$ which maximizes $x^TAx$. For general $A$ this problem (the so-called "Binary Quadratic Optimization" problem) is hard to solve exactly. My suspicion (though I don't have a proof for this) is that it remains hard to solve when restricted to the case where $A$ has the form in this problem. | |
| May 7, 2012 at 20:26 | comment | added | Chong Luo | I'm glad many people find this problem interesting. Maybe I should mention where it come from. The original problem is the bulb switching problem: "Given a MxN matrix of bulbs, some are on and some are off. We can flip the switch of bulb (i,j) to toggle the state of all bulbs in row i and column j. What's the minimum number of flips to turn all bulbs off?" I used $x_{ij}$ to denote whether to flip the switch of bulb (i,j), and $r_i$, $c_j$ to denote the row sums and column sums of $x_{ij}$. I found unique solution when M,N are both even. For M,N both odd, it's reduced to the problem above. | |
| May 7, 2012 at 19:16 | comment | added | Kevin P. Costello | You can still almost get half. If we choose $r$ uniformly from all vectors with $\frac{M+1}{2}$ nonzero entries, and $c$ uniformly from all vectors with $\frac{N \pm 1}{2}$ nonzero entries (sign chosen to match parity), then each cell has the correct sum with probability at least $\frac{MN-1}{2MN}$. The expected number of matching cells is $\frac{MN}{2}-\frac{1}{2}$. In general, I believe there are matrices where you can't match more than $1/2+\epsilon$ (e.g. random matrices) , but the original question seemed to be looking for an (Approx.?) algorithm instead of a bound over all matrices. | |
| May 7, 2012 at 15:46 | comment | added | Robert Israel | @TonyHuynh: Did you miss the constraint of $\sum r_i = \sum c_i$? | |
| May 7, 2012 at 10:53 | comment | added | Tony Huynh | Obvious comment: we can always get at least half of the cells satisfied. Set $c_i=0$ for all $i$. Then set $r_i=0$ or $r_i=1$ depending if row $i$ contains more zeros or ones | |
| May 7, 2012 at 10:03 | history | edited | Chong Luo |
edited tags
|
|
| May 6, 2012 at 5:59 | comment | added | Robert Israel | 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. | |
| May 5, 2012 at 18:20 | comment | added | Gerhard Paseman | 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 | |
| May 5, 2012 at 16:22 | comment | added | Gerhard Paseman | What would be a good match for the identity matrix for you? Gerhard "Ask Me About System Design" Paseman, 2012.05.04 | |
| May 5, 2012 at 14:40 | comment | added | Chong Luo | Sorry I forgot to add the constraint that $\sum r_i = \sum c_j$. Thanks for thinking about this problem. | |
| May 5, 2012 at 14:39 | history | edited | Chong Luo | CC BY-SA 3.0 |
deleted 3 characters in body
|
| May 5, 2012 at 14:18 | history | edited | Chong Luo | CC BY-SA 3.0 |
add an extra constraint that sum of r_i is the same as the sum of c_j
|
| May 5, 2012 at 13:18 | comment | added | Jyrki Lahtonen | 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 ... | |
| May 5, 2012 at 12:55 | history | edited | Chong Luo | CC BY-SA 3.0 |
added 82 characters in body
|
| May 5, 2012 at 10:16 | history | asked | Chong Luo | CC BY-SA 3.0 |