Objetivo: generar una matriz cuadrada de números enteros aleatorios cuyo determinante sea 1 o -1.
Una primera idea puede ser realizar un bucle en el que generamos una matriz cuadrada de números enteros aleatorios hasta que se satisfaga la condición de que su determinante sea 1 o -1. El problema estaría resuelto, pero el algoritmo no es muy eficiente.
Voy a proponer a continuación otra solución.
Problema previo: generar una matriz triangular de números enteros aleatorios cuyo determinante sea 1 o -1.
Este problema es muy sencillo teniendo en cuenta que el determinante de una matriz triangular es igual al producto de los elementos de su diagonal.
Únicamente necesitamos rellenar la diagonal con elementos del conjunto {-1, 1}, ceros por encima (o por debajo) de la diagonal y números enteros aleatorios en el resto de elementos de la matriz.
Ejemplo de función en Python que calcula una matriz triangular de enteros aleatorios (entre -10 y 10, ambos incluidos) utilizando la librería NumPy.
import numpy as np
# Función para crear una matriz triangular de enteros con determinante 1 o -1
# n es la dimensión de la matriz
def matriz_det1(n):
# Se crea una matriz M_azar con todos sus elementos aleatorios
M_azar = np.random.randint(-10, 11, size=(n, n))
# Se elige al azar si se construye una matriz triangular superior o inferior
if np.random.randint(2):
# Triangular superior: se cogen los elementos de M_azar por encima de la diagonal
# con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
MU = np.triu(M_azar, k=1) + np.diag(np.random.choice([-1, 1], size=n))
else:
# Triangular inferior: se cogen los elementos de M_azar por debajo de la diagonal
# con el resto de elementos iguales a 0 y se le suma una matriz diagonal con elementos 1 y -1
MU = np.tril(M_azar, k=-1)+ np.diag(np.random.choice([-1, 1], size=n))
return MU
Ejemplo de matriz (10x10) creada con dicho algoritmo:
Teniendo resuelto el problema previo, ahora podemos abordar el problema original. Las matrices resultantes del algoritmo anterior tienen el "inconveniente" de no ser lo suficientemente aleatorias, dado que son triangulares y tienen demasiados elementos 0 no aleatorios.
Sin embargo, sabemos que:
- El determinante del producto de matrices es igual al producto de los determinates (|A·B|=|A|·|B|). Por tanto, si multiplicamos matrices cuyo determinante es 1 o -1 el resultado será una matriz cuyo determinante es 1 o -1.
- El producto de matrices triangulares no tiene porqué ser una matriz triangular.
Utilizando esto, podemos idear un algoritmo para el objetivo principal que consista en crear varias matrices triangulares resultantes del algoritmo anterior y multiplicarlas:
# Función para crear una matriz con determinante 1 o -1# mediante la multiplicación de matrices triangulares
# n es la dimensión de la matriz y m el número de iteraciones
def genU(n, m):
# Comenzamos con la matriz identidad
U = np.eye(n, dtype=int)
# Creamos "m" matrices triangulares con determinante 1 o -1 y las multiplicamos
for k in range(m):
U = U @ matriz_det1(n)
return U
Ejemplo de matriz creada con dicho algoritmo (n=5, m=10):
