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

If you can only toggle the rows, and not the columns, then there will only be a subset of matrices that you can convert into the final result. If this is the case, then it would be very simple:

for every row, i:
  if matrix1[i] == matrix2[i]
    continue;
  else
    toggle matrix1[i];
    if matrix1[i] == matrix2[i]
      continue
    else
      die("cannot make similar");

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.

Answer 3

I came up with a brute force algorithm.

The algorithm is based on 2 conjectures:
^{(so it may not work for all matrices - I'll verify them later)}

• The minimum (number of toggles) solution will contain a specific row or column only once.
• In whatever order we apply the steps to convert the matrix, we get the same result.

The algorithm:
Lets say we have the matrix m = [ [1,0], [0,1] ].

m: 1 0
   0 1

We generate a list of all row and column numbers,
like this: ['r0', 'r1', 'c0', 'c1']

Now we brute force, aka examine, every possible step combinations.
For example,
we start with 1-step solution,
ksubsets = [['r0'], ['r1'], ['c0'], ['c1']]

if no element is a solution then proceed with 2-step solution,
ksubsets = [['r0', 'r1'], ['r0', 'c0'], ['r0', 'c1'], ['r1', 'c0'], ['r1', 'c1'], ['c0', 'c1']]

etc...

A ksubsets element (combo) is a list of toggle steps to apply in a matrix.

---

Python implementation (tested on version 2.5)

# Recursive definition (+ is the join of sets)
# S = {a1, a2, a3, ..., aN}
#
# ksubsets(S, k) = {
# {{a1}+ksubsets({a2,...,aN}, k-1)}  +
# {{a2}+ksubsets({a3,...,aN}, k-1)}  +
# {{a3}+ksubsets({a4,...,aN}, k-1)}  +
# ... }
# example: ksubsets([1,2,3], 2) = [[1, 2], [1, 3], [2, 3]]
def ksubsets(s, k):
    if k == 1: return [[e] for e in s]
    ksubs = []
    ss = s[:]
    for e in s:
        if len(ss) < k: break
        ss.remove(e)
        for x in ksubsets(ss,k-1):
            l = [e]
            l.extend(x)
            ksubs.append(l)
    return ksubs

def toggle_row(m, r):
    for i in range(len(m[r])):
        m[r][i] = m[r][i] ^ 1

def toggle_col(m, i):
    for row in m:
        row[i] = row[i] ^ 1

def toggle_matrix(m, combos):
    # example of combos, ['r0', 'r1', 'c3', 'c4']
    # 'r0' toggle row 0, 'c3' toggle column 3, etc.
    import copy
    k = copy.deepcopy(m)
    for combo in combos:
        if combo[0] == 'r':
            toggle_row(k, int(combo[1:]))
        else:
            toggle_col(k, int(combo[1:]))

    return k

def conversion_steps(sM, tM):
# Brute force algorithm.
# Returns the minimum list of steps to convert sM into tM.

    rows = len(sM)
    cols = len(sM[0])
    combos = ['r'+str(i) for i in range(rows)] + \
             ['c'+str(i) for i in range(cols)]

    for n in range(0, rows + cols -1):
        for combo in ksubsets(combos, n +1):
            if toggle_matrix(sM, combo) == tM:
                return combo
    return []

Example:

m: 0 0 0
   0 0 0
   0 0 0

k: 1 1 0
   1 1 0
   0 0 1

>>> m = [[0,0,0],[0,0,0],[0,0,0]]
>>> k = [[1,1,0],[1,1,0],[0,0,1]]
>>> conversion_steps(m, k)
['r0', 'r1', 'c2']
>>>

Answer 4

This is a state space search problem. You are searching for the optimum path from a starting state to a destination state. In this particular case, "optimum" is defined as "minimum number of operations".

The state space is the set of binary matrices generatable from the starting position by row and column toggle operations.

ASSUMING that the destination is in the state space (NOT a valid assumption in some cases: see Henrik's answer), I'd try throwing a classic heuristic search (probably A*, since it is about the best of the breed) algorithm at the problem and see what happened.

The first, most obvious heuristic is "number of correct elements".

Any decent Artificial Intelligence textbook will discuss search and the A* algorithm.

You can represent your matrix as a nonnegative integer, with each cell in the matrix corresponding to exactly one bit in the integer On a system that supports 64-bit long long unsigned ints, this lets you play with anything up to 8x8. You can then use exclusive-OR operations on the number to implement the row and column toggle operations.

CAUTION: the raw total state space size is 2^(N^2), where N is the number of rows (or columns). For a 4x4 matrix, that's 2^16 = 65536 possible states.

Answer 5

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 6

Algorithm

Simplify the problem from "Try to transform A into B" into "Try to transform M into 0", where M = A xor B. Now all the positions which must be toggled have a 1 in them.

Consider an arbitrary position in M. It is affected by exactly one column toggle and exactly one row toggle. If its initial value is V, the presence of the column toggle is C, and the presence of the row toggle is R, then the final value F is V xor C xor R. That's a very simple relationship, and it makes the problem trivial to solve.

Notice that, for each position, R = F xor V xor C = 0 xor V xor C = V xor C. If we set C then we force the value of R, and vice versa. That's awesome, because it means if I set the value of any row toggle then I will force all of the column toggles. Any one of those column toggles will force all of the row toggles. If the result is the 0 matrix, then we have a solution. We only need to try two cases!

Pseudo-code

function solve(Matrix M) as bool possible, bool[] rowToggles, bool[] colToggles:
    For var b in {true, false}
        colToggles = array from c in M.colRange select b xor Matrix(0, c)
        rowToggles = array from r in M.rowRange select colToggles[0] xor M(r, 0)
        if none from c in M.colRange, r in M.rowRange
                where colToggle[c] xor rowToggle[r] xor M(r, c) != 0 then
            return true, rowToggles, colToggles
        end if
    next var
    return false, null, null
end function

Analysis

The analysis is trivial. We try two cases, within which we run along a row, then a column, then all cells. Therefore if there are r rows and c columns, meaning the matrix has size n = c * r, then the time complexity is O(2 * (c + r + c * r)) = O(c * r) = O(n). The only space we use is what is required for storing the outputs = O(c + r).

Therefore the algorithm takes time linear in the size of the matrix, and uses space linear in the size of the output. It is asymptotically optimal for obvious reasons.

Answer 7

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