algorithm - Converting a binary matrix to 0s by toggling rows and columns?

Question

Suppose that you're given a grid of 0s and 1s. Your goal is to turn the grid into a grid of all zeros by performing a series of "flip" operations: if you flip position (x, y) in the grid, then all of the bits in the same row or column as (x, y) get flipped.

Does anyone know of an efficient algorithm that can be used to solve this problem?

Answer 1

One possible way to solve this is to treat this problem as a linear system of equations, except using just 0 and 1 instead of real numbers.

The numbers 0 and 1 form a field under the operations XOR and AND (this field is called GF(2), by the way). That is, you can "add" two bits together by XOR-ing them together, and you can "multiply" two bits together by ANDing them. It turns out that the behavior of XOR and AND matches many properties of normal multiplication and addition - multiplication and addition are commutative and associative, and multiplication distributes over addition, for example. It turns out that these properties are sufficient to let you use Gaussian elimination to solve a linear system of equations over 0s and 1s. For example, Gaussian elimination can be used to solve this linear system of equations:

x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0

Consequently, if we can phrase your problem in terms of a linear system of equations using XORs and ANDs, then you can solve the problem in polynomial time by just using standard Gaussian elimination over this field.

To do this, first notice that inverting a bit is equivalent to XOR-ing it with 1:

• 0 XOR 1 = 1
• 1 XOR 1 = 0

This means that if you toggle an entire row and column, it's equivalent to XORing everything in that row and column with the value 1.

Now, suppose that you have an m × n matrix of 0s and 1s. We'll denote by A[i][j] the value of the number in the ith row and the jth column. Since toggling (i, j) toggles all of the elements in the same row and column, you can imaging that toggling (i, j) is equivalent to XORing the original matrix A to a new matrix A that looks like this:

0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
1 1 ... 1 1 1 ... 1
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0

Here, the 1s are in row i and column j, and the 0s are everywhere else.

Note that every position in the grid gives rise to one of these "toggle matrices" such that the effect of performing operation "flip (i, j)" is XOR-ing the current matrix with toggle matrix number (i, j).

Now for another key observation: no optimal solution (one with the shortest number of operations) to this problem ever flips the same position twice. The reason for this is that XOR inverts itself: a XOR a = 0. Consequently, any solution that flips the same position twice can be shortened by removing two of the flips to get a shorter solution. Moreover, since XOR is associative and commutative ((x XOR y) XOR z = x XOR (y XOR z), and x XOR y = y XOR x), it doesn't matter what order we perform the flips in for an optimal solution. All you have to do is perform the flips in whatever order you'd like, once you know which flips to do.

Combining all this together, we have that we are trying to determine, for each possible flip, whether or not we should perform that flip. Ordering and quantity don't matter.

Here's where we get to actual linear systems of equations. We're given a starting matrix A and a bunch of different "toggle matrices", one for each of the different flips we can do. Let's denote the toggle matrix for position (i, j) by T[i, j]. We'll then introduce new variables b[i, j] to be a 0 or 1 value indicating whether or not we are supposed to actually flip position (i, j). Given this setup, we are looking for a set of values for the b[i, j]'s such that

A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0

Where 0 is the zero matrix. If it's possible to find a choice of b's that works, then you have your solution. If not, then no solution exists. The question now is how to find them.

To do this, we'll make one small change to the above system. Let's XOR both sides of this equation by A. Since A XOR A = 0, this cancels out the A from the left side. Since A XOR 0 = A, this moves the A to the right side. Now we have

b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = A

Finally, we'll do one more change. Rather than representing A and the T[i, j]'s as matrices, let's represent them as column vectors in row-major order. This means that the above linear system of equations can actually be thought of not as a sum of matrices, but as a sum of column vectors.

To seal the deal, let's define a matrix T, where the first column of T is T[1, 1], the second column of T is T[1, 2], ..., and the mn-th column of T is T[m, n]. Then, let's let b = (b[1, 1], b[1, 2], ..., b[m, n])^T (that's a transpose, by the way). In that case, we can rewrite the above system as

Tb = A

This is beautiful! We're now trying to solve for a vector b such that T multiplied by b gives the matrix A. As mentioned above, since 0s and 1s with XORs and ANDs forms a field, you can use standard Gaussian elimination to solve this system.

So how efficient is this? Well, the matrix T has size mn × mn. Therefore, running Gaussian elimination on it will take time O(m³n³), which is large but still not too bad for reasonably small grids. We can construct the grid in time O(m²n²) as well by simply figuring out what entries get toggled. Overall, this gives an O(m³n³) algorithm for your problem. Yay!

I have an implementation of a solver for the game "Lights Out", which is extremely similar to this problem except that a toggle only flips the lights in the immediate neighborhood of (i, j), rather than flipping the entire row and column. It is based on the exact same approach, so if you wanted to take the code and use it as a starting point, you could probably code up this solver in a short amount of time. I've tried to add comments to the relevant parts of the code to make it easy to read, so hopefully it's useful.

Hope this helps!