To build on another answer- you could use Zobrist Hashing, often used in (historically?) in chess engines to quickly update a hash based on individual piece changes. You will get some undesirable collisions, but its fast and “good enough”, provided you implement logic to actually handle the rare collision.

To determine which rows to zero out, I track the hashes for each row as well as maintain a set of hashes which represent potential duplicate rows (otherwise they’re just ordinary hash collisions). This allows me to quickly lookup the corresponding rows in a dictionary and verify that they are indeed identical, before zero’ing one of them.

For the other two rules, I also track rows that contain just a single ‘1’. In an optimized implementation, you could avoid this an just deal with each such row as it is created (removing 1-rows or 1-cols will only create at most a single new 1-row or 1-col, so you could just recursively handle these, and then just iterate over each in the duplicate row scenario). This would avoid needing to track single rows/cols explicitly.

In theory, you could potentially get incredibly, astronomically unlucky and have a bunch of hash collisions forcing the duplicate row detection to be O(N^2) instead of O(1), especially if you have a huge amount of rows / cols, but you can also just increase the hash size to offset this.

Here’s some Python code demonstrating this approach. I have done very little testing, besides a few easy cases, so there could be a mistake somewhere, but it demonstrates the core ideas none-the-less.

from collections import defaultdict
from contextlib import contextmanager
from itertools import combinations
from random import randrange

class Row:
    def __init__(self, index):
        self.index = index
        self.cols = set()
        
        self.id = randrange(2 ** 32)
        self.hash = 0

    def add(self, col):
        self.cols.add(col)
        self.hash ^= col.id

    def remove(self, col):
        self.cols.remove(col)
        self.hash ^= col.id

    def pop(self):
        col = self.cols.pop()
        self.hash ^= col.id

    def __len__(self):
        return len(self.cols)
        
    def __hash__(self):
        return self.id

class Matrix:
    def __init__(self, nrows, ncols, transpose=None):
        self.rows = list(map(Row, range(nrows)))

        if transpose:
            self.T = transpose
        else:
            self.T = Matrix(ncols, nrows, transpose=self)

        self.single_rows = set()              # rows with single '1' column
        self.hash_to_rows = defaultdict(set)  # dictionary mapping Zobrist Hashes to rows
        self.repeat_hashes = set()            # hashes with collisions (potential duplicate rows)

    @contextmanager
    def update_row(self, row):
        self.hash_to_rows[row.hash].discard(row)
        if len(self.hash_to_rows[row.hash]) < 2:
            self.repeat_hashes.discard(row.hash)

        yield row
        
        self.hash_to_rows[row.hash].add(row)
        if len(self.hash_to_rows[row.hash]) > 1 and any(self.hash_to_rows[row.hash]):
            self.repeat_hashes.add(row.hash)
        
        if len(row) == 1:
            self.single_rows.add(row)
        else:
            self.single_rows.discard(row)
            
    def reduce_single_row(self):
        row = self.single_rows.pop()
        with self.update_row(row):
            col = row.cols.pop()
        with self.T.update_row(col):
            col.remove(row)
        return row

    def reduce_duplicate_row(self):
        hash = self.repeat_hashes.pop()
            
        rows = [row for row in self.hash_to_rows[hash] if row]
        for row1, row2 in combinations(rows, 2):
            if row1.cols == row2.cols:
                if len(rows) > 2:
                    self.repeat_hashes.add(hash)
                for col in list(row1.cols):
                    with self.T.update_row(col):
                        col.remove(row1)
                    with self.update_row(row1):
                        row1.remove(col)
                return row1

    def reduce_step(self):
        while self.repeat_hashes:
            row = self.reduce_duplicate_row()
            if row is not None:
                return "duplicate row", row.index
                
        if self.single_rows:
            row = self.reduce_single_row()
            return "single row", row.index
        elif self.T.single_rows:
            col = self.T.reduce_single_row()
            return "single col", col.index
        else:
            return None

    def reduce(self):
        while step := self.reduce_step():
            yield step

    @classmethod
    def from_data(cls, data):
        nrows = len(data)
        ncols = len(data[0])

        matrix = cls(nrows, ncols)
        for row, rdata in zip(matrix.rows, data):
            for col, elem in zip(matrix.T.rows, rdata):
                if elem:
                    with matrix.update_row(row):
                        row.add(col)
                    with matrix.T.update_row(col):
                        col.add(row)
                    
        return matrix

You can use Matrix.reduce() to get an output of steps taken to reduce your matrix to zeros (as much as possible anyways):

data = [
    [1, 0, 0],
    [1, 1, 0],
    [1, 1, 1],
]
matrix = Matrix.from_data(data)
for step in matrix.reduce():
    print(step)

Outputting:

('single row', 0)
('single col', 2)
('duplicate row', 1)
('single col', 0)
('single row', 2)

I’d start by calculating a hash code for every row and hoping that rows with equal hash code are equal, and keeping track of single ones in rows and columns. If there are no more than c different rows with equal hash code for some fixed c then this should work in O(n^2). If you have too many non-equal rows with same hash code then try a different t random hash function.

I don’t think you can guarantee O(n^2) but in practice will get it.