1

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

4

2 回答 2

0

我也是这样处理的。

浮点数的空空间通常使用 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
于 2022-02-11T17:18:59.390 回答
0

我是你提到的galois图书馆的作者。正如其他评论所指出的，此功能很容易添加，因此我在galois#259中添加了它。它现在在 v0.0.24 中可用（今天发布 02/12/2022）。

FieldArray.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

这是列空间和空空间。

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
于 2022-02-12T21:55:45.747 回答