Transforming a NxN binary matrix to a zero matrix using minimum row and column toggles.

Question

Hello,

This is about the question i posted regarding converting one NxN binary matrix to another . The question i asked is a code-challenge problem . However, a similar question was asked at http://stackoverflow.com/questions/1310590/matrix-conversion. I went through that thread,and have gained some idea about how to go about solving the problem. I restate the problem here.

"I want to write code to solve the following problem. I am planning to use C, C++, Java or Python, depending on whichever allows a more convenient solution. Given two NxN (1 <= N <= 2000) binary matrices (A matrix each of whose element is either a one or a zero), A and B. The problem is to transform A into B, using the minimum number of permissible operations. The permissible operations are:
1. We can toggle a row,
  which will toggle all values in that row, i.e. it will change 1 to 0 and 0 to 1 in that row
2. We can toggle a column,
  which will toggle all values in that column, i.e. it will change 1 to 0 and 0 to 1 in that column.
If no solution is possible we print -1"

However, i have the following doubt.

I understood that the first step in finding the minimum number of toggles required to transform A to B is calculating A XOR B .The 1's in the result are the places which have to be toggled, in other words A XOR B has to be transformed to a zero matrix using the minimum number of row and column toggles . However, its not clear to me, how A XOR B is to be transformed to zero matrix , using the minimum number of row and column toggles. Could someone please shed some light on that ?

Thank You.

Answer 1

Fairly easy task.

First, we should understand that there is no sense in switching a row or a column more than once. For better understanding, we denote state like that: each cell has 0 or 1 in it and always take result of the sum with modulo 2:

final[i,j] = initial[i,j] + row_switched[i] + column_switched[j]  (mod 2)

where row_switched and column_switched are numbers of times we switched i-th row and j-th column. Now it's clear, that their values should be 0 or 1 to get minimal number of switches.

But that actually makes... a system of equations! We know initial states (given), we know final states (zeros), we only need to solve the system against r[i] and c[j]!

Unfortunately, it's still complex to solve because of moduli and because it doesn't include constraints implied on r[i] and c[j] (being 0 or 1).

---

Let's rewrite these condition without modulus:

row_switched[i] + column_switched[j] = 1  (if initial[i,j] = 1)
row_switched[i] - column_switched[j] = 0  (if initial[i,j] = 0)

Having written this for each cell, we have gotten an overdefined system of N^2 equations. Let's solve it in the following method. It's clear that if we knew the value of row_switched[0], we would then know the values of the whole column_switched[] array, because they're unambiguously deduced by the equations, in which row_switched[0] takes part. Then it's easy to deduce value of every row as well.

But we have only two variants for row_switched[0]: 0 and 1. Let's try each of them (SEE NOTE BELOW), and for each, calculate both arrays! Then we should check that all the equations hold and choose one of two sets that satisfies the whole system and has less switches.

If neither satisfies it, then, well, it's unsolvable. Try to solve this one, heh:

0 1
0 0

This completes the solution. I hope you'll do a +1 just for trying. :)

---

On the question why this is the least possible number of switches. Indeed, any valid number of switches should satisfy the system of equations outlined above (with 0 and 1 as constraints for values). But that system has not more than two solutions, and we find them all in the algorithm above. So, the algorithm above surely finds the minimal one.

---

NOTE: It seems to me, that we can only try one of set. If one passes the system, the other should pass as well. One set is a negation of another, so we just choose the set with less switch number. Sum of switches is 2N. But this only seems and is less clear than the other part.

Answer 2

Let me take another shot at explaining the end of my answer back in http://stackoverflow.com/questions/1310590/matrix-conversion.

We've reduced the problem to converting a matrix to the zero matrix via toggles, if possible. Start by noting that, if we want a minimal answer, we'll never toggle a row or column more than once, since toggling a row/column twice is the same as not toggling to begin with -- a consequence of the identity (P XOR 1) XOR 1 = P.

Let's look at the first row. Every 1 in the first row must be toggled to 0. We can do that by toggling each column with a 1 in the first row, or we can toggle the first row, swapping the 1's and 0's, and then toggle each new 1 back to a 0. And (assuming no toggle pairs) those are the only two sets of operations that result in the first row being reduced to all 0's.

At this point, look at the other rows. If any row has a mixture of 0's or 1's, you're done and the problem is insoluble; there is no way to make the row all 0's without a column toggle, and that destroys a 0 in the first row. OTOH, if every other row is all 0's or all 1's, then you just have row toggles remaining.

The final step is a consequence of the fact that there are 2N possible toggles, and no toggle will be part of both solutions. That should be immediately clear from the above for column toggles; for row toggles, note that a row that is all 0's after one set of column toggles will be all 1's after the other set of column toggles. So, after computing one set of K toggles, the size of the other set will be 2N - K toggles.