Comprobar la pertenencia a un grupo de matrices

Question

Estoy buscando un (preferiblemente un poco eficientes) algoritmo para este problema:

Dado un subgrupo normal de $SL(m, \mathbb{Z})$ generado por un conjunto finito $\{M_1, M_2, \dotsc, M_n\}$, y algunos $A \in SL(m, \mathbb{Z})$ $A$ en el subgrupo normal? Es decir, es $A$ un producto de los elementos de la generación del sistema?

Para la aplicación de estoy buscando a una existencia algoritmo estaría bien; yo en realidad no necesita saber qué producto produce $A$.

Edit: El fraseo original implícita conmutatividad, que es tonto y malo.

Actualización 2: @studiosus respuesta que me parezca bien, pero, si existe un eficiente-suficiente-para-usar el algoritmo, prefiero el premio de la recompensa allí.

Answer 1

Hay un ingrediente clave que hace que su problema solucionable a través de algoritmos:

Teorema. 1. Cada subgrupo normal de $\Gamma=SL(d,Z)$, $d\ge 3$, es ya sea central o ha finito índice en $\Gamma$. 2. Cada finitely generado normal subgrupo de $\Gamma=SL(2,Z)$, ya sea central o ha finito índice en $\Gamma$.

La parte 1 es debido a Margulis y es muy profundo, la parte 2 fue probablemente sabe de Poincaré y no es profundo. (Me pueden encontrar referencias si así lo desea).

Voy a dejar a elaborar un algoritmo que cubre la central de caso (es fácil) y considerar el "genérico" de la situación.

Ejecutar en paralelo de dos Máquinas de Turing:

T1 simplemente enumera reducido de palabras en el alfabeto $M_i^{\pm 1}, i=1,...,n$, de acuerdo a su longitud y comprueba si el correspondiente producto de matrices es igual a $A$.

T2 enumera los mapas de la escuela primaria matrices (generadores de $\Gamma$) a la permutación de grupos de $S_k$ (para cada una de las $k=2, 3, ...$) y comprueba si se define un homomorphism $f$ que envía matrices $M_i$ a la identidad de permutación. Al mismo tiempo, comprueba si $f(A)=1$.

Finalmente, una de estas máquinas de Turing se detiene y se ajusta de que cualquiera de las $A$ es el producto de matrices $M$ (es decir, si T1 wins) o $A$ no está en el subgrupo generado por a $M_i$'s (si T2 gana). Si $d\ge 3$ T2 puede ser sustituido por el siguiente:

T3: Enumerar los grupos finitos $SL(d, Z/k)$ donde $k$'s son números naturales. Para cada una de las $k$ calcular las reducciones de $A$ $M_i$'s modulo $k$ y comprobar si la reducción de $A$ es un producto de las reducciones de $M_i$'s. Si $A$ no está en el subgrupo generado por a $M_i$'s, a continuación, T3 eventualmente encontrarán $k$ que el mismo es cierto mod $k$. (La validez de este algoritmo depende de la Congruencia de los Subgrupos de la Propiedad que $SL(d, Z)$ tiene si y sólo si $d\ge 3$.)

Todos estos algoritmos son terriblemente ineficiente, pero yo no soy un programador.