行列が有限体上で可逆であるかどうかのテスト

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や他の適切なツールを使用する方がよいでしょう。 np.bool_だけ狭義にF_2に類似していることを

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) 

注 - ：

次は何かをやっ時だけ洗練されていない非専門家の試みですが、ガウスの消去法を旋回さは、可逆性のために、正確な結果を与える必要があります - Foolのバイナリ操作+はブールの場合は-、単精度の場合は-は+です。しかし、乗算は同じです。

>>> 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) 

上記のガウス消去法は、これらの演算のみを使用するため、動作します。

Answer 2

残念ながら、サポートは予定されていますが、SymPyは行列の有限体をまだ処理できません。

いくつかのコメント者が指摘したように、整数の行列式を調べることができます。 1（mod 2）の場合、行列は可逆です。実際に逆関数を見つけるには、整数の逆数を取って、行列式を掛けて（分数を持たないように）、それぞれの要素を2でmodするだけです。効率が悪いとは想像もできませんが、おそらく任意の行列ライブラリを使用することができます。最も近い整数に丸められた数値ライブラリも使用できます。 SymPyはこれらの各ステップも実行できます。

一般的な循環有限体では、逆行列mod pを乗じることで、「行列式による乗算」の部分を取り消す必要があることを指摘しておきます。