測試矩陣在有限域上是否可逆

我想測試一個特定類型的隨機矩陣是否在有限域上是可逆的，特別是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實現同樣的功能？

來源

2013-04-27 marshall

你可以用鼠尾草很輕鬆地做到這一點（[示例]（http://aleph.sagemath.org/?z=eJzzDVawVfBNLCnKrAguSExO1XB30zDS1FEwBiJNXq7yjMycVIWQotJUK14uBSDwBSkP1itKzEvJz41PzUnNTc0r0dCESGamKfjqZRbHZ-aVpRaVZCblpGpoQvWBQFJRamI2gsvLVVCUmVeioO5rpQ5j-yIEgYYgieuBzSxOBVkFU6GFpkZBC1UdABH6PRM=&lang=sage））。不過，我會很感興趣的，看看科學堆棧上是否有一個精巧的解決方案（numpy/scipy/sympy/mpmath/pandas等）。 – DSM 2013-04-27 17:09:58

我認爲，如果將F_2上的矩陣看作Z上的矩陣，只使用0和1，則F_2上的行列式應該是Z模2上的行列式（即，如果Z上的行列式是偶數或奇數，則檢查變爲）。這可能不是算法最優的。 – 2013-04-27 19:01:12

@ArminRigo不幸的是，我不能得到這個想法的工作。在上面的代碼中設置n = 100並打印linalg.det（矩陣），linalg.det（矩陣）％2。我總是得到0爲linalg.det（矩陣）％2，這大概是因爲浮點問題。是否有確切的整數行列式函數？ – marshall 2013-04-27 22:36:04

最好使用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-27 23:10:22

謝謝。如果這是正確的做法，我不介意爲這個特定任務導入外部庫。例如，我從未使用過鼠尾草，也不知道它與scipy矩陣交互的程度如何。 – marshall 2013-04-28 09:34:17

+和 - 在F_2中是一樣的。 – asmeurer 2013-04-28 19:58:03

@asmeuer：是的，但對布爾人來說並非如此。 – 2013-04-29 08:15:27

不幸的是，儘管支持計劃，但SymPy還不能處理矩陣中的有限域。

正如一些評論者指出，雖然，你可以檢查整數的行列式。如果它是1（mod 2），矩陣是可逆的。要實際找到反函數，可以對整數乘以正常的反函數，乘以行列式（這樣就不會有分數），並將每個元素修改爲2.我無法想象它會太高效，你甚至可以使用任何矩陣庫，即使是數字的（舍入到最接近的整數）。 SymPy也可以完成以上每個步驟。

我應該指出，在一般的循環有限域中，乘以行列式的部分將需要通過乘以逆模p來取消（這是不必要的mod 2，因爲唯一的可能性是1）。

來源

2013-04-28 20:01:16 asmeurer

謝謝，這很有趣。我想一個很好的補充是scipy可以計算整數的行列式。 – marshall 2013-04-29 07:46:30

測試矩陣在有限域上是否可逆

回答

相關問題