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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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):
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:
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)$.
