How to test linear independence of boolean array in a pythonic way?

Question

The rows of this matrix are not linearly independent, as the first two rows can be added (or XORed) to produce the third:

matrix = [
    [ 1, 0, 0, 1 ],
    [ 0, 0, 1, 0 ],
    [ 1, 0, 1, 1 ],
    [ 1, 1, 0, 1 ]
]

One could do brute-force reduction of the rows, with deeply nested for loops and if conditions and testing for an all zero row, but the resulting code doesn't feel like python.

Without using numpy or other library, what is a pythonic way of testing for independent rows (on much larger matrices)?

Answer 1

My guess is that you want something like this:

import itertools

def linearly_independent (rows):
    for r in range(2, len(rows) + 1):
        for c in itertools.combinations(rows, r):
            x = [0 for x in c[0]]
            for row in c:
                for i in range(len(x)):
                    x[i] ^= row[i]
            if not 1 in x:
                return False
    return True

If so, then calling algorithmically terrible code like this "Pythonic" and row reduction "brute force" suggests that your aesthetic principles are a problem. Because row reduction is absolutely the right approach.

---

For comparison here is the row reduction solution.

def linearly_independent (rows):
    # Clone everything to not mess up the original.
    rows = [[x for x in r] for r in rows]

    # We will be accessing rows[i][j].
    # Start at the top corner.
    i = j = 0
    while j < len(rows[0]):
        if 1 != rows[i][j]:
            found = False
            for i_swap in range(i+1, len(rows)):
                if 1 == rows[i_swap][j]:
                    (rows[i], rows[i_swap]) = (rows[i_swap], rows[i])
                    found = True
                    break
            if not found:
                j += 1
                continue
        # Now we have a row with a leading 1.
        for i_other in range(i+1, len(rows)):
            if rows[i_other][j] == 1:
                for k in range(j, len(rows[0])):
                    rows[i_other][k] ^= rows[i][k]
        i += 1
        if len(rows) < i:
            return True

    return False

Algorithmically the combinations code for an n x m matrix scales like O(m * n * 2^n). Row reduction scales like O(m * n^2). Which is much better.

Answer 2

This is also brute force, but using some Python tools:

from itertools import combinations

matrix = [
    [ 1, 0, 0, 1 ],
    [ 0, 0, 1, 0 ],
    [ 1, 0, 1, 1 ],
    [ 1, 1, 0, 1 ]
]

row_combinations = combinations(matrix, 2)


linear_dependant = True

for combination in row_combinations:
    
    result = [i1 ^ i2 for i1, i2 in zip(combination[0], combination[1])]
    not_all_zeros = not all([elem == 0 for elem in result])

    if not_all_zeros:
        linear_dependant = False
        break