5

我想测试一种特定类型的随机矩阵是否在有限域上可逆，特别是 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 上实现同样的目标？

4

2 回答 2

4

最好使用 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，而一元运算-是+. 不过，乘法是一样的。

>>> x = np.array([0, 1], dtype=np.bool_)
>>> x[:,None] - x[None,:]
array([[False,  True],
       [ True, False]], dtype=bool)
>>> x[:,None] * x[None,:]
array([[False, False],
       [False,  True]], dtype=bool)

上面的高斯消元法只使用了这些操作，所以它是有效的。

于 2013-04-27T23:10:22.987 回答
1

不幸的是，虽然计划提供支持，但 SymPy 还不能处理矩阵中的有限域。

但是，正如一些评论者指出的那样，您可以只检查整数的行列式。如果它是 1 (mod 2)，则矩阵是可逆的。要实际找到倒数，您可以对整数取正常倒数，乘以行列式（这样您就没有分数），然后将每个元素乘以 2。我无法想象它会太有效，您可能可以使用任何矩阵库，甚至是数字库（四舍五入到最接近的整数）。SymPy 也可以执行这些步骤中的每一个。

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

于 2013-04-28T20:01:16.187 回答