Sprawdź, czy macierz jest odwracalna nad skończonym polem.

Question

Chciałbym przetestować, czy określony typ macierzy losowej jest odwracalny w stosunku do pola skończonego, w szczególności F_2. Mogę sprawdzić, czy macierz jest odwracalna w stosunku do reali, używając następującego prostego kodu.

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!" 

Czy jest jakiś sposób osiągnięcia tego samego, ale ponad F_2?

Answer 1

Byłoby lepiej użyć Sage lub innego odpowiedniego narzędzia do tego.

Poniżej tylko naiwny non-ekspert próba zrobienia czegoś, ale obrócony eliminacji Gaussa należy podać dokładny wynik do odwracalności:

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) 

Zauważ, że np.bool_ jest analogiczna do F_2 tylko w ograniczonym znaczeniu - - operacja binarna + w F_2 jest - dla bool, a unary op - jest +. Mnożenie jest jednak takie samo.

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

Powyższa gausjańska eliminacja wykorzystuje tylko te operacje, więc działa.

Answer 2

Niestety, SymPy nie może jeszcze obsłużyć skończonych pól w macierzach, chociaż wsparcie jest planowane.

Jak zauważyli niektórzy komentatorzy, można po prostu sprawdzić wyznacznik na liczbach całkowitych. Jeśli jest 1 (mod 2), macierz jest odwracalna. Aby faktycznie znaleźć odwrotność, możesz po prostu przyjąć normalną odwrotność w stosunku do liczb całkowitych, pomnożyć przez wyznacznik (tak, abyś nie miał ułamków) i zmodyfikować każdy element przez 2. Nie mogę sobie wyobrazić, że byłoby to zbyt wydajne, i prawdopodobnie mógłbyś użyć dowolnej biblioteki macierzowej, nawet numerycznej (zaokrąglając do najbliższej liczby całkowitej). SymPy może również wykonać każdy z tych kroków.

Należy zauważyć, że w ogólnych cyklicznych polach skończonych część "mnożenie przez wyznacznik" będzie musiała zostać cofnięta poprzez pomnożenie przez odwrotny mod p (jest to niepotrzebny mod 2, ponieważ jedyną możliwością jest 1).