Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
The last column in the second example should consist of $0$s instead of $3$s. –  joriki Apr 19 '12 at 22:40
    
3 was technically still correct, but after looking at it I prefer 0 also, so I've changed it. –  Logan Maingi Apr 19 '12 at 22:52
    
The conventional notation for the elements of $\mathbb Z_3$ is $0$, $1$, $2$. If you wanted to use the name $3$ instead, I think it would have to be introduced, and if you were thinking of $3$ as a representative rather than a name, it would have to be $[1]$, $[2]$, $[3]$ instead. –  joriki Apr 19 '12 at 22:57
    
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. –  Logan Maingi Apr 19 '12 at 23:10

1 Answer 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.