Find the rank of a binary matrix over Z/2Z

binary_rank.py

# Find the rank of a binary matrix over Z/2Z
# (conceptual implementation)
#
# RA, 2017-11-07 (CC-BY-4.0)
#
# Adapted from
#   https://triangleinequality.wordpress.com/2014/01/23/computing-homology/
#
def binary_rank(M) :
    
    # M-pty matrix?
    if not M.count_nonzero() : return 0

    # Find any nonzero entry, i.e. the pivot
    (p, q) = tuple(a[0] for a in M.nonzero())

    # Indices of entries to flip
    # (Could filter out p and q)
    I = M[:, q].nonzero()[0]
    J = M[p, :].nonzero()[1]

    # Flip those entries
    for i in I :
        for j in J :
            M[i, j] = not M[i, j]

    # Zero out pivot row p / column q
    # (Or delete them from the matrix)
    M[p, :] = 0
    M[:, q] = 0
    
    return 1 + binary_rank(M)