有限域中的Python线性代数

Question

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

Answer 1

我是您提到的galois库的作者。正如其他评论所指出的，这个功能很容易添加，所以我在galois#259中添加了它。它现在有0.0.24版本(于2022年12月2日发布(。

以下是用于计算所需的空空间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

Answer 2

我也会这样做。

浮点数的零空间通常使用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