How to do matrix conversions by row and columns toggles?

Question

I have got a square matrix consisting of elements either 1 or 0. An ith row toggle toggles all the ith row elements (1 becomes 0 and vice versa) and jth column toggle toggles all the jth column elements. I have got another square matrix of similar size. I want to change the initial matrix to the final matrix using the minimum number of toggles. For example

|0 0 1|
|1 1 1|
|1 0 1|

to

|1 1 1|
|1 1 0|
|1 0 0|

would require a toggle of the first row and of the last column.

What will be the correct algorithm for this?

Answer 1

In general, the problem will not have a solution. To see this, note that transforming matrix A to matrix B is equivalent to transforming the matrix A - B (computed using binary arithmetic, so that 0 - 1 = 1) to the zero matrix. Look at the matrix A - B, and apply column toggles (if necessary) so that the first row becomes all 0's or all 1's. At this point, you're done with column toggles -- if you toggle one column, you have to toggle them all to get the first row correct. If even one row is a mixture of 0's and 1's at this point, the problem cannot be solved. If each row is now all 0's or all 1's, the problem is solvable by toggling the appropriate rows to reach the zero matrix.

To get the minimum, compare the number of toggles needed when the first row is turned to 0's vs. 1's. In the OP's example, the candidates would be toggling column 3 and row 1 or toggling columns 1 and 2 and rows 2 and 3. In fact, you can simplify this by looking at the first solution and seeing if the number of toggles is smaller or larger than N -- if larger than N, than toggle the opposite rows and columns.

Answer 2

It's not always possible. If you start with a 2x2 matrix with an even number of 1s you can never arrive at a final matrix with an odd number of 1s.