有限域上矩阵是否可逆的检验

Question

我想测试一种特殊类型的随机矩阵在有限域上是否可逆，特别是F_2。我可以用下面的简单代码测试一个矩阵是否在实数上可逆。在

import random
from scipy.linalg import toeplitz
import numpy as np
n=10
column = [random.choice([0,1]) for x in xrange(n)]
row = [column[0]]+[random.choice([0,1]) for x in xrange(n-1)]
matrix = toeplitz(column, row)
if (np.linalg.matrix_rank(matrix) < n):
    print "Not invertible!"

有没有什么方法可以达到同样的效果，但要超过F 2？在

Answer 1

最好使用Sage或其他合适的工具。在

以下只是简单的非专家尝试，但是旋转高斯消去法应该给出可逆性的确切结果：

import random
from scipy.linalg import toeplitz
import numpy as np

def is_invertible_F2(a):
    """
    Determine invertibility by Gaussian elimination
    """
    a = np.array(a, dtype=np.bool_)
    n = a.shape[0]
    for i in range(n):
        pivots = np.where(a[i:,i])[0]
        if len(pivots) == 0:
            return False

        # swap pivot
        piv = i + pivots[0]
        row = a[piv,i:].copy()
        a[piv,i:] = a[i,i:]
        a[i,i:] = row

        # eliminate
        a[i+1:,i:] -= a[i+1:,i,None]*row[None,:]

    return True

n = 10
column = [random.choice([0,1]) for x in xrange(n)]
row = [column[0]]+[random.choice([0,1]) for x in xrange(n-1)]
matrix = toeplitz(column, row)

print(is_invertible_F2(matrix))
print(int(np.round(np.linalg.det(matrix))) % 2)

请注意，np.bool_仅在有限的意义上与F_2相似——Fୱ2中的二进制运算+是bool的-，一元运算-是{}。不过，乘法是一样的。在

^{pr2}$

上面的高斯消去法只使用这些运算，所以它是有效的。在

Answer 2

不幸的是，SymPy还不能处理矩阵中的有限域，尽管支持是计划好的。在

不过，正如一些评论者所指出的，你可以只检查整数的行列式。如果它是1（模2），矩阵是可逆的。要真正求逆，只需对整数求正逆，乘以行列式（这样就没有分数），然后将每个元素修改为2。我无法想象它的效率会有多高，而且你可以使用任何矩阵库，甚至是一个数值库（四舍五入到最接近的整数）。SymPy也可以执行这些步骤中的每一步。在

我要指出的是，在一般的循环有限域中，“乘行列式”部分需要乘以逆mod p来撤销（不需要mod 2，因为唯一的可能性是1）。在