Namespaces
Variants
Actions

Difference between revisions of "Magic square"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621101.png" /> array <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621102.png" /> composed of the integers from 1 up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621103.png" /> and satisfying the following conditions:
+
<!--
 +
m0621101.png
 +
$#A+1 = 54 n = 0
 +
$#C+1 = 54 : ~/encyclopedia/old_files/data/M062/M.0602110 Magic square
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621104.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621105.png" />. There are also more general magic squares, in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621106.png" /> is not required.
+
A square  $  n \times n $
 +
array  $  \| a _ {ij} \| $
 +
composed of the integers from 1 up to  $  n  ^ {2} $
 +
and satisfying the following conditions:
  
Any number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621108.png" />, is uniquely characterized by a pair of residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m0621109.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211010.png" /> (the digits to base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211011.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211012.png" />), that is, by the points of the two-dimensional space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211013.png" /> over the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211014.png" /> of residues modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211015.png" />. Since the coordinates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211016.png" /> of the cells of the square may also be regarded as the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211017.png" />, it follows that any distribution of the numbers from 1 up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211018.png" /> in an array <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211019.png" /> is given by a mapping
+
$$ \tag{* }
 +
\sum _ { i= } 1 ^ { n }
 +
a _ {ij}  = \
 +
\sum _ { j= } 1 ^ { n }
 +
a _ {ij}  = \
 +
\sum _ { i= } 1 ^ { n }
 +
a _ {ii}  = \
 +
\sum _ { i= } 1 ^ { n }
 +
a _ {i , n + 1 - i }
 +
= s ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211020.png" /></td> </tr></table>
+
where  $  s = n ( n  ^ {2} + 1 ) / 2 $.  
 +
There are also more general magic squares, in which  $  1 \leq  a _ {ij} \leq  n  ^ {2} $
 +
is not required.
  
that is, by a pair of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211022.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211023.png" />. The problem is to investigate those pairs that give magic squares. In general this has been done (see [[#References|[1]]]) only under the additional assumption of linearity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211025.png" />. It turns out, in particular, that magic squares with linear <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211027.png" /> exist for odd <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211028.png" /> only.
+
Any number  $  a $,
 +
$  1 \leq  a \leq  n  ^ {2} $,
 +
is uniquely characterized by a pair of residues  $  ( \alpha , \beta ) $
 +
$  \mathop{\rm mod}  n $(
 +
the digits to base  $  n $
 +
of  $  a - 1 $),  
 +
that is, by the points of the two-dimensional space  $  ( \mathbf Z / n )  ^ {2} $
 +
over the ring  $  \mathbf Z / n $
 +
of residues modulo  $  n $.  
 +
Since the coordinates  $  ( i , j ) $
 +
of the cells of the square may also be regarded as the elements of $  ( \mathbf Z / n )  ^ {2} $,  
 +
it follows that any distribution of the numbers from 1 up to  $  n  ^ {2} $
 +
in an array  $  \| a _ {ij} \| $
 +
is given by a mapping
  
Already in the Middle Ages a number of algorithms for constructing magic squares of odd order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211029.png" /> had been found. Each such algorithm is characterized by six residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211035.png" />, and is described by the following rules: 1) the number 1 is put into the cell <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211036.png" />; and 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211037.png" /> was put into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211038.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211039.png" /> is put into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211040.png" /> if that cell is still empty or into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211041.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211042.png" /> is occupied.
+
$$
 +
( \mathbf Z / n )  ^ {2}  \rightarrow \
 +
( \mathbf Z / n ) ^ {2} ,
 +
$$
  
The residues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211043.png" /> are not arbitrary but must satisfy certain conditions to ensure not only that (*) holds, but also that the algorithm is feasible, that is, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211044.png" /> is empty when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211045.png" /> is occupied. These conditions are easily found (see [[#References|[1]]]). Moreover, it turns out that a magic square can be constructed by an algorithm of this type if and only if the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211047.png" /> describing the square are linear.
+
that is, by a pair of functions  $  \alpha = \alpha ( i , j ) \in \mathbf Z / n $,
 +
$  \beta = \beta ( i , j ) \in \mathbf Z / n $,
 +
where  $  i , j \in \mathbf Z / n $.  
 +
The problem is to investigate those pairs that give magic squares. In general this has been done (see [[#References|[1]]]) only under the additional assumption of linearity of  $  \alpha $
 +
and  $  \beta $.  
 +
It turns out, in particular, that magic squares with linear  $  \alpha $
 +
and $  \beta $
 +
exist for odd  $  n $
 +
only.
  
Many algorithms for constructing magic squares are known (resulting in squares with non-linear <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211048.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211049.png" />), but there is no general theory for them (1989). Even the number of magic squares of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211050.png" /> is unknown (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211051.png" />; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211052.png" /> there is, up to obvious symmetries, only one magic square, whereas for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211053.png" /> there are 880 magic squares).
+
Already in the Middle Ages a number of algorithms for constructing magic squares of odd order  $  n $
 +
had been found. Each such algorithm is characterized by six residues  $  i _ {0} $,
 +
$  j _ {0} $,
 +
$  p $,
 +
$  q $,
 +
$  \overline{p}\; $,
 +
$  \overline{q}\; $,  
 +
and is described by the following rules: 1) the number 1 is put into the cell  $  ( i _ {0} , j _ {0} ) $;  
 +
and 2) if  $  a $
 +
was put into  $  ( i , j ) $,
 +
then  $  a + 1 $
 +
is put into  $  ( i + p , j + q ) $
 +
if that cell is still empty or into  $  ( i + \overline{p}\; , j + \overline{q}\; ) $
 +
if  $  ( i + p , j + q ) $
 +
is occupied.
  
Magic squares having additional symmetry have also been investigated, again only in very special circumstances (for example, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062110/m06211054.png" />; see [[#References|[2]]]).
+
The residues  $  i _ {0} , j _ {0} , p , q , \overline{p}\; , \overline{q}\; $
 +
are not arbitrary but must satisfy certain conditions to ensure not only that (*) holds, but also that the algorithm is feasible, that is, that  $  ( i + \overline{p}\; , j + \overline{q}\; ) $
 +
is empty when  $  ( i + p , j + q ) $
 +
is occupied. These conditions are easily found (see [[#References|[1]]]). Moreover, it turns out that a magic square can be constructed by an algorithm of this type if and only if the functions  $  \alpha $
 +
and  $  \beta $
 +
describing the square are linear.
 +
 
 +
Many algorithms for constructing magic squares are known (resulting in squares with non-linear  $  \alpha $
 +
and  $  \beta $),
 +
but there is no general theory for them (1989). Even the number of magic squares of order  $  n $
 +
is unknown (for  $  n \geq  5 $;
 +
for  $  n = 3 $
 +
there is, up to obvious symmetries, only one magic square, whereas for  $  n = 4 $
 +
there are 880 magic squares).
 +
 
 +
Magic squares having additional symmetry have also been investigated, again only in very special circumstances (for example, for $  n \leq  5 $;  
 +
see [[#References|[2]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M.M. Postnikov,  "Magic squares" , Moscow  (1964)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.Ya. Gurevich,  "The secret of the Ancient Talisman" , Moscow  (1969)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M.M. Postnikov,  "Magic squares" , Moscow  (1964)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.Ya. Gurevich,  "The secret of the Ancient Talisman" , Moscow  (1969)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 04:11, 6 June 2020


A square $ n \times n $ array $ \| a _ {ij} \| $ composed of the integers from 1 up to $ n ^ {2} $ and satisfying the following conditions:

$$ \tag{* } \sum _ { i= } 1 ^ { n } a _ {ij} = \ \sum _ { j= } 1 ^ { n } a _ {ij} = \ \sum _ { i= } 1 ^ { n } a _ {ii} = \ \sum _ { i= } 1 ^ { n } a _ {i , n + 1 - i } = s , $$

where $ s = n ( n ^ {2} + 1 ) / 2 $. There are also more general magic squares, in which $ 1 \leq a _ {ij} \leq n ^ {2} $ is not required.

Any number $ a $, $ 1 \leq a \leq n ^ {2} $, is uniquely characterized by a pair of residues $ ( \alpha , \beta ) $ $ \mathop{\rm mod} n $( the digits to base $ n $ of $ a - 1 $), that is, by the points of the two-dimensional space $ ( \mathbf Z / n ) ^ {2} $ over the ring $ \mathbf Z / n $ of residues modulo $ n $. Since the coordinates $ ( i , j ) $ of the cells of the square may also be regarded as the elements of $ ( \mathbf Z / n ) ^ {2} $, it follows that any distribution of the numbers from 1 up to $ n ^ {2} $ in an array $ \| a _ {ij} \| $ is given by a mapping

$$ ( \mathbf Z / n ) ^ {2} \rightarrow \ ( \mathbf Z / n ) ^ {2} , $$

that is, by a pair of functions $ \alpha = \alpha ( i , j ) \in \mathbf Z / n $, $ \beta = \beta ( i , j ) \in \mathbf Z / n $, where $ i , j \in \mathbf Z / n $. The problem is to investigate those pairs that give magic squares. In general this has been done (see [1]) only under the additional assumption of linearity of $ \alpha $ and $ \beta $. It turns out, in particular, that magic squares with linear $ \alpha $ and $ \beta $ exist for odd $ n $ only.

Already in the Middle Ages a number of algorithms for constructing magic squares of odd order $ n $ had been found. Each such algorithm is characterized by six residues $ i _ {0} $, $ j _ {0} $, $ p $, $ q $, $ \overline{p}\; $, $ \overline{q}\; $, and is described by the following rules: 1) the number 1 is put into the cell $ ( i _ {0} , j _ {0} ) $; and 2) if $ a $ was put into $ ( i , j ) $, then $ a + 1 $ is put into $ ( i + p , j + q ) $ if that cell is still empty or into $ ( i + \overline{p}\; , j + \overline{q}\; ) $ if $ ( i + p , j + q ) $ is occupied.

The residues $ i _ {0} , j _ {0} , p , q , \overline{p}\; , \overline{q}\; $ are not arbitrary but must satisfy certain conditions to ensure not only that (*) holds, but also that the algorithm is feasible, that is, that $ ( i + \overline{p}\; , j + \overline{q}\; ) $ is empty when $ ( i + p , j + q ) $ is occupied. These conditions are easily found (see [1]). Moreover, it turns out that a magic square can be constructed by an algorithm of this type if and only if the functions $ \alpha $ and $ \beta $ describing the square are linear.

Many algorithms for constructing magic squares are known (resulting in squares with non-linear $ \alpha $ and $ \beta $), but there is no general theory for them (1989). Even the number of magic squares of order $ n $ is unknown (for $ n \geq 5 $; for $ n = 3 $ there is, up to obvious symmetries, only one magic square, whereas for $ n = 4 $ there are 880 magic squares).

Magic squares having additional symmetry have also been investigated, again only in very special circumstances (for example, for $ n \leq 5 $; see [2]).

References

[1] M.M. Postnikov, "Magic squares" , Moscow (1964) (In Russian)
[2] E.Ya. Gurevich, "The secret of the Ancient Talisman" , Moscow (1969) (In Russian)

Comments

Magic squares have been considered since ancient times. For instance, the magic square of order 3 was known in China around 2000 B.C.. Dürer's famous "Melancholy" shows a magic square of order 4.

There is a close connection between (pairs of orthogonal) Latin squares (cf. Latin square; Orthogonal Latin squares) and magic squares, which has been studied since L. Euler (see [a1] and [a2]). See also [a3] and the references given there.

References

[a1] L. Euler, "De quadratis magicis" G. Kowalewski (ed.) , Opera Omnia Ser. 1; opera mat. , 7 , Teubner (1923) pp. 441–457
[a2] L. Euler, "Recherches sur une nouvelle espèce de quarrés magiques" G. Kowalewski (ed.) , Opera Omnia Ser. 1; opera mat. , 7 , Teubner (1923) pp. 291–392
[a3] J. Dénes, A.D. Keedwell, "Latin squares and their applications" , English Univ. Press (1974)
How to Cite This Entry:
Magic square. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Magic_square&oldid=13333
This article was adapted from an original article by M.M. Postnikov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article