Resolución de un sistema de ecuaciones mediante aritmética modular

Question

Estoy intentando implementar un solucionador para el juego lights out. Tienes una cuadrícula de luces, cuando haces clic en una de ellas la luz que has pulsado y sus cuatro vecinas cambian de color, y la luz vuelve a empezar cuando se le acaban los colores. El objetivo es conseguir que todas las luces tengan un color determinado.

Como la forma en que cambian los colores es cíclica, pensé que podría implementarlo como un sistema de ecuaciones y hacer todos los cálculos mod n (siendo n el número de colores disponibles).

Este método funcionó en algunos rompecabezas, pero me quedé atascado en otros.

Represento el juego como un sistema de ecuaciones en una matriz aumentada y lo reduzco a la forma escalonada reducida utilizando la eliminación gaussiana. Como he dicho, en algunos casos esto ha funcionado bien. Sin embargo hay algunos casos (ejemplo a seguir) donde termino con una línea que no puedo reducir completamente, la razón es que, como estoy usando aritmética modular, algunos valores no tienen una inversa multiplicativa por lo que me quedo atascado.

He aquí un ejemplo: El juego mostrado aquí representa una cuadrícula de 4x4 con 4 colores disponibles. Aquí está la matriz tal y como empezó:

1100100000000000 3
1110010000000000 3
0111001000000000 2
0011000100000000 3
1000110010000000 3
0100111001000000 3
0010011100100000 0
0001001100010000 0
0000100011001000 0
0000010011100100 0
0000001001110010 2
0000000100110001 1
0000000010001100 3
0000000001001110 1
0000000000100111 0
0000000000010011 0

y esto es lo máximo que he conseguido reducir:

1000000000000333 2
0100000000003323 3
0010000000003233 0
0001000000003330 0
0000100000001232 2
0000010000002003 2
0000001000003002 3
0000000100002321 3
0000000010001320 1
0000000001003332 1
0000000000102333 0
0000000000010231 2
0000000000000220 2
0000000000002222 0
0000000000002222 0
0000000000000220 2

En este caso, la última línea, por ejemplo, es ...220 2 y no puedo averiguar cómo puedo reducirlo ya que no puedo simplemente dividir por 2 (2 no tiene inverso multiplicativo en z4). Intente lo que intente, siempre termino con un 2 inicial en una fila. Estoy absolutamente seguro de que existe una solución para el juego (yo mismo lo resolví correctamente), pero no estoy seguro de si me estoy perdiendo algo aquí, o simplemente que el método simplemente no funciona para todos los casos.

Gracias

Editar: Se han corregido las matrices del ejemplo. Había incoherencias al final. Me he dado cuenta de que cualquier incoherencia allí significa que no hay solución. En el ejemplo actualizado sí existe una solución con seguridad, y esto hace que no haya incoherencias al final. Sin embargo, sigo sin poder resolverlo

Answer 1

A continuación se presenta un breve resumen de cómo se pueden resolver los sistemas lineales módulo cualquier número entero fijo $~n>0$ . Si $n$ es primo, la reducción gaussiana habitual del sistema funciona. Si $n$ es un producto de factores distintos relativamente primos $~n_i$ entonces, por el teorema del resto chino, el sistema es equivalente a la colección de sistemas que se obtienen a partir de él reduciendo en módulo $~n_i$ por cada $i$ . Suponiendo que cada uno de estos sistemas se pueda resolver (o demostrar que es inconsistente, lo que considero una forma de resolver) se pueden combinar las soluciones para obtener la solución del sistema original mediante el teorema chino del resto. En detalle: si el sistema reducido modula cualquier $~n_i$ es incoherente, por lo que el sistema original; en caso contrario, existen soluciones parametrizadas módulo cada $~n_i$ puede ser necesario introducir parámetros ficticios (que aparecen con el coeficiente $~0$ en todas partes) en algunos de ellos para forzar el mismo número de parámetros libres para cada $~n_i$ y luego se puede aplicar la TRC a una solución particular y a cada uno de los parámetros para elevar cada uno de ellos a un valor módulo $~n$ que da una solución parametrizada sobre $\def\Z{\Bbb Z}\Z/n\Z$ .

Así, se puede reducir al caso en que cada $n_i$ es una potencia primera; todavía hay que salvar la distancia entre las potencias primeras $p^k$ y el primer $~p$ . Para ello sugiero utilizar una forma de Elevación de Hensel * al sistema. En primer lugar, reduzca el sistema módulo $~p$ y resolverlo. Entonces, si hay alguna solución, eleva una de ellas arbitrariamente a un módulo de no solución $~p^2$ . A continuación, añada un múltiplo desconocido de $~p$ como término de corrección a la misma, y expresar la ecuación de que la suma se convierta en una solución verdadera módulo $~p^2$ ya que cualquier defecto de la no-solución levantada es un múltiplo de $~p$ se puede dividir un factor $~p$ a partir de las ecuaciones obtenidas, y obtener un sistema lineal módulo $~p$ que de nuevo puede resolverse mediante la eliminación gaussiana. Una vez elevado a $~p^2$ , continúan de forma similar para elevarse a potencias superiores de $~p$ , hasta llegar a $~p^k$ .

Esta idea tiene una complicación para la que ahora mismo no tengo respuesta. En general, las soluciones no serán únicas, sino parametrizadas; en principio, esto significa que hay que aplicar el levantamiento por separado a una solución particular y a la parte parametrizada (la solución del sistema homogéneo correspondiente). Sin embargo, parece que a veces la cuestión de si la solución particular puede ser levantada en absoluto a una potencia mayor de $~p$ puede depender de la elección de esa solución concreta. Si esto ocurre, significaría que durante el proceso de elevación habría que permitir la adaptación de la solución particular para evitar incoherencias en el conjunto de ecuaciones obtenidas. Esto sería un dolor de cabeza adicional, pero tal vez se pueda demostrar que esto nunca ocurre. Una cosa que ciertamente puede es que existe una solución modulo $~p$ pero no existe ningún módulo $~p^2$ ; esto a diferencia de la situación del lema de Hensel (que sólo trata una ecuación, pero que es no lineal). Un ejemplo trivial de esta situación es el sistema de ecuaciones $(x\equiv1,x\equiv3)\pmod4$ que es claramente inconsistente pero cuya reducción modulo $~2$ no lo es.

*Esto se debe en realidad a Schönemann Un matemático relativamente desconocido del siglo XIX que también formuló por primera vez el "criterio de Eisenstein" para la irreducibilidad de los polinomios.

Answer 2

Esta es una respuesta probablemente mucho más útil que la anterior. Cuando se resuelve un sistema de ecuaciones, se pueden utilizar libremente las operaciones de fila (como siempre modificando el lado derecho correspondientemente). Sin embargo, también se pueden permitir las operaciones de columna, siempre que se lleve la cuenta de ellas. Por ejemplo, se podría añadir el doble de la primera columna a la tercera, lo que equivale a sustituir la primera incógnita $x_1$ por un nuevo desconocido $x_1'=x_1-2x_3$ manteniendo todas las demás incógnitas $x_i$ (uno tiene $ax_1+cx_3=ax'_1+(2a+c)x_3$ para cualquier $a,c$ que explica el funcionamiento de la columna). Después de resolver el nuevo sistema, no hay que olvidar recuperar $x_1=x'_1+2x_3$ de la solución en términos de las nuevas variables. En términos matriciales, si modificamos el sistema $A\cdot x=b$ mediante operaciones de columna que equivalen a la multiplicación por la derecha de una matriz invertible $R$ Entonces tenemos un nuevo sistema $AR\cdot x'=b$ en términos de la variable $x'=R^{-1}\cdot x$ y al final se calcula $x=R\cdot x'$ . Así, cada operación de columna aplicada a $~A$ va acompañada de la el mismo operación de columna aplicada a $~R$ (que comienza como la identidad), y al final $R$ se aplica (desde la izquierda) al vector solución $x'$ para obtener la verdadera solución $x$ del sistema original.

Dado que se pueden mezclar las operaciones de filas y columnas (registrando estas últimas), ahora se puede disponer que cualquier pivote utilizado en última instancia divide todo las entradas restantes (las de abajo a la derecha), y también el módulo $~n$ . La forma de conseguirlo está inspirada en el algoritmo de Euclides, y es muy similar al algoritmo para reducir una matriz a su Forma normal de Smith . Básicamente se reduce continuamente el tamaño de la mínima entrada restante no nula $~d$ calculando el resto de la división euclidiana de otra entrada restante por $~d$ mientras esto sea posible (es decir, mientras $d$ no divide todas las demás): si esa otra entrada está en la misma fila o columna que $~d$ una sola operación de fila o columna será suficiente; si no, se realiza una operación de fila para hacer un no múltiplo de $~d$ aparecen en la columna de $~d$ de los cuales uno forma el resto mediante una operación de columna. Como diferencia con el algoritmo de la forma normal de Smith sobre $~\Bbb Z$ las entradas se definen ahora todas en módulo $~n$ y, por tanto, toda la aritmética se realiza en módulo $~n$ . De hecho, esto permite una importante operación adicional para reducir $~d$ : siempre que $d$ no divide $~n$ , sólo forma un múltiplo de su fila para que $~d$ se hace más pequeño después de la reducción modulo $~n$ se ve fácilmente que se puede reducir a $\gcd(d,n)$ de esta manera. En definitiva, aunque hay un gran número de posibilidades a considerar en general (el programa es más complicado que para la eliminación gaussiana), en la práctica la reducción de $~d$ es muy rápido, y la mayoría de las veces (hasta el final del procedimiento) se consigue reducirlo a $~1$ .

Con este algoritmo de forma normal el sistema $A\cdot x=b\pmod n$ puede transformarse en un sistema de este tipo en el que las únicas entradas no nulas de $~A'$ están en la diagonal principal, y cada una divide a su sucesora. Una vez en esta forma, la solución del sistema es obvia; para tener cualquier solución, cada entrada diagonal de $~A'$ debe dividir la entrada correspondiente de $~b$ (y en particular cada fila cero de $~A'$ debe tener la correspondiente entrada de $~b$ cero.