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.

What is the usual size of you matrices i.e. how important is performance for you? What is stopping you from implementing your own version in vanilla python? Here's some inspiration https://math.stackexchange.com/questions/671722/how-to-find-the-null-space-of-the-matrix-over-finite-field-of-size-2 — DaveIdito, Feb 11 '22 at 10:37

score 2 · Accepted Answer · answered Feb 12 '22 at 21:55

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

Thats great, thanks a lot! This makes things much easier for me. — fran, Feb 16 '22 at 13:47

score 0 · Answer 2 · answered Feb 11 '22 at 17:18

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

Python linear algebra in a finite field

2 Answers2