Geek asks and answers

If the matrix is ​​invertible over a finite field

I would like to check if a particular type of random matrix is ​​reversible over a finite field, in particular F_2. I can check if the matrix is ​​reversible over actions using the following simple code.

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

Is there a way to achieve the same, but over F_2?

+5
source share
2 answers

It would be better to use Sage or some other suitable tool for this.

The following is just an inexperienced inexperienced attempt to do something, but turning a Gaussian exception should give an exact result for reversibility:

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, op - - +. .

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

, .

+4

, SymPy , .

, . 1 (mod 2), . , , (, ), 2. , , , , , ( ). SymPy .

, " " , mod p ( mod 2, 1).

+1

More articles:


All Articles