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