6
$\begingroup$

A magic square over $\mathbb{Z}$ is an n x n matrix whose entries are $\{1, \ldots, n^2\}$, with the sum of every row and column identical (in particular, my magic squares are all normal, but the sum of diagonal entries need not equal the sum of the rows/columns, which is necessarily $\frac{n(n^2+1)}{2}$). A magic square over $\mathbb{Z}_m$ is the same, except that $\{1, \ldots, n^2\}$ should be interpreted as a multiset of congruence classes modulo m.

Suppose I have an n x n magic square over $\mathbb{Z}_m$. Is there a simple way to tell if it is the image of a magic square over $\mathbb{Z}$ under the (element-wise) canonical projection map $a_{i,j} \mapsto a_{i,j}+m\mathbb{Z}$?

It's easy to come up with examples that are the image of a magic square. But not every one is. Two examples where this may fail are: $m=n=2$

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

and

$m=n=3$

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

Adding the identity to A in this case gives another counterexample of a slightly less trivial nature.

However, for $m=2$, $n=3$, every magic square over $\mathbb{Z}_2$ is the preimage of a magic square over $\mathbb{Z}$. This is extremely easy to see, since there are 5 ones and 4 zeros, so the matrix must be the image of the Lo Shu Square (up to permuting rows and columns).There are no magic squares with $m=3, n=2$. There are doable larger cases, but none of the ones I tried gave anything that seemed generic.

In general, what I would expect is that for m large compared to n, there won't be any additional ones; this is obvious if $m \ge n^3$ (better bounds are certainly possible). But for m small and n large, there might be more magic squares. And of course, if $m|n$ then cases like the 3x3 above will probably crop up.

The question I'm more interested in than the sort of general results above, though, is for a particular magic square over $\mathbb{Z}_m$, what is a fast way to check if it is the image of a magic square over $\mathbb{Z}$ (if such a way exists at all).

  • 0
    The conventions I have usually seen are not so rigid, namely for any $n \in \mathbb{Z}$, n indicates the element $n+m\mathbb{Z}$ in $\mathbb{Z}_m$. This may only be standard in physics, I'm not sure. Of course this is abuse of notation, and $[n]$ is more correct. In any case, the first paragraph states that all of them should be interpreted as congruence classes, though perhaps this was not clearly stated to extend to later paragraphs. Still, whether or not$3$is incorrect,$0$is certainly correct.2012-04-19

1 Answers 1

1

Write $A=mQ+R$, with the entries of $R$ in $[1,m]$ determined by the corresponding entry in the square over $\mathbb Z_m$ and $Q$ remaining to be determined. The values in $Q$ corresponding to a given value $r$ in $R$ must run from $0$ to $\lfloor(n-r)/m\rfloor$. The row and column sums of $R$ must have the required residue of $n(n^2+1)/2\bmod m$. Any multiples of $m$ in the row and column sums of $R$ yield contributions to the required row and column sums of $Q$, so $Q$ must be a modified magic square in which the row and column sums are almost the same but modified by the corresponding sums of $R$.

A quick check that's easy to perform manually and could be easily performed programmatically using backtracking is to check whether the parities of $Q$ can work out.

In your first example, $Q$ would have to contain two $0$s and two $1$s, and its row and column sums would all have to be $1$; thus the $1$s would have to be in different rows and columns, which is incompatible with $R$.

In your second example, the row sums of $Q$ would have to be $3$, $3$, $3$ and the columns sums $4$, $3$, $2$, respectively. The corresponding parities are $1$, $1$, $1$ and $0$, $1$, $0$ respectively. Again this is incompatible with $R$, which would require us to put exactly one value with parity $1$ into each column of $Q$.

Your third example, with the identity added to the second one, which you call a counterexample of a slightly less trivial nature, is, for the purposes of checking for a corresponding magic square over $\mathbb Z$, actually of a more trivial nature, since the row and column sums in this case have the wrong residue modulo $m$, so they can't possibly correspond to the required row and column sums in $\mathbb Z$.