Most-perfect squares ^{∗}

David S. Brée and Kathleen Ollerenshaw^{†}

September 8, 1999

Keywords: magic squares, pandiagonal squares, combinatorics.

Abstract

We have developed a method for constructing and enumerating all squares of any size in an interesting class of magic squares, which we call ‘mostperfect.’ This is the first time, in the thousand years during which magic squares have challenged mathematicians, that a method of construction, let alone enumeration, has been found for a whole class of magic square. In mostperfect squares integers come in complementary pairs along the diagonals and any 2×2 block of four adjacent integers add to the same sum. These properties ensure that most-perfect squares are pandiagonal magic squares. A method of constructing and a formula for enumerating all most-perfect squares are given.

At least since Euler, and most probably much earlier, there has been an interest in generating ‘magic squares’ of different sizes [12]. Let A be an m × n matrix with entries in ℕ:

A : Δ_{m} × Δ_{n} → ℕ where Δ_{n} = {k ∈ ℕ|k < n}.

∗Sumbitted to Discrete Mathematics. Our thanks to Peter Aczel for the proofs in Section 4.4 †Both authors are at the Computer Science Department, University of Manchester, Oxford Road, Manchester, UK M13 9PL. Email: bree@cs.man.ac.uk

A(i, j), for (i, j) ∈ Δ_{m} × Δ_{n}, is the natural number occurring in row i and column j of A, where rows and columns are numbered from zero.

Definition 0.1 A is normal if every natural number less than nm occurs in the matrix, necessarily exactly once; ie A : Δ_{n} × Δ_{m} → Δ_{nm} is a bijection.

Definition 0.2 A is a magic square if m = n and its entries are arranged in such a way that the sums of the integers in every row, column or either principal diagonal are all the same.

∀(i ∈ Δ_{n}) ∑_{j∈Δ_{n}} A(i, j) = ∑_{j∈Δ_{n}} A(j, i) = ∑_{j∈Δ_{n}} A(j, j) = ∑_{j∈Δ_{n}} A(j, n − 1 − j).

Methods for generating at least one normal magic square for any size n ≥ 3 are well known. However, generating all magic squares is difficult and has only been completed for n = 3, for n = 4 originally by enumeration by Frénicle de Bessey [7] and then analytically by Ollerenshaw and Bondi [16], and for n = 5 by exhaustion by Schroeppel [10]. Attention has turned to generating all of a class of magic square, namely ‘pandiagonal magic squares’ in which all diagonals, not only the two principal diagonals, have the same sum.

Definition 0.3 A path [i, j] is a sequence of positions in an n × n square that can be reached from a starting position by moving i rows down and j columns to the right, n times and then returning to the starting position. Whenever the path encounters an edge of the square, it wraps around to the opposite side of the square.

Definition 0.4 A diagonal is any [1, 1] or [1, −1] path.

Definition 0.5 A pandiagonal magic square is a magic square in which the integers in every diagonal have the same sum, ie

∀(i ∈ Δ_{n}) ∑_{j∈Δ_{n}} A(i, j) = ∑_{j∈Δ_{n}} A(j, i) = ∑_{j∈Δ_{n}} A(j, i + j) = ∑_{j∈Δ_{n}} A(j, i − j).

Pandiagonal magic squares were recognised by Euler [6] but interest lay dormant until they were rediscovered in the 1860s by Frost [8], who showed that there are no singly-even (ie with n a multiple of 2 but not of 4) pandiagonal squares. Methods are known for generating a pandiagonal magic square of any size, eg using pairs of orthogonal pandiagonal Latin squares (Euler’s method [5] [3] [4] [22]). However, a large proportion of pandiagonal squares for all values of n (n not singly even, for which there are no pandiagonal magic squares [9]) cannot be made using Latin squares. Some - but not all [2] - of these other pandiagonal squares can be made by adding a pair of auxiliary squares constructed using two non-intersecting paths (Frost [9], Bellew [1]), eg the chess knight’s paths [1, 2] and [2, 1]. Rosser and Walker [20] have a third method that enables all pandiagonal squares to be constructed for n ≤ 5, but only some of them for larger values of n. Recently it has been shown [21] that Rosser and Walker’s method, if suitably extended, generates the same squares as a generalisation of the methods of Frost and Bellew, using any pair of non-intersecting paths.

Attention was briefly paid to a subclass of pandiagonal squares having ‘most perfect form’ but only by McClintock [13]. For odd n this most perfect form required that any pair of integers at positions that are reflections in the centre position of a normal pandiagonal magic square, have a constant sum. For even n we need some definitions:

Definition 0.6 Each integer in a matrix has four adjacent integers: to its left and right in the same row and above and below it in the same column.

Definition 0.7 A 2 × 2 block consists of four adjacent integers, ie the set

∀(i ∈ Δ_{m}, j ∈ Δ_{n}){A(i, j), A(i, j + 1), A(i + 1, j), A(i + 1, j + 1)}

Rows 0 and m − 1 are adjacent, as are columns 0 and n − 1. For example, the integers at (m − 1, n − 1), (0, n − 1), (m − 1, 0) and (0, 0) form a 2 × 2 block of adjacent integers.

Definition 0.8 A pair of integers in an m × n matrix A are S-complements if their sum is S = nm − 1.

Definition 0.9 When n is doubly even, ie an integral multiple of 4, most-perfect squares are n by n normal squares containing n^{2} integers arranged in such a way that any pair of integers distant n/2 along any diagonal are S-complements and the sum of any 2 × 2 block of adjacent integers within the square is equal to 2S, ie.

∀(i ∈ Δ_{n}, j ∈ Δ_{n}) A(i, j) + A(i + n/2, j + n/2) = n^{2} − 1;

∀(i ∈ Δ_{n}, j ∈ Δ_{n}) A(i, j) + A(i, j + 1) + A(i + 1, j) + A(i + 1, j + 1) = 2(n^{2} − 1).

Note that most-perfect squares are only defined for doubly-even values of n. We will be concerned here only with squares with most perfect form when n is doubly even.

Two magic squares are essentially different if one is not the reflection of the other in either of the central axes or in the main diagonal, ie the path [1,1], or some combination of these reflections. (Reflection in the other principal diagonal, [1,-1], is a combination of all three of these reflections.) Consequently magic squares come in subsets of 8 that are not essentially different. Numbers of magic squares are traditionally given for essentially different squares, eg there is only one essentially different magic square for n = 3. Here we give the total number of most-perfect squares, including those that are not essentially different.

There are 48 × 8 pandiagonal magic squares with n = 4, all of which are mostperfect [19]. The number of most-perfect squares when n = 8 is known to be 368, 640 × 8 [14].

In this paper, Rosser and Walker’s [20] method of constructing some pandiagonal squares is restricted to give just the most-perfect squares. This new method requires that a ‘standardised reversible square’ is first constructed, then, optionally, converted into an ordinary reversible square, which is then transformed into a most-perfect square. It is shown that there is a one-to-one correspondence between these reversible squares and the resulting most-perfect squares. Formulae are developed for the enumeration of reversible squares associated with each standardised reversible square, and of the standardised reversible squares themselves.

1 Most-perfect squares and reversible matrices

It is not easy to construct most-perfect squares directly. Here we will show how they can be constructed from ‘reversible’ squares. In the next section we will show that there is a bijection between these two types of square. But first we show that most-perfect squares, as defined in 0.9, are indeed pandiagonal magic squares.

1.1 Most-perfect squares are pandiagonal magic squares

McClintock [13] introduced squares of most perfect form as being a subclass of pandiagonal magic squares. Here it is shown that squares that are most-perfect are necessarily pandiagonal magic squares.

Lemma 1.1 The integers in any row of a most-perfect square have the same sum, nS/2.

Proof. Two adjacent rows of a most-perfect square are made up of n/2 2 × 2 blocks, whose integers each sum to 2S. Therefore, the sum of the 2n integers in any two adjacent rows is constant. Consider three adjacent rows. The sums of the top pair of rows and of the bottom pair of rows are the same, namely nS. Subtracting the sum of the integers in the common middle row from these sums means that the top row and bottom bottom of the three have the same sum. By induction, all rows with the same parity have the same sum.

Consider a pair of rows n/2 apart. As n is doubly even, these rows must have the same parity and hence the same sum. Moreover, by Definition 0.9 each integer in one row is the S-complement of an integer in the other row, so the sum of these two rows must be nS. Hence each row must sum to nS/2. This is true whether the pair of rows are both odd or both even, so all rows have the same sum. □

Lemma 1.2 The integers in any column of a most-perfect square have the same sum, nS/2.

Proof. This is similar to the proof of Lemma 1.1 □

Lemma 1.3 The integers in any diagonal, including broken diagonals, of a mostperfect square have the same sum, nS/2.

Proof. Any integer in a most-perfect square is the S-complement of the integer distant n/2 along a diagonal, hence the sum of all the integers in a diagonal is nS/2. □

Theorem 1.1 A most-perfect square is a pandiagonal square.

Proof. This follows from Lemmas 1.1, 1.2 and 1.3, by Definition 0.9. □

1.2 Reversible and primitive squares

Most-perfect squares will be constructed by a transformation from reversible squares. First some definitions.

Definition 1.1 A is primitive if the integers at the opposite corners of any rectangle within the matrix have equal sums [20], a property here called equal cross sums, ie

∀(i, i′, j, j′ ∈ Δ_{n}) A(i, j) + A(i′, j′) = A(i, j′) + A(i′, j).

Definition 1.2 A is row reversible if the sums of pairs of integers at positions that are reflections in the midpoints of any row are constant, ie

∀(j ∈ Δ_{n}) A(i, j) + A(i, n − 1 − j) is constant, for any i ∈ Δ_{n}.

Definition 1.3 A is column reversible if the sums of pairs of integers at positions that are reflections in the midpoints of any column are constant, ie

∀(i ∈ Δ_{n}) A(i, j) + A(n − i − i, j) is constant, for any j ∈ Δ_{n}.

Definition 1.4 A is reversible if it is primitive and also row and column reversible.

1.3 Transforming reversible squares into most-perfect squares

It will now be shown that every doubly-even reversible n × n square will be transformed into a different most-perfect square by Transform 1.1.

Transform 1.1

1. Interchange columns so that the order of the integers in the right half of each row is reversed, ie interchange columns n/2 + j and n − 1 − j , for all j < n/4.

2. Interchange rows so that the order of the integers in the bottom half of each column is reversed, ie interchange rows n/2 + i and n − 1 − i , for all i < n/4.

3. Move every integer from its position (i, j) to the position (i + jn/2, j + (i + j)n/2) for all i × j, where all position coordinates are taken modulo n.

Lemma 1.4 Every reversible square is transformed into a different square by Transform 1.1.

Proof. At every step of Transform 1.1, each integer either remains where it is or is swapped with an integer in a different position. This is obvious for Steps 1 and 2. For Step 3 the integers in even columns stay in the same row, whereas the integers in odd columns are always swapped with an integer in the row distant n/2. If the original integer is in a position with equal parity (ie the row and column have the same parity), then the swap (if there needs to be one) is with the integer in the same column, whereas if the integer is in a position with unequal parity, the swap is with an integer in the column distant n/2. Consequently, any change to the original reversible square will result Transform 1.1 generating a different square. □

It will now be shown that the square that results from the application of Transform 1.1 to a reversible square has the defining properties of a most-perfect square (Definition 0.9). First some properties of the square resulting from Steps 1 and 2 will be established. Definition 1.5 An intermediary square is the one formed by applying just Steps 1 and 2 of the Transform 1.1 to a reversible square. Lemma 1.5 Interchanging any pair of rows or columns in a primitive matrix gives a matrix that is also primitive, ie the property of equal cross sums is preserved. Proof. Every rectangle in the matrix with a pair of interchanged rows or columns was also a rectangle in the original matrix [20]. □

Lemma 1.6 An intermediary square is a primitive square. Proof. A reversible square is a primitive matrix (Definition 1.4) and Steps 1 and 2 of Transform 1.1 are simply row or column interchanges which preserve the property of being a primitive square (Lemma 1.5). □

To show that integers distant n/2 along a diagonal in the transformed square are S-complements we show that these integers came from positions in the reversible square that were reflections in the midpoint of the square and that these are Scomplements.

Lemma 1.7 Any pair of integers that are reflections in the midpoint of a reversible matrix are S-complements.

Proof. Consider any pair of integers that are at positions that are reflections in the midpoint of a reversible matrix, say integers x = A(i, j) and x′ = A(n − 1 − i, n − 1 − j). They specify a rectangle, ie the integers of the pair are at opposite corners of the rectangle. Let the integers at the other pair of opposite corners of the rectangle be y = A(i, n − 1 − j) and y′ = A(n − 1 − i, j). Take any other integer in the same row as x and y, say u = A(i, j′)|j′ ≠ j, and its reflection in the midpoint, u′ = A(n − 1 − i, n − 1 − j′), which will be in the same row as x′ and y′. Consider the rectangle specified by u and u′; let the integers at the other pair of opposite corners of this rectangle be v = A(i, n − 1 − j′) and v′ = A(n − 1 − i, j′). These integers will be positioned as follows:

\begin{matrix}… & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \\ … & x & … & u & … & … & v & … & y & … \\ … & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \\ … & ⋮ & … & ⋮ & … & … & z & … & ⋮ & … \\ … & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \\ … & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \\ … & ⋮ & … & z′ & … & … & ⋮ & … & ⋮ & … \\ … & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \\ … & y′ & … & v′ & … & … & u′ & … & x′ & … \\ … & ⋮ & … & ⋮ & … & … & ⋮ & … & ⋮ & … \end{matrix}

Now: x + x′ = y + y′, by equal cross sums;
u + u′ = v + v′, by equal cross sums;
x + y = u + v, by reversible row;
x′ + y′ = u′ + v′, by reversible row.
So:  x + x′ = v + v′, by addition and division by 2.

That is, the sum of the original pair of integers, x and x′, is the same as the sum of any other pair of integers, v and v′, that are also reflections in the midpoint of the matrix, with v and v′ being in the same row as x and x′, respectively. A similar argument shows that the same is true for v and v′ with any other pair of integers that are reflections in the midpoint and in the same columns as v and v′, respectively. In particular the pair of integers v and v′ have the same sum as any other pair of integers, z = A(i′, n − 1 − j′)|i′ ≠ i and z′ = A(n − 1 − i′, j′), that are reflections in the midpoint and are in the same columns as v and v′, respectively. Hence x and x′ have the same sum as z and z′, ie the sum of any pair of integers that are reflections in the midpoint of the matrix is constant.

The sum of all integers in the matrix is mnS/2 and there are mn/2 such pairs, so the sum of each of these pairs that are reflections in the midpoint of the matrix must be S. □

Lemma 1.8 Integers that are distant n/2 along a diagonal in the intermediary square will be S-complements. Proof. Consider pairs of integers that are reflections of each other in the midpoint of a reversible square. One integer from each such pair must be in the top half of the square, in either the left or right quadrant. An integer in the top left quadrant of a reversible square, ie at position (i, j) with i, j < n/2, will not have moved after Steps 1 and 2. The other integer of the pair, at the position that is a reflection of (i, j), ie at (n − 1 − i, n − 1 − j), will be moved by Steps 1 and 2 to the position (i + n/2, j + n/2). Therefore integers forming this pair, that were originally at positions that were reflections in the midpoint, are now, in the intermediary square, at positions that are distant n/2 along a diagonal.

Consider now an integer in the top right quadrant of a reversible square, ie at position (i, j) with i < n/2 ≤ j < n. By Step 1 it will have moved to (i, (3n/2) − 1 − j), where it stays after Step 2. The other integer of the pair, which was at the position that is a reflection of (i, j), ie at (n − 1 − i, n − 1 − j), will be moved by Step 2 to the position (i + n/2, n − 1 − j). Hence these two integers, that were originally at positions that were reflections in the midpoint of the reversible square, are now at positions that are also distant n/2 along a diagonal in the intermediary square.

Therefore all pairs of integers that were at positions that were reflections in the midpoint of the reversible square will be moved to positions that are distant n/2 along a diagonal in the intermediary square. By Lemma 1.7 these integers are S-complements. □

Lemma 1.9 Integers distant n/2 along a diagonal in a square obtained by applying Transform 1.1 to a reversible square are S-complements.

Proof. Two integers that are n/2 apart a diagonal of the intermediary square are also distant n/2 along a diagonal of the square after Step 3. The reason for this is that, as the parity of the rows and columns of positions distant n/2 along a diagonal is the same, the transformation in Step 3 either leaves the two integers in the same place, or moves them both the same distance. But integers distant n/2 along a diagonal in the intermediate square are S-complements (Lemma 1.8). Hence, integers distant n/2 along a diagonal in the final square are S-complements as well. □

Lemma 1.9 establishes one of the defining properties of a most-perfect square. We now turn to the other.

Definition 1.6 A horizontal couplet is a pair of adjacent integers in the same row, ie the pair ∀(i ∈ Δm, j ∈ Δn){A(i, j), A(i, j + 1)}.

Lemma 1.10 The four integers in a 2 × 2 block in a square obtained by applying Transform 1.1 to a reversible square sum to 2S.

Proof. Consider a horizontal couplet in the intermediary square, say at positions (i, j) and (i, j + 1), together with the horizontal couplet in the same columns but in row i + 1 + n/2. The four integers are at the corners of a rectangle, so have equal cross sums (Lemma 1.6). Take one pair of opposite corners of this rectangle, say at (i, j+1) and (i+1+n/2, j). By Lemma 1.9, the integers at these positions are each S-complements of integers distant n/2 along a diagonal, ie at (i + n/2, j + 1 + n/2) and (i+1, j +n/2) respectively. Consequently, the sum of the integers at these two positions, together with the two integers at the other pair of opposite corners of the original rectangle, is 2S, ie the four integers at (i+n/2, j +1+n/2), (i+1, j +n/2) and (i, j), (i + 1 + n/2, j + 1) in the intermediary square sum to 2S.

Applying Step 3 of Transform 1.1 moves the integers at these four positions as follows (recall that the positions are given modulo n and that n is doubly even, so that n^{2}/4 = 0 modulo 4):

(i, j) to (i + jn/2, j + (i + j)n/2),
(i + n/2, j + 1 + n/2) to (i + (1 + j + 1 + n/2)n/2,
j + 1 + (1 + i + n/2 + j + 1 + n/2)n/2)
= (i + jn/2, j + 1 + (i + j)n/2),
(i + 1, j + n/2) to (i + 1 + (j + n/2)n/2,
j + (1 + i + 1 + j + n/2)n/2)
= (i + 1 + jn/2, j + (i + j)n/2),
(i + 1 + n/2, j + 1) to (i + 1 + (1 + j + 1)n/2,
j + 1 + (i + 1 + n/2 + j + 1)n/2)
= (i + 1 + jn/2, j + 1 + (i + j)n/2).

Hence, the integers in these positions in the transformed square also sum to 2S. But note that these four positions form a 2 × 2 block. This is the other property of most-perfect squares. Conversely, any 2 × 2 block from the transformed square must have come from four positions in the intermediary square that are related by (i, j), (i + 1 + n/2, j + 1), (i + n/2, j + 1 + n/2) and (i + 1, j + n/2), and so must sum to 2S. □

Theorem 1.2 Every doubly-even reversible square is transformed by Transform 1.1 into a different most-perfect square.

Proof. By Lemmas 1.9 and 1.10, the Definition 0.9 of a most-perfect square is satisfied. By Lemma 1.4 each of these most-perfect squares is different. □

2 Correspondence between most-perfect and re-

versible squares

In order later to enumerate most-perfect squares by counting doubly-even reversible squares, it is necessary not only that all doubly-even reversible squares can be transformed into different most-perfect squares, as has just been shown, but also that every most-perfect square must always have come from a different doubly-even reversible square. Here it is shown that the inverse of Transform 1.1, when applied to a most-perfect square, results in a doubly-even reversible square.

The inverse transform to be applied to any most-perfect square is: Transform 2.1

1. Move every integer from its position (i, j) to the position (i + jn/2, j + (i + j)n/2), where all positions are taken modulo n.

2. Interchange rows so that the order of the integers in the bottom half of each column is reversed, ie interchange rows i + n/2 and n − 1 − i, for all i < n/4.

3. Interchange columns so that the order of the integers in the right half of each

row is reversed, ie interchange columns j + n/2 and n − 1 − j, for all j < n/4. Note that Step 1 of Transform 2.1 is identical to Step 3 of Transform 1.1. This is correct as:

• by Step 3 of Transform 1.1, the integer at the position (i, j) in an intermediary square moves to the position (i + jn/2, j + (i + j)n/2) in the most-perfect square; • by Step 1 of Transform 2.1, this integer, originally at the position (i+jn/2, j+

(i + j)n/2) in the most-perfect square, will be moved to:

(i + jn/2 + (j + (i + j)n/2)n/2, j + (i + j)n/2 + (i + jn/2 + j + (i + j)n/2)n/2)

= (i + jn + (i + j)n^{2}/4, j + (i + j)n + (i + 2j)n^{2}/4)
= (i, j) modulo n,

as n^{2}/4 = 0 modulo n, since n is doubly even, ie back to where it came from in the intermediary square.

To show that the transformed square is not only a primitive square but also a reversible square, we first establish a property of most-perfect squares. Lemma 2.1 The sum of the two integers in horizontal couplets that are in the same two adjacent columns and in rows with the same parity of a most-perfect square, is constant. Proof. Consider three horizontal couplets in the same two columns and in three adjacent rows, ie one above the other. The middle horizontal couplet forms a 2 × 2 block with both the top and bottom couplet. By Definition 0.9, the four integers in both these two 2 × 2 blocks have the same sum, 2S. Subtracting the middle couplet from this sum shows that the top and bottom couplet have the same sum. This argument can be repeated for all horizontal couplets in the same column but in alternate rows. □

Lemma 2.2 All pairs of integers distant n/2 along a row and in even columns of a most-perfect square have the same sum; similarly for pairs in odd columns; and these two sums together add to 2S. Proof. Consider a horizontal couplet in the left half of the square. By Lemma 2.1 its integers have the same sum as the integers in a horizontal couplet in the same two adjacent columns but in a row n/2 up (or down). By Definition 0.9, the S-complements of the integers in this second horizontal couplet are in a third horizontal couplet in the right half of the square, in a row distant n/2 and in columns also distant n/2. Therefore the first and third horizontal couplets are in the same row but distant n/2 from each other. Their four integers sum to 2S.

Take two horizontal couplets, B = {A(i, j−1), A(i, j)} and C = {A(i, j), A(i, j+ 1)}, in the same half of the square and with one integer in common, and the two horizontal couplets that are distant n/2 along the same row, B′ = {A(i, j − 1 + n/2), A(i, j+n/2)} and C′ = {A(i, j+n/2), A(i, j+1+n/2)} respectively, as shown:

B  B′
… b x c . . . . . . b′ x c′ …
C  C′

It has just been shown that ∑ B +∑ B′ = ∑ C +∑ C′ = 2S, where ∑ X is the sum of the integers in the pair X. Rearranging gives ∑ B − ∑ C = ∑ C′ − ∑ B′. Now ∑ B − ∑ C is the difference between a pair of integers, b = A(i, j − 1) and c = A(i, j+1), in the same row and same half of the square, separated by one column; ∑ C′ −∑ B′ is the difference between another pair of integers, c′ = A(i, j +1+n/2) and b′ = A(i, j − 1 + n/2), separated from each other by one column and distant n/2 from b, c respectively. Therefore, b + b′ = c + c′, ie the sum of a pair of integers distant n/2 along a row, is the same as a pair of integers also distant n/2 along the same row, but separated by one column. This holds for all such pairs of pairs, ie any pair of integers distant n/2 along the same row and in columns with the same parity have the same sum. □

Likewise it can be shown that: Lemma 2.3 Any pair of integers distant n/2 up (or down) the same column and in rows with the same parity have the same sum; and that the sum for the pairs in even rows and the pairs in odd rows together add to 2S.

We now use this property of most-perfect squares to show that they are transformed into reversible squares by Transform 2.1. We first prove that the transformed square is row and column reversible and then that the square is primitive. Lemma 2.4 The rows of the square obtained by applying Transform 2.1 to a mostperfect square are reversible. Proof. Let Q be the square obtained by applying Step 1 of Transform 2.1 to an n × n most-perfect square P. Then, as Step 1 of Transform 2.1 is the same as Step 3 of Transform 1.1:

Q(i, j) = P (i + jn/2, j + (i + j)n/2),
ie, Q(i, j) = \{ \begin{matrix}P (i, j + in/2) & j even; \\ P (i + n/2, j + in/2 + n/2) & j odd. \end{matrix}

Consequently, Q(i, j) + Q(i, j + n/2)

= \{ \begin{matrix}P (i, j + in/2) + P (i, j + in/2 + n/2)  j even; \\ P (i + n/2, j + in/2 + n/2) + P (i + n/2, j + in/2) \\ = 2S − (P (i, j + in/2) + P (i, j + in/2 + n/2)) j odd. \end{matrix}

From Lemma 2.2, Q(i, j) + Q(i, j + n/2) is constant for any row i, ie any pair of integers distant n/2 in a row of the square Q have a constant sum.

Step 2 of Transform 2.1 only interchanges rows and so preserves this property. Step 3 reverses integers in the right half of each row; consequently, in the final square all pairs of integers Q(i, j) and Q(i, 3n/2−1−(j +n/2)) = Q(i, n−1−j), ie pairs of integers that are reflections in the midpoint, have a constant sum. Hence, the rows are reversible. □

Lemma 2.5 The columns of the square obtained by applying Transform 2.1 to a most-perfect square are reversible.

Proof. The proof is similar to that of Lemma 2.4, but using Lemma 2.3 instead of Lemma 2.2. □

Lemma 2.6 Any 2 × 2 block in the square obtained by applying Step 1 of Transform 2.1 to a most-perfect square has equal cross sums.

Proof. Consider a 2 × 2 block in the square Q with top left corner at the position (i, j). The difference between the sums of the integers at opposite corners is: Q(i, j) + Q(i + 1, j + 1) − (Q(i, j + 1) + Q(i + 1, j))

= P (i + jn/2, j + (i + j)n/2) + P (i + 1 + (j + 1)n/2, j + 1 + (i + j + 2)n/2)

− P (i + (j + 1)n/2, j + 1 + (i + j + 1)n/2) − P (i + 1 + jn/2, j + (i + j + 1)n/2)

by Step 1 of Transform 2.1;

= P (i + jn/2, j + (i + j)n/2) + P (i + 1 + jn/2 + n/2, j + 1 + (i + j)n/2)

− S + P (i + jn/2, j + 1 + (i + j)n/2) − S + P (i + 1 + jn/2 + n/2, j + (i + j)n/2)

by Definition 0.9;

= P (i + jn/2, j + (i + j)n/2) + P (i + jn/2, j + (i + j)n/2 + 1)

+ P (i + jn/2 + 1 + n/2, j + (i + j)n/2) + P (i + jn/2 + 1 + n/2, j + (i + j)n/2 + 1) − 2S

by rearranging terms;

= P (i + jn/2, j + (i + j)n/2) + P (i + jn/2, j + (i + j)n/2 + 1)

+ P (i + jn/2 + 1, j + (i + j)n/2) + P (i + jn/2 + 1, j + (i + j)n/2 + 1) − 2S

by Lemma 2.1;

= 0  by Definition 0.9.

Therefore any 2 × 2 block in the square Q has equal cross sums. □

Lemma 2.7 The square resulting from applying Transform 2.1 to a most-perfect square is a primitive square.

Proof. Consider two 2 × 2 blocks in the square Q with one column in common as shown:

… a c e … where a = A(i, j − 1), c = A(i, j), e = A(i, j + 1)
… b d f … and b = A(i + 1, j − 1), d = A(i + 1, j), f = A(i + 1, j + 1).

Note that: a − b = c − d = e − f by equal cross sums of 2 × 2 blocks in the intermediary square (Lemma 2.6), so a + f = b + e, ie the 2 × 3 rectangle also has the property of equal cross sums. This can be generalised to any size of rectangle. Consequently all rectangles in the intermediary square have equal cross sums and so the intermediary square is a primitive square.

Interchanging pairs of rows or columns preserves the property of equal cross sums (Lemma 1.5), so Steps 2 and 3 of the inverse transform preserve equal cross sums. Consequently the final square also has equal cross sums, ie it is a primitive square by Definition 1.1. □

Theorem 2.1 The square obtained by applying Transform 2.1 to a most-perfect square is a doubly-even reversible square.

Proof. By Lemma 2.7 the resulting square is primitive and by Lemmas 2.4 and 2.5, the rows and columns of the resulting square are reversible. Hence, by Definition 1.4, the resulting square is a reversible square. All most-perfect squares are doubly even, so the final square is also doubly even. □

Theorem 2.2 There is a one-to-one correspondence between most-perfect and doublyeven reversible squares.

Proof. It has been shown both that Transform 1.1 applied to a doubly-even reversible square always gives a different most-perfect square (Theorem 1.2) and that the Transform 2.1 applied to a most-perfect square always gives a different doublyeven reversible square (Theorem 2.1). □

3 Standardised reversible matrices

Both to construct and to enumerate reversible matrices it is useful to arrange them in groups, with matrices in each group being reachable from any other matrix in the group by certain row and column interchanges. One matrix in each group is then chosen to be the standard matrix. The structure of standardised primitive matrices is then investigated in order to develop a method for constructing all such matrices. Finally in this section it is shown that standardised primitive matrices are equivalent to standardised reversible matrices.

3.1 Standardising reversible matrices

Definition 3.1 Row and column interchanges applied to a reversible matrix are legitimate if the result is still a reversible matrix.

For each group of reversible matrices there is just one matrix that is considered the standardised form.

Definition 3.2 A is monotone if

∀(i, i′ ∈ Δ_{m}, j, j′ ∈ Δ_{n}) i ≤ i′&j ≤ j′ ⟹ A(i, j) ≤ A(i′, j′).

Definition 3.3 A is (row) standardised if it is monotone and A(0, 1) = 1.

Definition 3.4 A is a column standardised if A^{t} is row standardised.

Lemma 3.1 Interchanging any pair of rows or columns of a reversible matrix results in a primitive matrix.

Proof. A reversible matrix is a primitive matrix (Definition 1.4) and any row or column interchanges applied to a primitive matrix result in a primitive matrix (Lemma 1.5). □

However, not all such interchanges will retain the properties of row and column reversibility:

Definition 3.5 Symmetric rows/columns are rows/columns that are reflections in the mid horizontal/vertical axis, respectively.

Lemma 3.2 Interchanging a pair of symmetric rows of a reversible matrix retains the properties of row and column reversibility.

Proof. Pairs of integers in any column of a reversible matrix that are in symmetric rows have a constant sum, by Definition 1.4, so the interchange of their two rows will still result in the same sum. Also this interchange does not affect any individual row. □

Similarly, Lemma 3.3 Interchanging a pair of symmetric columns of a reversible matrix retains the properties of row and column reversibility.

Lemma 3.4 If two rows in one half of a reversible matrix are interchanged and their symmetric rows in the other half of the matrix are also interchanged, then the resulting matrix is still reversible.

Proof. If rows i and h are the rows interchanged in one half of the matrix (eg i, h ≤ m/2) and rows i′ = n − 1 − i and h′ = n − 1 − h are the rows symmetric to i and h in the other half of the matrix (eg m/2 ≤ i′, h′ < m) that are also interchanged, then in any column j, the symmetric positions (i, j) and (i′, j) will now have the integers originally at (h, j) and (h′, j) and vice versa. Therefore, any column j is still reversible. As the rows themselves are not affected they will still be reversible, so the resulting matrix will retain the property of reversible rows and columns. □

Likewise, Lemma 3.5 If two columns in one half of a reversible matrix are interchanged and their symmetric columns in the other half are also interchanged, the resulting matrix will still have reversible rows and columns. Lemma 3.6 The transpose of a reversible matrix will be row and column reversible. Proof. All the rows and columns are interchanged but their order is retained. □

Any reversible matrix can be standardised in the following manner: Transform 3.1

1. Select the row in which the integer 0 is to be found. Until the integers in the left half of this row are in ascending order, apply column interchanges as follows, starting with 0 as the current integer up to the largest integer in this row:

(a) If the current integer is in the right half of the matrix, then interchange its column with the symmetric column in the left half of the matrix.

(b) If the current integer is in the left half of the matrix but not in the correct column, interchange its present column with the column in which it should be placed and, at the same time, interchange the symmetric columns in the other half of the matrix.

(c) Update the current integer to the next highest integer in this row.

2. Repeat Step 1 but with “rows” for “columns”.

3. If the integer 1 is in column 0 rather than row 0, then transpose the matrix.

Lemma 3.7 Transform 3.1 applied to a reversible matrix will always terminate.

Proof. To prove that Transform 3.1 terminates, it is sufficient to show that while an integer, say c, is being brought to its correct column and row, the integers less than c are not disturbed.

1. Let the row in which 0 is located be row i. Let the correct position for the current integer c be A(i, k), ie ∀(j ∈ Δ_{n}|j < k) A(i, j) < c. Note that the column interchanges in Steps 1a and 1b preserve row reversibility.

• If k ≥ n/2 then, as integers in the left half of the row are in ascending order, so are those in the right half (by row reversibility). Therefore, c is in its correct place, ie A(i, k) = c.

• If A(i, k) = c, no column interchanges are required.

• If k < n/2, by row reversibility, ∀(j ∈ Δ_{n}|j < k) A(i, n − 1 − j) > c. So c must lie between columns k and n − 1 − k:

– If c is in the right half of row i, then Step 1a will interchange its column with the symmetric column in the left half, but this will not be to the left of column k.

– If c is in the left half of row i, then Step 1b will interchange its column with column k and also their two symmetric columns in the right half of the square.

In both cases, columns to the left of column k will not be disturbed.

2. The proof proceeds likewise with “rows” substituted for “columns” in Step 1.

3. The integer 1 must always be either in the same row or the same column as 0. If this were not so, then 0 and 1 would define a rectangle with equal cross sums. But no other pair of integers between 0 and nm − 1 can add to 1, so this is not possible.

Hence the process will terminate and result in a reversible matrix in which the integers down the left column are in ascending order and the integers along the top row from left to right are also in ascending order, starting with 0 1. □

Theorem 3.1 Transform 3.1 will transform any reversible matrix into a standardised reversible matrix.

Proof. Applying Transform 3.1 to a reversible matrix terminates (Lemma 3.7) and results in a matrix A′. Step 1 of Transform 3.1 ensures that integers in the row in A′ containing 0 are in ascending order, in particular that 0 is in the left column. Step 2 ensures that the integers in the left column are in ascending order and so 0 is in the top row.

As Transform 3.1 applies only legitimate row and column interchanges to a reversible matrix, A′ is also reversible (Lemma 1.5). Therefore, any integer in A′, A′(i, j), that is not in the top row or left column, is, by equal cross sums: A′(i, 0)+A′(0, j)−0. As the top row of A′ is in ascending order, A′(0, j′) < A′(0, j) for all j′ < j, and so all integers in any row i that are to the left of (i, j) are less than A′(i, j). Likewise all integers in column j that are above (i, j) are less than A′(i, j). Therefore A′ is monotone. Step 3 ensures that the top row begins with 0 1. Therefore, by Definition 3.3, A′ is standardised. □

In order to enumerate a set of reversible matrices, it needs to be shown that:

Theorem 3.2 All the reversible matrices in the same set as a standardised reversible matrix can be reached from that matrix by legitimate row and column interchanges and by transposing the matrix.

Proof. If a row interchange is required other than a legitimate one, then let the two rows being interchanged be i and h (h ≠ i, n − 1 − i). If rows i and h are now interchanged, two possibilities arise:

• If rows i and h are in the same half of the matrix, then their symmetric rows in the other half must be interchanged to maintain column reversibility, but this, if accompanied by an interchange of their symmetric rows in the other half of the matrix, is a legitimate row interchange. If it is not so accompanied, then the columns in the matrix are no longer reversible as the matrix is normal.

• If rows i and h are in different halves of the matrix, then for any column j the integers in row i and h will be A(h, j) and A(i, j) respectively. As in a normal matrix A(i, j) ≠ A(h, j), to preserve column reversibility the integers at (n − 1 − i, j) and (n − 1 − h, j) must be A(n − i − h, j) and A(n − 1 − i, j) respectively. But this can be achieved with three legitimate row interchanges, namely interchanging row i with row n − 1 − i, row h with row n − 1 − h and then the new rows at i and n − 1 − h (which are in the same half of the matrix) and their symmetric new rows at n − 1 − i and h in the other half of the matrix.

A similar argument holds for two column interchanges. □

3.2 The structure of standardised primitive matrices

To construct all standardised reversible matrices it is necessary to know their structure. For standardised primitive squares Rosser and Walker [20] show that:

Lemma 3.8 The rows of any standardised primitive matrix consist of sequences of consecutive integers.

Proof. (Not that given in [20]) Let c_{1}(c_{1} ≤ n) be the length of such sequences, if they exist. Consider placing the integers one by one consecutively in the m × n matrix, beginning with 0. The top row must then begin with 0 followed by c_{1} − 1 consecutive integers; as 1 is always at (0, 1) the minimum value of c_{1} is 2. The sequence of consecutive integers ends with c_{1} − 1. As the integer at (0, c_{1}) is greater than c_{1} and the integers less than c_{1} have already been placed, the integer c_{1} must then be placed at (1, 0). By equal cross sums, this must begin a sequence of c_{1} consecutive integers in row 1. The next integer, 2c_{1}, can either be placed at (0, c_{1}) or at (2, 0). If it is placed at (2, 0) it must again, by equal cross sums, begin a sequence of c_{1} consecutive integers. Eventually a multiple of c_{1}, say r_{1}c_{1}, r_{1} ≤ m, must be placed at (0, c_{1}). By equal cross sums, the integer (r_{1} + 1)c_{1} must be placed at (1, c_{1}). There is nowhere else for the integers r_{1}c_{1} + 1 to (r_{1} + 1)c_{1} − 1 to be placed except along the top row in the positions (0, c_{1} + 1) to (0, 2c_{1} − 1), without violating the requirement for integers to be in ascending order. If c_{1} > n/2, it would not be possible to place all the integers from r_{1}c_{1} + 1 to (r_{1} + 1)c_{1} − 1 and so a standardised reversible matrix could not be completed. If c_{1} = n/2, the top row is now complete. Otherwise, ie if c_{1} < n/2, as all the integers in columns to the left of 2c_{1} must, by equal cross sums, be in sequences of length c_{1}, the integer at (0, 3c_{1}) must be a multiple of c_{1}. The same argument is repeated to show that this must begin a sequence of c_{1} consecutive integers. By induction, the top row must consist of n/c_{1} sequences of c_{1} consecutive integers, where c_{1} is a factor of n. By equal cross sums, every row of the matrix must consist of sequences of c_{1} consecutive integers.

□

Definition 3.6 A sequence of proper factors of n is a set of different proper factors of n, the smallest factor being greater than 1 and the largest factor being a proper factor of n, arranged in such a way that each factor in the sequence is a proper factor of its following factor.

For example, all the sequences of proper factors of n = 12 are: [], [2], [4], [3], [6], [2, 4], [2, 6] and [3, 6]; whereas, [1], [12] and [2, 3, 4] are NOT sequences of proper factors of 12.

Theorem 3.3 The m × n normalised primitive matrices are parameterised by two sequences of proper factors, of m and of n, in which the length of the sequence for n is the same or one more than the length of the sequence for m.

Proof. Given in [21] (based on [17]). □

If m = n = 12, the pairs of sequences could be any of the 42 combinations indicated by a ‘+’ in Table 1, but no others. One such sequence is to be used for the columns at which there are breaks in consecutive integers in the rows of the primitive square, the other sequence is for the rows in which there are breaks in the sequences of integers in the columns.

3.3 Construction of standardised primitive matrices

It has just been shown in Theorem 3.3 that all standardised primitive matrices can be constructed by selecting two sequences of proper factors of m and of n. These factors are used to construct the left column and top row of the standardised primitive matrix. The rest of the matrix is constructed using equal cross sums.

Construction 3.1 (Based on [17].) Suppose that the sequence of f proper factors of m giving the rows at which breaks in the sequences of integers in the columns occur, is:

Table 1: Permitted combinations of a pair of sequences of proper factors, n = 12

Sequence of proper  Sequence of proper factors for columns
factors for rows [] [2] [4] [3] [6] [2,4] [2,6] [3,6]
[] + + + + +
[2]  + + + + +  +  +
[4]  + + + + +  +  +
[3]  + + + + +  +  +
[6]  + + + + +  +  +
[2,4]  +  +  +
[2,6]  +  +  +
[3,6]  +  +  +

r_{1} < r_{2} < … < r_{f} (1 = r_{0} < r_{1}, r_{f} < r_{f+1} = m); and that the sequence of f or f + 1 proper factors of n giving the columns at which breaks in the sequences of integers in the rows occur, is:

c_{1} < c_{2} < … < c_{f}[< c_{f+1}] (1 = c_{0} < c_{1}, c_{f+1} ≤ c_{f+2} = n). To construct a reversible matrix A using two sequences of proper factors both of length f or with one of length f and the other of length f + 1:

1. If the number of factors in each sequence is the same, then set c_{f+1} = n.

2. Set A(0, 0) = 0.

3. Create the top row by, for h = 0 step 1 up to f + 1:

• for g = 1 step 1 up to (c_{h+1}/c_{h}) − 1: – let shift = g ∗ c_{h} and shiftsize = shift ∗ r_{h};

– for j = 0 step 1 up to c_{h}−1, set A(0, shift+j) = shiftsize+A(0, j).

4. Create the left column by, for h = 0 step 1 up to f:

• for g = 1 step 1 up to (r_{h+1}/r_{h}) − 1:

Table 2: A 12 by 12 standardised reversible square

0 1  6  7 12 13 36 37 42 43 48 49
2 3  8  9 14 15 38 39 44 45 50 51
4 5 10 11 16 17 40 41 46 47 52 53
18 19 24 25 30 31 54 55 60 61 66 67
20 21 26 27 32 33 56 57 62 63 68 69
22 23 28 29 34 35 58 59 64 65 70 71
72 73 78 79 84 85 108 109 114 115 120 121
74 75 80 81 86 87 110 111 116 117 122 123
76 77 82 83 88 89 112 113 118 119 124 125
90 91 96 97 102 103 126 127 132 133 138 139
92 93 98 99 104 105 128 129 134 135 140 141
94 95 100 101 106 107 130 131 136 137 142 143

– let shift = g ∗ r_{h} and shiftsize = shift ∗ c_{h+1};

– for j = 0 step 1 up to r_{h} −1, set A(shift+j, 0) = shiftsize+A(j, 0).

5. Fill in the rest of the matrix by, for i = 1 step 1 up to m − 1:

• for j = 1 step 1 up to n − 1 set A(i, j) = A(i, 0) + A(0, j).

For example, with m = n = 12, f = 2, column factors 2, 6 (ie c_{1} = 2, c_{2} = 6) and row factors 3, 6 (ie r_{1} = 3, r_{2} = 6), the completed square is shown in Table 2.

Theorem 3.4 Construction 3.1 results in a standardised primitive matrix.

Proof. The matrix that results from Construction 3.1 is a primitive matrix as it has been constructed using the property of equal cross sums (Step 5). The integer 0 is placed at (0, 0) by Step 2 of the Construction 3.1 and the integer 1 is placed at (0, 1) by Step 3 with h = 0, g = 1 and j = 0; hence, the top row begins with the integers 0 1. As the integers in the top row have been arranged in ascending order from left to right and the integers in the left column in ascending order from top to bottom and the rest of the integers have been determined using equal cross sums, the integers are in ascending order in all the rows from left to right and in all the columns from top to bottom. From Definitions 1.1 and 3.3 the matrix is a standardised primitive matrix. □

3.4 A standardised primitive matrix is a standardised re-

versible matrix

A standardised primitive matrix A will now be shown to be a standardised reversible matrix. Hence, all standardised reversible matrices can be constructed by Construction 3.1.

To prove that a standardised primitive matrix is also a reversible matrix, it is sufficient to show that both the rows and the columns are reversible.

Definition 3.7 Two sequences of integers are similar if the difference between integers in the same relative positions in each sequence is constant.

Lemma 3.9 Assuming that the sequence of integers along the top row of the standardised primitive matrix from (0, 0) to (0, c_{i−1} − 1) is reversible, the sequence of integers along the top row from (0, 0) to (0, c_{i} − 1) would then also be reversible.

Proof. From Construction 3.1, for i > 0 the partial top row from (0, 0) to (0, c_{i} −1) is made up of g = c_{i}/c_{i−1} sequences of c_{i−1} integers similar to the integers from (0, 0) to (0, c_{i−1} − 1), with each sequence beginning with an integral multiple of c_{i−1}r_{i−1}. When g is even, then there are equal numbers of sequences in either half of the partial top row from (0, 0) to (0, c_{i−1}); when g is odd, then the middle sequence straddles the midpoint of this partial top row symmetrically. The pairs of integers equidistant from either end of this partial top row are:

hc_{i−1}r_{i−1} + c_{0, j} and (g − 1 − h)c_{i−1}r_{i−1} + c_{0, c_{i−1}−1−j}, for all values of j (j < c_{i} − 1) and h (h < g/2 if g is even; h < (g + 1)/2 if g is odd). Their sum is:

(g − 1)c_{i−1}r_{i−1} + c_{0, j} + c_{0, c_{i−1}−1−j}. As the sequence of integers from (0, 0) to (0, c_{i−1} − 1) has been assumed to be reversible, c_{0, j} + c_{0, c_{i−1}−1−j} is constant, and so this sum is constant for all values of j and h. Therefore the partial top row from (0, 0) to (0, c_{i} −1) is also reversible.

□

Lemma 3.10 The rows of the matrix resulting from Construction 3.1 are reversible.

Proof. By Construction 3.1, the sequence of integers from (0, 0) to (0, c_{1} − 1) is made up of c_{1} consecutive integers, beginning with 0, and so is a reversible sequence. Therefore, by induction using Lemma 3.9, the sequences of integers from (0, 0) to (0, c_{i} − 1) are reversible for all i ≤ (f + 2). As c_{f+2} = n, the top row of the entire matrix is reversible. Consequently, as the matrix is a primitive matrix (Theorem 3.4) by equal cross sums, every row of the matrix is reversible. □

Lemma 3.11 The columns of the matrix resulting from Construction 3.1 are reversible.

Proof. Assuming that the sequence of integers in the left column from (0, 0) to (r_{i−1}−1, 0) is reversible, then so is the sequence of integers from (0, 0) to (r_{i}−1, 0) for any i > 1. The proof follows that of Lemma 3.9. For i = 1 the sequence at the top of the left-most column is, by Construction 3.1: 0, c_{1}, 2c_{1}, 3c_{1}, …, (r_{1} − 1)c_{1}, which is reversible. Hence, by induction, the sequence of integers from (0, 0) to (0, n − 1), ie the entire left column, is reversible. Consequently, as the matrix is a primitive matrix (Theorem 3.4) by equal cross sums, every column of the matrix is reversible. □

Theorem 3.5 Construction 3.1 always results in a standardised reversible matrix and every standardised reversible matrix can be constructed using Construction 3.1.

Proof. By Theorem 3.4, Construction 3.1 always results in a standardised primitive matrix. By Lemmas 3.10 and 3.11 the rows and columns of these matrices are reversible. This fulfills the Definition 3.3 of a standardised reversible matrix and proves the first half of Theorem 3.5. A standardised reversible matrix is a standardised primitive matrix by Definitions 3.3 and 3.3. All standardised primitive matrices can be constructed using Construction 3.1, from two sequences of proper factors of n (Theorem 3.3). Therefore all standardised reversible matrices can be constructed using Construction 3.1. □

4 Enumeration of reversible matrices

We wish to count the number of most-perfect squares of size n, where n is doubly even, by enumerating reversible squares of size n. Although Rosser and Walker [20] provided the basis of a method for constructing primitive squares, they did not give a method for their enumeration. We first enumerate standardised reversible m × n matrices. Then we count the number of reversible matrices corresponding to each standardised reversible matrix. This will give the total number of reversible matrices and so the total number of most-perfect squares.

4.1 Enumeration of standardised reversible matrices

Let W_{f}(n) be the number of ways of choosing a sequence of f proper factors of n, including the empty sequence but excluding the sequences [1] and [n], ie

W_{f}(n) = ∑_{n′∈Z_{n}} W_{f−1}(n′), where Z_{n} is the set of proper factors of n, 1 and n excluded, ie

Z_{n} = {k > 0|k divides n} − {1, n};

W_{0}(0) = 0; W_{0}(n) = 1, n > 0, ie the empty sequence.

Theorem 4.1 For all m, n ∈ ℕ, the total number of standardised reversible m × n matrices is

Equation 4.1 N(m, n) = ∑_{f} W_{f}(m)(W_{f}(n) + W_{f+1}(n)).

Proof. (By induction on m and n.) Assume that for any m′, n′ which are proper factors of m, n, respectively:

N(m′, n′) = ∑_{f} W_{f}(m′)(W_{f}(n′) + W_{f+1}(n′)). For the singleton matrix there is only one standardised reversible matrix, namely [0], and indeed

N(1, 1) = W_{0}(1)(W_{0}(1) + W_{1}(1)) = 1(1 + 0) = 1 as required. A general m×n standardised reversible matrix has one of the following structures:

• It was constructed using two empty sequences of proper factors, ie A(i, j) = ni + j. There is just one such standardised reversible matrix.

• It was constructed using a sequence of just one factor of n, {n′}, for the columns and an empty sequence for the rows: A(i, j) = ⌊j/n′⌋(m − 1)n′ + in′ + j. There are W_{1}(n) of these, ie the number of ways of selecting just one proper factor of n.

• It was constructed from two non-empty sequences of proper factors, one for columns with the highest proper factor of n being n′, and one for rows, with highest proper factor of m being m′. By the induction assumption, the number of such matrices is:

∑_{m′∈Z_{m}} ∑_{n′∈Z_{n}} ∑_{f} W_{f}(m′)(W_{f}(n′) + W_{f+1}(n′))
= ∑_{f} ∑_{m′∈Z_{m}} W_{f}(m′) ∑_{n′∈Z_{n}}(W_{f}(n′) + W_{f+1}(n′)
= ∑_{f} W_{f+1}(m)(W_{f+1}(n) + W_{f+2}(n))

Therefore the total number of standardised reversible squares is:

N(m, n) = 1 + W_{1}(n) + ∑_{f} W_{f+1}(m)(W_{f+1}(n) + W_{f+2}(n))
= W_{0}(m)(W_{0}(n) + W_{1}(n)) + ∑_{f} W_{f+1}(m)(W_{f+1}(n) + W_{f+2}(n))
= ∑_{f} W_{f}(m)(W_{f}(n) + W_{f+1}(n))  □

Clearly if f < 0, W_{f}(n) = 0. Also, if f is greater than the maximum number of possible factors, then again W_{f}(n) = 0, so the summation in Equation 4.1 is computable. It remains to find a formula for the non-zero values of W_{f}(n).

4.2 When m = n = 2^{r}

Lemma 4.1 The number of ways, W_{f}(n), of choosing f different sequences of proper factors when n = 2^{r}, r > 1, is \binom{r−1}{f}.

Proof. The number of proper factors of n that are between 1 and n = 2^{r}, is r − 1. For any two such factors, one is always a proper factor of the other. □

Substituting this value for W_{f}(n) and W_{f}(m) in Equation 4.1 gives:

N(2^{r}, 2^{r}) = ∑_{f} \binom{r−1}{f} \{\binom{r−1}{f} + \binom{r−1}{f+1}\}
= ∑_{f} \binom{r−1}{f}\binom{r}{f+1}  by Identity 5.8 in [11],
= \binom{2r−1}{r}  by Identity 5.23 in [11],

confirming a conjecture by Ollerenshaw [15].

4.3 When m = n = 2^{r}p^{s}

When n is a product of a power of 2 and a power of one other prime, ie n = 2^{r}p^{s}, p any prime > 2 and r, s ∈ ℕ|r > 1, then the maximum number of proper factors in a sequence of proper factors of n, that are between 1 and n, is r + s − 1. To enumerate the ways of choosing a sequence of f proper factors from these factors, we introduce:

Definition 4.1 A step in a sequence of proper factors of n = 2^{r}p^{s} is where the power of 2 stops increasing and the power of p starts increasing.

In any sequence of proper factors of n there are a number of steps. Consider first full length sequences consisting of exactly r + s − 1 proper factors. Such full length sequences start at 2^{0}p^{0} (which is not itself included the sequence), go to the first step, and then progress from one step to the next, eventually reaching 2^{r}p^{s} (which again is not itself included the sequence). A sequence progress to the next step, say at 2^{r′}p^{s′}, by first incrementing the power of p to s′ and then incrementing the power of 2 to r′. Consequently for the first step, if there is one, r′ > 0 and for the final step s′ < s. Some full length sequences, showing just the powers of 2 and p, ie 01 stands for 2^{0}p^{1}, are:

Full length sequences :  Steps at:
01, 02, …, 0s, 1s, …, (r − 1)s  −
10, 20, …, r0, r1, …, r(s − 1)  r0
01, 02, …, 0(s − 2), 1(s − 2), 1(s − 1), 1s, … (r − 1)s  1(s − 2)
01, … 0(s − 2), 1(s − 2), 2(s − 2), 2(s − 1), 3(s − 1), 3s, … (r − 1)s 1(s − 2), 2(s − 1)

The number of ways of choosing full length sequences with exactly i steps is the number of ways of choosing i values of r′ between 1 and r and i values of s′ between 0 and s − 1, ie \binom{r}{i}\binom{s}{i}.

Lemma 4.2 The number of ways, W_{f}(n), of selecting sequences of f proper factors of n = 2^{r}p^{s}, p any prime > 2 and r, s ∈ ℕ|r > 1, is ∑_{i} \binom{r}{i}\binom{s}{i}\binom{r+s−1−i}{f−i}, where the summation is over all values of i.

Proof. To avoid double counting, the number of ways of choosing sequences of f proper factors of n, each sequence is first selected by choosing i ≤ f values of the powers of 2, in the range 1 to r, and i values of powers of p, in the range 0 to s − 1, which, when combined pairwise, give i proper (step) factors. The number of ways of doing this is \binom{r}{i}\binom{s}{i}.

Then the remaining (f − i) proper factors are chosen from among the other (non-step) factors along the full length sequence specified by these i steps. As there are still r + s − 1 − i proper factors along the full length sequence not yet chosen, there are \binom{r+s−1−i}{f−i} ways of selecting these remaining (f − i) factors. Therefore the total number of sequences of f proper factors is ∑_{i} \binom{r}{i}\binom{s}{i}\binom{r+s−1−i}{f−i}.

□

Terms in this series are zero for i < 0 and i > minimum[r, s, f]. The Zeilberger [18] algorithm shows that there is no closed form solution to this series. Consequently, these values for W_{f}(n) and W_{f+1}(n) must be substituted into Equation 4.1, to obtain a value for N(2^{r}p^{s}, 2^{r}p^{s}). When this is done and the result simplified using standard identities from [11] (see Table 3), we get:

Equation 4.2 N(2^{r}p^{s}, 2^{r}p^{s}) = \frac{1}{2} \binom{2s}{s} ∑_{i} \binom{s}{i}\binom{r+s}{r−i}\binom{2r+s−i}{r+s}.

Some of these identities from [11] have pre-conditions for their application that are not shown here. We have proved (in chapter 6 of [17]) that these preconditions are either met or met except for the borderline case and, further, that the equality still holds for these borderline cases in this context. The application of the Identity 5.28 in [11] is non-trivial; see Ollerenshaw and Brée [17] chapter 6 for details on how it has been applied here.

Even though Zeilberger’s algorithm [18] finds a recursive relation for the remaining summation under i, Petkovšek’s algorithm [18], hyper, shows that the recursive relation has no closed form solution. Equation 4.2 confirms a conjecture of Ollerenshaw deposited with M. Gardner in 1992.

Table 3: Deriving N(2^{r}p^{s}, 2^{r}p^{s})

N(2^{r}p^{s}, 2^{r}p^{s})

= ∑_{f} ∑_{i} \binom{r}{i}\binom{s}{i}\binom{t−i}{f−i} \{∑_{j} \binom{r}{j}\binom{s}{j}\binom{t−j}{f−j} + ∑_{j} \binom{r}{j}\binom{s}{j}\binom{t−j}{f+1−j}\}
where t = r + s − 1
= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{r}{i}\binom{s}{i} ∑_{f} \binom{t−i}{f−i} \{\binom{t−j}{f−j} + \binom{t−j}{f+1−j}\}

as i, j and f are independent

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{r}{i}\binom{s}{i} ∑_{f} \binom{t−i}{f−i}\binom{t−j+1}{f+1−j}

by Identity 5.8 in [11]

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{r}{i}\binom{s}{i}\binom{2t−i−j+1}{t−i}

by Identity 5.23 in [11]

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{s}{i} ∑_{k} \binom{j−s}{k}\binom{t−(j−s)}{t−i−k}\binom{t+r−i−k}{t}

by Identity 5.28 in [11]

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{k} \binom{j−s}{k} ∑_{i′} \binom{s}{i′−k}\binom{t+s−j}{t−i′}\binom{t+r−i′}{t}

as i and k are independent; let i′ = i − k

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{t+s−j}{t−i}\binom{t+r−i}{t} ∑_{k} \binom{j−s}{k}\binom{s}{i−k}

let i = i′

= ∑_{j} \binom{r}{j}\binom{s}{j} ∑_{i} \binom{t+s−j}{t−i}\binom{t+r−i}{t}\binom{j}{i}

by Identity 5.22 in [11]

= ∑_{i} \binom{t+r−i}{t} ∑_{j} \binom{s}{j}\binom{j}{i}\binom{r}{j}\binom{t+s−j}{t−i}

by rearrangement and as i and j are independent

= ∑_{i} \binom{t+r−i}{t} ∑_{j} \binom{s}{i}\binom{s−i}{s−j}\binom{r}{j}\binom{t+s−j}{t−i}

by Identity 5.21 in [11]

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} ∑_{j} \binom{r}{j}\binom{s−i}{s−j}\binom{t+s−j}{t−i}

by rearrangement and Identity 5.4 in [11]

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} ∑_{j} \{\binom{r−1}{j} + \binom{r−1}{j−1}\} \binom{t−i−r+1}{t−i−(r−1−i)−j}\binom{t−i+s+i−j}{t−i}

by Identity 5.8 [11] & as t = r + s − 1

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} ∑_{j} \{\binom{r−1}{j}\binom{t−i−(r−1)}{t−i−(r−1−i)−j}\binom{t−i+(s+i)−j}{t−i}

+\binom{r−1}{j−1}\binom{t−i−(r−1)}{t−i−(r−i)−(j−1)}\binom{t−i+(s+i−1)−(j−1)}{t−i}\}

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} \{\binom{r−1−i+s+i}{r−1−i}\binom{t−i−(r−1)+s+i}{t−i−(r−1−i)} + \binom{r−i+s+i−1}{r−i}\binom{t−i−(r−1)+s+i−1}{t−i−(r−i)}\}

by Identity 5.28 in [11]

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} \{\binom{t}{r−i−1}\binom{r+s−1−r+1+s}{r+s−1−r+1} + \binom{t}{r−i}\binom{r+s−1−r+s}{r+s−1−r}\}

as t = r + s − 1

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i} \{\binom{t}{r−i−1}\binom{2s}{s} + \binom{t}{r−i}\binom{2s−1}{s−1}\}

= ∑_{i} \binom{t+r−i}{t}\binom{s}{i}\binom{2s}{s} \{\binom{t}{r−i−1} + \frac{1}{2} \binom{t}{r−i}\}

as \binom{2s−1}{s−1} = \frac{1}{2} \binom{2s}{s}

= ∑_{i} \frac{(t+r−i)!}{t!(r−i)!} × \binom{s}{i}\binom{2s}{s} × \frac{t!(t+1)}{(r−i)!(t−r+i+1)!} × \frac{t+r−i+1}{2(t+1)}

by expansion of coefficients

= \frac{1}{2} \binom{2s}{s} ∑_{i} \binom{s}{i}\binom{t+1}{r−i}\binom{t+r−i+1)}{t+1}

by contraction into binomial coefficients

= \frac{1}{2} \binom{2s}{s} ∑_{i} \binom{s}{i}\binom{r+s}{r−i}\binom{2r+s−i}{r+s}
as t = r + s − 1.

37

4.4 When m = n

The value of n is now generalised to be the product of any number of primes each raised to any power, ie n = ∏_{p∈P_{n}} p^{s_{p}} where p is an index over all different primes P_{n} of n and the s_{p} ∈ ℕ, with s_{2} > 1 to ensure that the squares are doubly even.

Any factor of n has the same primes as n, each raised to a power in the range 0 to s_{p}, ie there are s_{p} + 1 possible values for the power of any prime p. To calculate N(n, n) we wish to know W_{f}(n), the number of ways of selecting a sequence of f proper factors of n, 1 and n excluded. Although this is not directly available, we do know W_{f}^{+}(n), the number of ways of selecting a sequence of f non-decreasing factors of n, ie

Definition 4.2 A non-decreasing sequence of factors of n is a sequence of factors of n, which may include 1 or n, where each factor in the sequence is a factor, but not necessarily a proper factor of the following factor, ie it may be the same as the following factor in the sequence.

The number of ways of selecting sequences of f non-decreasing factors of n is:

W_{f}^{+}(n) = ∑_{n′∈Z^{+}} W_{f−1}^{+}(n′)

where Z_{n}^{+} is the set of all factors of n, 1 and n included, ie

Z_{n}^{+} = {k ∈ ℕ|k divides n}
and W_{0}^{+}(n) = 1 for n ∈ ℕ.

Let G_{n} be the set of functions g with domain P_{n}, such that 0 ≤ g(p) ≤ s_{p} for all p in P_{n}.

Lemma 4.3 For all f, n ∈ ℕ

∏_{p∈P_{n}} \binom{s_{p} + f + 1}{f + 1} = ∑_{g∈G_{n}} ∏_{p∈P_{n}} \binom{g(p) + f}{f}.

Proof.

\binom{s+f+1}{f+1} = ∑_{s′∈ℕ|s′≤s} \binom{s′+f}{f}  by Identity 5.9 in [11].
So ∏_{p∈P_{n}} \binom{s_{p}+f+1}{f+1} = ∏_{p∈P_{n}} ∑_{s′∈ℕ|s′≤s_{p}} \binom{s′+f}{f}
= ∑_{g∈G_{n}} ∏_{p∈P_{n}} \binom{g(p)+f}{f}.  □

Lemma 4.4 The number of ways of selecting sequences of f non-decreasing factors of n = ∏_{p∈P_{n}} p^{s_{p}}, p any prime, is W_{f}^{+}(n) = ∏_{p∈P_{n}} \binom{s_{p}+f}{f}.

Proof. (For all f and for all n is proved by induction on f.) For f = 0, ∏_{p∈P_{n}} \binom{s_{p}+0}{0} = 1 = W_{0}^{+}(n) for all n ∈ ℕ. Assume as the induction hypothesis that for all n′ = ∏_{p∈P_{n′}} p^{s′_{p}}:

W_{f}^{+}(n′) = ∏_{p∈P_{n′}} \binom{s′_{p}+f}{f}.
Let  K(g) = ∏_{p∈P_{n}} p^{g(p)}.
Then s′_{p} = g(p) for all p ∈ P_{n}.

So K gives a one-to-one correspondence between G_{n} and Z_{n}^{+}.

Then W_{f+1}^{+}(n) = ∑_{n′∈Z_{n}^{+}} W_{f}^{+}(n′)
= ∑_{g∈G_{n}} W_{f}^{+}(K(g)),  as Z_{n}^{+} = {K(g)|g ∈ G_{n}},
= ∑_{g∈G_{n}} ∏_{p∈P_{K(g)}} \binom{g(p)+f}{f} by the induction hypothesis,
= ∑_{g∈G_{n}} ∏_{p∈P_{n}} \binom{g(p)+f}{f}  as g(p) = 0 for all p ∉ P_{n},
= ∏_{p∈P_{n}} \binom{s_{p}+f+1}{f+1}  by Lemma 4.3,

which proves the induction hypothesis. □

Lemma 4.5 For all f, n ∈ ℕ

W_{f}^{+}(n) = ∑_{i} \binom{f + 1}{i + 1}W_{i}(n).

Proof. (By induction on f.) For f = 0

∑_{i} \binom{0+1}{i+1}W_{i}(n) = \binom{1}{1}W_{0}(n) = 1 = W_{0}^{+}(n), as required. Assume as the induction hypothesis:

W_{f}^{+}(n) = ∑_{i} \binom{f+1}{i+1}W_{i}(n).
Then W_{f+1}^{+}(n) = ∑_{n′∈Z_{n}^{+}} W_{f}^{+}(n)  by definition
= W_{f}^{+}(1) + ∑_{n′∈(Z_{n}∪{n})} W_{f}^{+}(n)
= 1 + ∑_{n′∈(Z_{n}∪\{n\})} ∑_{i} \binom{f+1}{i+1}W_{i}(n′)

by the induction hypothesis,

= 1 + ∑_{i} \binom{f+1}{i+1} ∑_{n′∈(Z_{n}∪\{n\})} W_{i}(n′)
= 1 + ∑_{i} \binom{f+1}{i+1}\{∑_{n′∈Z_{n}} W_{i}(n′) + W_{i}(n)\}
= 1 + ∑_{i} \binom{f+1}{i+1}\{W_{i+1}(n) + W_{i}(n)\}
= 1 + ∑_{i} \binom{f+1}{i}W_{i}(n) − \binom{f+1}{0}W_{0}(n) + ∑_{i} \binom{f+1}{i+1}W_{i}(n)
= 1 + ∑_{i}\{\binom{f+1}{i} + \binom{f+1}{i+1}\}W_{i}(n) − 1
= ∑_{i} \binom{f+2}{i+1}W_{i}(n)  by Identity 5.8 in [11],

which proves the induction hypothesis. □

Theorem 4.2 The total number of ways, W_{f}(n), of selecting sequences of f proper factors of n = ∏_{p∈P_{n}} p^{s_{p}}, p any prime, is given by:

W_{f}(n) = ∑_{i}(−1)^{f+i}\binom{f + 1}{i + 1} ∏_{p} \binom{s_{p} + i}{i},

where the summation is over all integer values of i.

Proof. From Lemma 4.5:

W_{f}^{+}(n) = ∑_{i}(−1)^{i}\binom{f+1}{i+1}(−1)^{−i}W_{i}(n)
(−1)^{f}W_{f}(n) = ∑_{i}(−1)^{i}\binom{f+1}{i+1}W_{i}^{+}(n)  by Identity 5.48 in [11]
W_{f}(n) = ∑_{i}(−1)^{i+f} \binom{f+1}{i+1} ∏_{p∈P_{n}} \binom{s_{p}+f}{f} by Lemma 4.4.  □

The Zeilberger algorithm cannot find a general (ie for any number of primes) closed form solution to the series given in Theorem 4.2. However, only the terms with 0 ≤ i ≤ f are non-zero, so the summation can always be computed. The numeric values for W_{f}(n) and W_{f+1}(n) obtained from Theorem 4.2 must then be substituted using Equation 4.1, to give N(n, n), the total number of standardised reversible squares.

The formula for W_{f}(n) when n = ∏_{p} p^{s_{p}} can be specialised by setting n = 2^{r}p^{s}. W_{f}(n) is then ∑_{i}(−1)^{f+i}\binom{f+1}{i+1}\binom{r+i}{i}\binom{s+i}{i}. By Euler’s method this can be shown to be the same as ∑_{i} \binom{r}{i}\binom{s}{i}\binom{r+s−1−i}{f−i} given by Lemma 4.2.

4.5 The total number of reversible squares

Reversible squares can be grouped into sets in such a way that all the squares within one set can be standardised to the same standardised reversible square (Theorem 3.1). Theorem 4.3 The number of different reversible squares in each set of squares which includes just one standardised reversible square is a constant, M_{n}, for any given n, equal to 2^{n+1}(n/2)!^{2}. Proof. The value of M_{n} can be determined by considering the number of different reversible squares that can be reached from a standardised reversible square by legitimate interchanges.

The columns in the left half of a standardised reversible square can be permuted into any order, provided the columns in the right half are permuted in the same way. There are (n/2)! possible such permutations. For each such permutation it is possible to interchange any column in the left half with its symmetric column in the right half. This can be done to any of the 2^{n/2} columns in the left half. Therefore, there are 2^{n/2}(n/2)! reversible squares that can be reached from a standardised reversible square by legitimate column interchanges.

Likewise there are 2^{n/2}(n/2)! reversible squares that can be reached by legitimate row interchanges. Combining both row and column interchanges results in 2^{n}(n/2)!^{2} different reversible squares. No other row or column interchanges are possible (Theorem 3.2).

Each of these squares can be reflected in the main diagonal so there are in total 2^{n+1}(n/2)!^{2} different reversible squares for every standardised reversible square. □

The total number of reversible squares is the product of the number of standardised reversible squares, N(m, n), and the number of reversible squares associated with each standardised reversible square, M_{n}. This is the same as the total number of most-perfect squares (Theorem 2.2). It has been shown that M_{n} = 2^{n+1}(n/2)!^{2} (Theorem 4.3) and that N(n, n) = ∑_{f} W_{f}(n)(W_{f}(n) + W_{f+1}(n)) (Theorem 4.1), where W_{f}(n) is the number of ways of choosing sequences of f proper factors of n with 1 and n excluded. In summary, the formulae of W_{f}(n) and N_{n} for various values of n are:

\begin{matrix}n : & W_{f}(n) : & N(n, n) : \\ 2^{r}; r > 1 & \binom{r−1}{f} & \binom{2r−1}{r} \\ 2^{r}p^{s}; r > 1 & ∑i \binom{r}{i}\binom{s}{i}\binom{r+s−1−i}{f−i} & \frac{1}{2} \binom{2s}{s} ∑i \binom{s}{i}\binom{r+s}{r−i}\binom{2r+s−i}{r+s} \\ ∏_{p∈P_{n}} p^{s_{p}}; s_{2} > 1 & ∑_{i}(−1)^{f+i}\binom{f+1}{i+1} ∏_{p} \binom{s_{p}+i}{i} & ∑_{f} W_{f}(n)(W_{f}(n) + W_{f+1}) \end{matrix}

where P_{n} is the set of primes dividing n.

5 Conclusion

The construction and enumeration of all most-perfect squares is the first time that it has been possible to do this for all members of a class of magic square of any size.

The construction is based on the same primitive squares that Rosser and Walker [20] used for constructing pandiagonal magic squares. It has recently been shown [21] that this construction, suitably extended, constructs the same pandiagonal squares that can be made using an extension of the traditional (Euler’s) method of adding two auxiliary squares. The challenges remain of enumerating all such pandiagonal squares and of constructing the remaining pandiagonal magic squares.

References

[1] J. Bellew, Counting the number of compound and Nasik magic squares, Math. Today 33 (1997) 111-118.

[2] D.S. Brée and K. Ollerenshaw, Pandiagonal magic squares from mixed auxiliary squares, Math. Today 34 (1998) 105-111.

[3] A.E. Brouwer, Recursive constructions of mutually orthogonal Latin squares, in: J. Dénes and A.D. Keedwell, eds, Latin squares: new developments in the theory and applications, (North-Holland, Amsterdam, 1991) 149-168.

[4] J.W. Brown, F. Cherry, L. Most, M. Most, E.T. Parker, and W.D. Wallis, Completion of the spectrum of orthogonal diagonal Latin squares, in: R.S. Rees, ed., Graphs, matrices, and applied mathematics, Lecture Notes in Pure and Applied Math. 139 (Springer, Berlin, 1993) 43-49.

[5] J. Dénes and A.D. Keedwell, Latin squares and their applications (Academic Press, London, 1974).

[6] L. Euler, Recherches sur une nouvelle espèce de quarrés magiques. Memoir presented to the Academy of Sciences of St Petersburg on 8 March 1779. Republished in Leonhardi Euleri Opera Omnia (1) 7 (1923) 291-392.

[7] B. Frénicle de Bessey, Des quarrez ou tables magiques, in P. de la Hire, Sedileau and Pothenot, eds, Divers ouvrages de mathématique et de physique par messieurs de l’Académie Royale des Sciences (l’Imprimerie Royale, Paris, 1693) 423-507.

[8] A.H. Frost, Invention of magic cubes, and construction of magic squares possessing additional properties, Quarterly J. Math. 7 (1866) 92-101.

[9] A.H. Frost, On the general properties of Nasik squares, Quarterly J. Math. 15 (1878) 34-49.

[10] M. Gardner, Mathematical games: a breakthrough in magic squares and the first perfect magic cube, Scientific American 234 (1976) 118-123.

[11] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete mathematics, 2nd edn (Addison-Wesley, Menlo Park, California, 1989).

[12] M. Kraitchik, La mathématique des jeux ou récréations mathématiques (Stevens Frères, Brussels, 1930).

[13] E. McClintock, On the most perfect forms of magic squares, with methods for their production, Am. J. Math. 19 (1897) 99-120.

[14] K. Ollerenshaw, On ‘most perfect’ or ‘complete’ 8 × 8 pandiagonal magic squares, Proc. Royal Soc. A 407 (1986) 259-281.

[15] K. Ollerenshaw, Living mathematics: introduction to the 25th anniversary issue, Bulletin of the Institute of Mathematics and its Applications 25 (1989) 50-56.

[16] K. Ollerenshaw and H. Bondi, Magic squares of order four, Philosophical Trans. Royal Soc. A 306 (1982) 443-532.

[17] K. Ollerenshaw and D.S. Brée, Most-perfect pandiagonal magic squares: their construction and enumeration (Institute for Mathematics and its Applications, Southend-on-Sea, 1998).

[18] M. Petkovšek, H.S. Wilf and D. Zeilberger, A = B (Peters, Wellesley Massachusetts, 1996).

[19] B. Rosser and R.J. Walker, On the transformation group for diabolic magic squares of order four, Bull. Am. Math. Soc. 44 (1938) 416-420.

[20] B. Rosser and R.J. Walker, The algebraic theory of diabolic magic squares, Duke Math. J. 5 (1939) 705-728.

[21] A.Todd and D.S. Brée, A new method for constructing pandiagonal magic squares. In draft.

[22] C.-X. Xu and Z.-W. Lu, Pandiagonal magic squares, in: D.-Z. Du and M. Li, eds, Computing and combinatorics, Proc. COCOON ’95, Lecture Notes in Computer Science 959 (Springer, Berlin, 1995) 388-391.