tutorial - que es un array en python

Prueba si la matriz es invertible sobre un campo finito

Question

Me gustaría probar si un tipo particular de matriz aleatoria es invertible sobre un campo finito, en particular F_2. Puedo probar si una matriz es invertible sobre los reales usando el siguiente código simple.

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

¿Hay alguna manera de lograr lo mismo pero por encima de F_2?

Answer 1

Sería mejor usar Sage o alguna otra herramienta adecuada para esto.

Lo siguiente es simplemente un intento no experto y poco sofisticado de hacer algo, pero la eliminación pivotada de Gauss debería dar el resultado exacto para la invertibilidad:

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)

Tenga en cuenta que np.bool_ es análogo a F_2 solo en un sentido restringido --- la operación binaria + en F_2 es - para bool, y el unary op - es + . La multiplicación es lo mismo, sin embargo.

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

La eliminación gaussiana anterior usa solo estas operaciones, por lo que funciona.

Answer 2

Desafortunadamente, SymPy aún no puede manejar campos finitos en matrices, aunque se planea soporte.

Sin embargo, como señalaron algunos comentaristas, puedes verificar el determinante sobre los enteros. Si es 1 (mod 2), la matriz es invertible. Para encontrar realmente lo inverso, puedes tomar el inverso normal sobre los enteros, multiplicar por el determinante (para que no tengas fracciones) y modificar cada elemento por 2. No me puedo imaginar que sería demasiado eficiente, y probablemente puedas usar cualquier biblioteca de matriz, incluso una numérica (redondeando al entero más cercano). SymPy también puede hacer cada uno de estos pasos.

Debo señalar que en los campos finitos cíclicos generales, la parte "multiplicar por el determinante" tendrá que deshacerse multiplicando por la mod inversa p (no es necesaria la modificación 2 porque la única posibilidad es 1).