# Magic square

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)