测试矩阵在有限域上是否可逆

Question

测试矩阵在有限域上是否可逆

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上实现相同的事情？

- marshall

2

你可以很容易地使用Sage来完成它（示例)。不过，我会很感兴趣看到在科学堆栈（numpy/scipy/sympy/mpmath/pandas等）中是否有一个简洁的解决方案。 - DSM

1

我认为，如果您将F_2上的矩阵视为仅使用0和1的Z上的矩阵，则F_2上的行列式应该是Z上模2的行列式（即检查Z上的行列式是偶数还是奇数）。这可能不是算法上最优的选择。 - Armin Rigo

@ArminRigo 很遗憾，我无法让这个想法起作用。在上面的代码中设置n = 100并打印linalg.det(matrix)，linalg.det(matrix)%2。我总是得到linalg.det(matrix)%2为0，这可能是由于浮点问题导致的。是否有一个精确的整数行列式函数？ - marshall

@marshall：Numpy/Scipy中的det仅支持浮点数。 - pv.

@marshall：我注意到你添加了sympy标签。它可以完成完整的整数行列式，但速度会非常慢。 - DSM

@DSM 是的，我真的不想用sympy来做这件事。最终，我想知道科学堆栈中的哪一部分应该包含它？ - marshall

2个回答

1

不幸的是，SymPy目前无法处理矩阵中的有限域，尽管支持计划中。

正如一些评论者所指出的那样，您可以在整数上检查行列式。如果它是1（mod 2），则该矩阵可逆。要实际找到逆矩阵，您只需在整数上取正常的逆矩阵，乘以行列式（这样就不会有分数），并将每个元素模2。我想效率可能不太高，您甚至可以使用任何矩阵库，甚至是数值库（四舍五入到最近的整数）。SymPy也可以执行这些步骤。

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

- asmeurer

谢谢，这很有意思。我想一个不错的补充是Scipy可以计算整数行列式。 - marshall

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pv. · Accepted Answer

最好使用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)

上述高斯消元只使用了这些操作，因此可以正常工作。