Generación de matrices unimodulares con elementos acotados

Question

¿Alguien sabe cuál es el algoritmo para generar matrices unimodulares aleatorias (matrices enteras con determinante $\pm 1$ ) cuyos elementos no superen un límite determinado? Se menciona un algoritmo de este tipo aquí y se facilita la siguiente referencia:

Jürgen Hausen, Generación de problemas de álgebra lineal , MapleTech Vol. 1, nº 2, 1994.

Sin embargo, parece que este documento ya no está disponible en línea. Si el algoritmo se basa en la forma normal de Hermite, ¿cómo aseguran que los elementos de la matriz generada están acotados por un número entero positivo dado? Muchas gracias de antemano por cualquier idea :-)

Answer 1

He intentado el siguiente enfoque

1. generan una matriz unimodular $A$ (posiblemente con entradas grandes)
2. arreglarlo para reducir el tamaño abs de las entradas

En 1, genero $n\times n$ matrices $L$ y $U$ con 1 en la diagonal; multiplícalos y permuta al azar filas y columnas.

En 2, repita hasta la "convergencia" el paso siguiente. Elija el elemento más grande en valor absoluto, suponga que es $a_{ij}$ . Elige una entrada aleatoria distinta de cero $a_{kj}$ en el $j$ -th columna, $k\ne i$ para reducir el tamaño de $a_{ij}$ con $a'_{i,.} = a_{i,.} + a_{k,.}$ .

genunimod <- function(n,k=5){
r <- trunc(sqrt(k))+1
A <- matrix(sample(-r:r,n**2,rep=T),n,n)
L <- matrix(0,n,n)
U <- matrix(0,n,n)
l <- outer(1:n,1:n,">")
u <- outer(1:n,1:n,"<")
L[l] <- A[l]
U[u] <- A[u]
diag(U) <- 1
diag(L) <- 1

p1 <- sample(1:n) #permutation shuffle rows
p2 <- sample(1:n) #permutation shuffle cols
P <- diag(rep(1,n)) # identity

A <- P[p1,] %*% L %*% U %*% P[p2,]
# this A is unimodular but may have large entries

m <- k+1
useless <- 0
steps <- 0
while(m>k & useless<=n**2){
    steps <- steps+1
    mm <- max(abs(A))
    v <- which(abs(A)==mm,arr.ind=T)[1,]        
    # use a random element to reduce element v by row
    k <- sample(which(A[,v[2]]!=0)[-v[1]],1)
    s <- sign(A[v[1],v[2]]*A[k,v[2]])
    A[v[1],] <- A[v[1],]-s*A[k,]
    m <- max(abs(A)) # new max term
    if(m>=mm) useless <- useless+1
    }
list(A=A,LU=P[p1,] %*% L %*% U %*% P[p2,],steps=steps,useless=useless)
}

El código puede fallar de varias maneras: el elemento más grande puede, en principio, estar situado en una columna por lo demás nula; un solo paso puede no tener éxito en la reducción de la entrada más grande y detengo los cálculos si más de $n^2$ tal inútil se producen pasos.

La eficacia puede mejorarse enormemente utilizando métodos menos primitivos (por ejemplo, utilizando ideas "pivotantes" en lugar de elegir al azar $k$ utilizando columnas y filas, etc.).

Se tarda 1,2 segundos (en un Macbook Air) en generar 1000 $5\times5$ matrices unimodulares con entradas $\leq 10$ . Nunca tuve una columna "por lo demás cero" (¡bien!) y experimenté 69 "fallos" (7\%, ¡menos bien!) debidos a demasiados pasos inútiles. Por lo tanto, se necesitaron 1,2 segundos para crear 931 matrices. Los dígitos tienen la siguiente distribución en forma de campana. Debería ser simétrica y se da más peso a los números pequeños.

Answer 2

No es una respuesta completa, pero es un comienzo. La cita es incorrecta, ya que el nombre del autor está mal escrito. Véase aquí (ir al vol.1 no.2), que desgraciadamente tiene el enlace deseado roto, pero aquí es una versión corregida de ese enlace. Por desgracia, el artículo no está, pero sí su resumen:

Este artículo presenta un método para crear ejercicios de álgebra lineal haciendo uso del generador de números aleatorios de Maple. La principal herramienta para ello es un procedimiento de Maple que genera matrices integrales unimodulares. La presentación también considera ejercicios estándar para temas básicos como la independencia lineal, las bases y el rango de una matriz.

Lo más importante es que el nombre del autor se escribe Hausen (no Hansen). Actualmente es profesor en la Universidad de Tubinga. Su sitio web es aquí Allí encontrará su dirección de correo electrónico. Aunque sus intereses de investigación parecen haberse alejado de la programación en Maple, le sugiero que se ponga en contacto con él directamente.

Answer 3

En primer lugar, la matriz unimodular $U$ que se obtiene al hacer una descomposición de Hermite $A=U R$ ( $U$ es unimodular, $R$ es triangular inferior) puede tener algunas entradas muy grandes. Numéricamente, he encontrado que para una matriz $A$ de dimensión $n\times n$ con sus entradas elegidas uniformemente al azar entre $\{0,\pm1\}$ la entrada máxima de $U$ se comporta aproximadamente como $$ \log \max(U) \approx 2(n-10) \log 2, \qquad n\geq 20, $$ por lo que para grandes dimensiones, el enfoque directo no funciona tan bien.

En segundo lugar, si no te importa mucho obtener una distribución posterior específica sobre las matrices unimodulares, existe un algoritmo muy sencillo. Sea $U$ sea una matriz triangular superior con unos en la diagonal y cuyas entradas por encima de la diagonal se eligen uniformemente al azar de un intervalo entero $I$ con magnitud máxima $a = \max\limits_{x\in I}|x|$ .

Claramente, $\det U=1$ . Entonces, si se forma una matriz $A = U_1 U_2^\top$ tendrá determinante $1$ y sus entradas serán como máximo $(n-1)^2 a^2$ . Sin embargo, sus entradas no se distribuirán uniformemente; por ejemplo, la entrada superior izquierda siempre será $1$ . También es posible tomar matrices como $U_1 U_2^\top U_3 U_4^\top$ que seguirá teniendo una distribución desigual de las entradas, pero un poco menos.

Para satisfacer un límite superior en los elementos de la matriz, debería bastar con elegir un valor suficientemente pequeño de $a$ y posiblemente generar varias matrices hasta que una de ellas tenga elementos suficientemente pequeños.

En tercer lugar, otra forma es dejar que $J_k$ sea la matriz identidad con las entradas no nulas en su $k$ -ésima columna sustituida por números enteros aleatorios. Entonces $\det J_k=1$ y la matriz $A=J_1J_2\cdots J_n$ tendrá $\det A=1$ aunque las distintas columnas tendrán distribuciones diferentes.

Si desea tener determinantes $-1$ elige al azar una permutación impar con una matriz $P$ , $\det P=-1$ y utilice $AP$ .