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']
>>>
```