Python 有限域中的线性代数

Question

有没有办法在Python的有限域中进行线性代数和矩阵运算？我需要能够在有限域 F2 中找到非方阵的空值 space。我目前找不到执行此操作的方法。我试过galois包，但是不支持scipy null space函数。在 sympy 中计算 null space 很容易，但是我不知道如何在 sympy 中的有限域中工作。

Answer 1

这也是我的做法。

Null space 浮点数通常使用 SVD 或其他一些稳健的算法来实现，对于您的 GF(2) 字段，您可以简单地使用高斯消元法，因为没有舍入。

举个例子

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

Answer 2

我是 galois library you mentioned. As noted by other comments, this capability is easy to add, so I added it in galois#259 的作者。它现在在 v0.0.24 中可用（今天发布 02/12/2022）。

这是用于计算您想要的空 space FieldArray.null_space() 的文档。

这是一个计算行 space 和左空值 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

这是列 space 和空值 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

Python 有限域中的线性代数

Python linear algebra in a finite field

python

python-3.x

matrix

linear-algebra

finite-field