Python linear algebra in a finite field

Question

Is there a way to do linear algebra and matrix manipulation in a finite field in Python? I need to be able to find the null space of a non-square matrix in the finite field F2. I currently can't find a way to do this. I have tried the galois package, but it does not support the scipy null space function. It is easy to compute the null space in sympy, however I do not know how to work in a finite field in sympy.

Answer 1

I'm the author of the galois library you mentioned. As noted by other comments, this capability is easy to add, so I added it in galois#259. It is now available in v0.0.24 (released today 02/12/2022).

Here is the documentation for computing the null space FieldArray.null_space() that you desire.

Here's an example computing the row space and left null space.

In [1]: import galois

In [2]: GF = galois.GF(2)

In [3]: m, n = 7, 3

In [4]: A = GF.Random((m, n)); A
Out[4]: 
GF([[1, 1, 0],
    [0, 0, 0],
    [1, 0, 0],
    [1, 1, 1],
    [0, 0, 1],
    [1, 1, 1],
    [0, 1, 0]], order=2)

In [5]: R = A.row_space(); R
Out[5]: 
GF([[1, 0, 0],
    [0, 1, 0],
    [0, 0, 1]], order=2)

In [6]: LN = A.left_null_space(); LN
Out[6]: 
GF([[1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 1, 1, 1],
    [0, 0, 0, 1, 0, 1, 0]], order=2)

# The left null space annihilates the rows of A
In [7]: LN @ A
Out[7]: 
GF([[0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]], order=2)

# The dimension of the row space and left null space sum to m
In [8]: R.shape[0] + LN.shape[0] == m
Out[8]: True

Here's the column space and null space.

In [9]: C = A.column_space(); C
Out[9]: 
GF([[1, 0, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 0, 1],
    [0, 0, 0, 1, 1, 1, 0]], order=2)

In [10]: N = A.null_space(); N
Out[10]: GF([], shape=(0, 3), order=2)

# If N has dimension > 0, then A @ N.T == 0

In [11]: C.shape[0] + N.shape[0] == n
Out[11]: True