Test if matrix is invertible over finite field

math, numpy, python, scipy, sympy

Solution

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

The following is just unsophisticated non-expert attempt at doing something, but pivoted Gaussian elimination should give the exact result for 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)

Note that `np.bool_` is analogous to F_2 only in a restricted sense --- the binary operation `+` in F_2 is `-` for bool, and the unary op `-` is `+`. Multiplication is the same, though.

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

The gaussian elimination above uses only these operations, so it works.

Problem

I would like to test if a particular type of random matrix is invertible over a finite field, in particular F_2. I can test if a matrix is invertible over the reals 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 some way to achieve the same thing but over F_2?

Original source