Test se la matrice è invertibile su campo finito

Question

Vorrei testare se un particolare tipo di matrice casuale è invertibile su un campo finito, in particolare F_2. Posso verificare se una matrice è invertibile sui reali usando il seguente codice semplice.

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

C'è un modo per ottenere la stessa cosa ma su F_2?

Answer 1

Sarebbe meglio usare Sage o qualche altro strumento adeguato per questo.

che segue è solo ingenuo tentativo non esperto a fare qualcosa, ma imperniato eliminazione di Gauss dovrebbe dare il risultato esatto per invertibilit'a:

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) 

noti che np.bool_ è analogo a F_2 solo in un senso ristretto - - l'operazione binaria + in F_2 è - per bool, mentre la versione unaria - è +. La moltiplicazione è la stessa, però.

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

L'eliminazione gaussiana sopra utilizza solo queste operazioni, quindi funziona.

Answer 2

Sfortunatamente, SymPy non può ancora gestire i campi finiti nelle matrici, sebbene sia pianificato il supporto.

Come alcuni commentatori hanno notato, tuttavia, è possibile controllare il determinante sugli interi. Se è 1 (mod 2), la matrice è invertibile. Per trovare effettivamente l'inverso, puoi semplicemente prendere l'inverso normale sopra gli interi, moltiplicare per il determinante (in modo da non avere frazioni) e modare ogni elemento per 2. Non riesco a immaginare che sarebbe troppo efficiente, e probabilmente potresti usare qualsiasi libreria di matrici, anche una libreria numerica (arrotondando al numero intero più vicino). SymPy può anche eseguire ognuno di questi passaggi.

Devo sottolineare che in generale i campi ciclici finiti, la parte "moltiplicare per il determinante" dovrà essere annullata moltiplicando per l'inversa mod p (non è necessario mod 2 perché l'unica possibilità è 1).