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

Answer 2

That's how I would approach as well.

Null space for floating point numbers is usually implemented using SVD or some other robust algorithm, for your GF(2) field it you can simply use a gaussian elimination, since there is no rounding.

Here goes an example

import numpy as np
import galois
# Initialize GF(2) and a random matrix to serve as an example
M,N = 7, 4
GF2 = galois.GF(2)
A = GF2.Random((M, N))

# B is an augmented matrix [A | I]
B = GF2.Zeros((M, M+N));
B[:, :N] = A
for i in range(M):
  B[i, N+i] = 1;
for i in range(M):
  B[i, N+i] = 1;
# Run gaussian elimination
k = 0;
for j in range(N):
  i = j;
  for i in range(k, M):
    if B[i,j] != 0:
      if i != j:
        B[[i,k],:] = B[[k,i],:]
        break;
  if B[k,j] == 0:
    continue;
  for i in range(j+1, M):
    if B[i,j]:
      B[i,j:] += B[k,j:];
  k += 1;
C = B[k:, N:]

# C should be the left null space of A
C @ A # should be zero