4
$\begingroup$

Magic square is a $n*n$ matrix with numbers of $1,2,...,n^2$ and has the property that sum of any row and any column and sum of main diameter and
adjunct diameter is identical. There exists a very simple algorithm to generate a magic square when $n$ is odd. What is the best algorithm for magic square with even size?

$\endgroup$
7
$\begingroup$

There is an extremely simple method attributed to Conway by Eric Weisstein, who describes it in a MathWorld article.

All formulas below assume that row and column indices are 1-based. We have to distinguish two cases, according to the residue of $n$ modulo $4$.

Case 1: $n = 4m$. An $n\times n$ magic square is given explicitly by the following rule, which is most easily explained by an example (taken from the article):

8x8 magic square

An entry on row $i$, column $j$ gets the value $(i-1)n + j$ if "uncrossed" and $n^2+1-((i-1)n+j)$ if "crossed". An entry $(i,j)$ is crossed if $i=4I+a$ and $j=4J+b$ for $a=b$ or $a=5-b$ (here $a,b \in \{1,2,3,4\}$).

Why does this work? If an entry $(i,j)$ is crossed then so is the entry $(n+1-i,n+1-j)$ (this is clear from the image). The value corresponding to the latter is $n^2+1-((n-i)n+n+1-j) = (i-1)n+j$, and this implies that all numbers appear in the square.

Now take any row, and partition it into groups of 4 entries. I claim that the sum of any such group is $2(n^2+1)$. Indeed, if the row is $4I+1$ or $4I+3$, then the entries are $n^2+1-x,x+1,x+2,n^2+1-(x+3)$, and we get this since $(x+1)+(x+2)=(x)+(x+3)$. The other case is similar.

Case 2: $n = 4m+2$, $n > 2$. Here the idea is to blow up a magic array of size $n/2 \times n/2$, which we already know how to generate. Again, an illustration (taken from the MathWorld article) will be helpful:

enter image description here

Generally speaking, we will blow up an original square of value $x$ into a new $2\times 2$ square containing the values $4(x-1)+1,4(x-1)+2,4(x-1)+3,4(x-1)+4$, according to the three different orders: $$ \begin{array}{ccc} \begin{array}{|c|c|} \hline 4(x-1)+4 & 4(x-1)+1 \\\hline 4(x-1)+2 & 4(x-1)+3 \\\hline \end{array} & \begin{array}{|c|c|} \hline 4(x-1)+1 & 4(x-1)+4 \\\hline 4(x-1)+2 & 4(x-1)+3 \\\hline \end{array} & \begin{array}{|c|c|} \hline 4(x-1)+1 & 4(x-1)+4 \\\hline 4(x-1)+3 & 4(x-1)+2 \\\hline \end{array} \\ L & U & X \end{array} $$

The blow-up guarantees that all numbers appear in the square.

The orders will be chosen as follows:

  • $m+1$ rows consisting only of Ls.
  • one row consisting only of Us.
  • $m-1$ rows consisting only of Xs. (Here we use $n>2$.)

To check that rows and columns sum to the correct number, notice that it's enough to check that the "residues" sum to a constant, the residues being the numbers $1,2,3,4$ which are added on top to the $4(x-1)$ above. This is because the original square was a magic square.

The rows in all gadgets sum to 5, and this takes care to the rows. The first columns in the gadgets $L,U,X$ sum to $6,3,4$, and so the total residue in an odd column is $6(m+1) + 3 + 4(m-1) = 10m+5 = 5(2m+1)$. The second columns in the gadgets $L,U,X$ sum to $4,7,6$, and so the total residue in an even column is $4(m+1) + 7 + 6(m-1) = 10m+5 = 5(2m+1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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