测试矩阵在有限域上是否可逆 [英] Test if matrix is invertible over finite field
问题描述
我想测试一种特定类型的随机矩阵在有限域(尤其是F_2)上是否可逆.我可以使用以下简单代码测试矩阵是否可逆于实数.
I would like to test if a particular type of random matrix is invertible over a finite field, in particular F_2. I can test if a matrix is invertible over the reals using the following simple code.
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之外,是否有其他方法可以实现相同的目的?
Is there some way to achieve the same thing but over F_2?
推荐答案
为此最好使用Sage或其他一些合适的工具.
It would be better to use Sage or some other proper tool for this.
以下只是做某事的不复杂的非专家尝试,但是枢轴的高斯消去应该给出可逆性的确切结果:
The following is just unsophisticated non-expert attempt at doing something, but pivoted Gaussian elimination should give the exact result for invertibility:
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 --- bool的F_2中的二元运算+
为-
,一元运算符-
为+
.但是,乘法是相同的.
Note that np.bool_
is analogous to F_2 only in a restricted sense --- the binary operation +
in F_2 is -
for bool, and the unary op -
is +
. Multiplication is the same, though.
>>> 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)
上面的高斯消除仅使用这些操作,因此可以正常工作.
The gaussian elimination above uses only these operations, so it works.
这篇关于测试矩阵在有限域上是否可逆的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!