Construcción de cuadrados mágicos sobre$\mathbb{Z}$ de cuadrados mágicos sobre$\mathbb{Z}_m$

Question

Un cuadrado mágico $\mathbb{Z}$ es un n x n matriz cuyas entradas son $\{1, \ldots, n^2\}$, con la suma de cada fila y columna idénticos (en particular, mi cuadrados mágicos son normales, pero la suma de las entradas de la diagonal no necesita ser igual a la suma de las filas/columnas, que es necesariamente $\frac{n(n^2+1)}{2}$). Un cuadrado mágico $\mathbb{Z}_m$ es el mismo, excepto que $\{1, \ldots, n^2\}$ debe ser interpretado como un conjunto múltiple de clases de congruencia módulo m.

Supongamos que tengo un n x n cuadrado mágico $\mathbb{Z}_m$. Hay una manera sencilla de saber si es la imagen de un cuadrado mágico $\mathbb{Z}$ bajo (elemento-wise) canónica mapa de proyección $a_{i,j} \mapsto a_{i,j}+m\mathbb{Z}$?

Es fácil de llegar con ejemplos que son la imagen de un cuadrado mágico. Pero no cada uno es. Dos ejemplos en los que esto puede fallar son: $m=n=2$

$A= \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \end{array} \right)$

y

$m=n=3$

$A= \left( \begin{array}{ccc} 1 & 2 & 0 \\ 1 & 2 & 0 \\ 1 & 2 & 0 \end{array} \right) $

La adición de la identidad a Una en este caso le da otro contraejemplo de un poco menos trivial de la naturaleza.

Sin embargo, para $m=2$, $n=3$, cada cuadrado mágico $\mathbb{Z}_2$ es la preimagen de un cuadrado mágico $\mathbb{Z}$. Esto es muy fácil de ver, ya que hay 5 queridos y 4 ceros, por lo que la matriz debe ser la imagen de la Shu de la Plaza (hasta permuting filas y columnas).No hay cuadrados mágicos con $m=3, n=2$. Hay factible mayor de los casos, pero ninguno de los que he probado dieron algo que parecía genérico.

En general, lo que yo esperaría es que para m grande en comparación con n, no habrá ninguna adicionales; esto es obvio si $m \ge n^3$ (mejor los límites son ciertamente posible). Pero para m las pequeñas y n grande, no podría ser más cuadrados mágicos. Y por supuesto, si $m|n$, en casos como el de 3x3 por encima probablemente de los cultivos.

La pregunta que me interesa más que el tipo de los resultados generales de arriba, sin embargo, es una magia particular cuadrados en $\mathbb{Z}_m$, lo que es una forma rápida de comprobar si es la imagen de un cuadrado mágico $\mathbb{Z}$ (si tal manera que existe en absoluto).

Answer 1

Escribir $A=mQ+R$, con las entradas de $R$ $[1,m]$ determinado por la entrada correspondiente en la plaza de la $\mathbb Z_m$ $Q$ restante a ser determinado. Los valores de $Q$ correspondiente a un valor dado $r$ $R$ se debe ejecutar de$0$$\lfloor(n-r)/m\rfloor$. La fila y la columna de sumas de $R$ debe disponer de los residuos de $n(n^2+1)/2\bmod m$. Cualquier múltiplos de $m$ en la fila y la columna de sumas de $R$ el rendimiento de las contribuciones a la fila y columna de sumas de $Q$, lo $Q$ debe ser modificado cuadrado mágico en el que la fila y columna de sumas son casi la misma pero modificada por el correspondiente sumas de $R$.

Una comprobación rápida y fácil de realizar de forma manual y puede realizarse fácilmente mediante programación utilizando el retroceso es comprobar si las paridades de $Q$ puede trabajar.

En el primer ejemplo, $Q$ tendría que contienen dos $0$s y dos $1$s, y su fila y columna sumas todos tendrían que ser $1$; por lo tanto el $1$s tendría que ser en diferentes filas y columnas, lo cual es incompatible con $R$.

En el segundo ejemplo, la fila sumas de $Q$ tendría que ser $3$, $3$, $3$ y las columnas de sumas $4$, $3$, $2$, respectivamente. La correspondiente paridades son $1$, $1$, $1$ y $0$, $1$, $0$ respectivamente. De nuevo esto es incompatible con $R$, lo que nos obligaría a poner exactamente un valor con paridad $1$ en cada columna de $Q$.

Su tercer ejemplo, con la identidad añadido a la segunda, que llame a un contraejemplo de un poco menos trivial de la naturaleza, es decir, para los fines de la comprobación de una correspondiente cuadrado mágico $\mathbb Z$, en realidad más trivial de la naturaleza, desde la fila y la columna se suma en este caso se han equivocado de residuos modulo $m$, por lo que no es posible que corresponden a la fila y la columna de cantidades en $\mathbb Z$.