Kiểm tra nếu ma trận có thể đảo ngược trên trường hữu hạn

Question

Tôi muốn kiểm tra xem một loại ma trận ngẫu nhiên cụ thể có thể đảo ngược trên trường hữu hạn hay không, cụ thể là F_2. Tôi có thể kiểm tra nếu một ma trận là không thể đảo ngược trên thực tế bằng cách sử dụng mã đơn giản sau đây.

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ó cách nào để đạt được điều tương tự nhưng trên F_2 không?

Answer 1

Sẽ tốt hơn nếu sử dụng Sage hoặc một số công cụ thích hợp khác cho việc này.

Sau đây chỉ là không phức tạp nỗ lực phi chuyên gia làm một cái gì đó, nhưng xoay khử Gauss nên cho kết quả chính xác cho 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) 

Lưu ý rằng np.bool_ là tương tự như F_2 chỉ trong một cảm giác giới hạn - - hoạt động nhị phân + trong F_2 là - cho bool và op unary - là +. Phép nhân cũng giống nhau.

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

Loại bỏ gaussian ở trên chỉ sử dụng các hoạt động này, vì vậy nó hoạt động.

Answer 2

Thật không may, SymPy chưa thể xử lý các trường hữu hạn trong ma trận, mặc dù hỗ trợ được lên kế hoạch.

Tuy nhiên, như một số người nhận xét, bạn chỉ có thể kiểm tra yếu tố quyết định trên các số nguyên. Nếu đó là 1 (mod 2), ma trận là không thể đảo ngược. Để thực sự tìm thấy nghịch đảo, bạn có thể lấy nghịch đảo bình thường trên các số nguyên, nhân với yếu tố quyết định (để bạn không có phân số), và mod mỗi phần tử bằng 2. Tôi không thể tưởng tượng nó sẽ quá hiệu quả, và bạn có thể sử dụng bất kỳ thư viện ma trận nào, thậm chí là một thư viện số (làm tròn số nguyên gần nhất). SymPy cũng có thể thực hiện từng bước này.

Tôi nên chỉ ra rằng trong các trường hữu hạn cyclic chung, phần "nhân với yếu tố quyết định" sẽ cần được hoàn tác bằng cách nhân với mod nghịch đảo p (không cần thiết mod 2 vì khả năng duy nhất là 1).