Search code examples
pythonnumpymathmatrixlinear-algebra

How to find linear dependence mod 2 in python

I have a n+1 by n matrix of integers. I want to find a linear combination of the rows that reduces to zero mod 2. How would I do this in python? I could write gaussian elimination on my own, I feel there ought to be a way to do this using numpy or other library without writing it from scratch. Example:

I have the matrix

[1, 3, 0]

[1, 1, 0]

[1, 0, 1]

[0, 1, 5]

The function should return [1, 0, 1, 1]. Because that linear combination yields [2,4,6] = [0,0,0] mod 2.

Solution

  • You can use galois:

    from galois import GF2
import numpy as np

A = [[1, 3, 0], 
     [1, 1, 0],
     [1, 0, 1],
     [0, 1, 5]]

A = GF2(np.array(A).T % 2)
print(A.null_space())

    It gives:

    [[1 0 1 1]
 [0 1 1 1]]

    The rows are a basis of the null space of the matrix over the field F_2.