\documentclass[fleqn]{article}	%fleqn ensures equations/arrays are NOT centred
\usepackage{a4}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}

\renewcommand{\baselinestretch}{2}

\title{Most-perfect squares
\thanks{Sumbitted to Discrete Mathematics. Our thanks to Peter Aczel for the proofs in Section 4.4}}
\author{David S. Br\'{e}e  and Kathleen Ollerenshaw\thanks{Both authors are at the Computer Science Department, University of Manchester, Oxford Road, Manchester, UK M13 9PL. Email: bree@cs.man.ac.uk}}
%\date{}

%Ian`s counting environment
\newcounter{sentence}
\newcounter{scount}
\newenvironment{x}{
\begin{list}%
{(\arabic{scount})}
{\usecounter{scount}
\setlength{\topsep}{-2mm}
\setlength{\itemsep}{0mm}
\setlength{\rightmargin}{\leftmargin}}
\setcounter{scount}{\value{sentence}}}
{\setcounter{sentence}{\value{scount}}
\end{list}}
%end of Ian`s counting environment

\newcommand{\Sum}{\displaystyle \sum}
\newcommand{\Prod}{\displaystyle \prod}

\newenvironment{Eqnarray}
{\begin{array}{lrclr}}
{\end{array}}

\newcommand{\Mbox}{\hspace*{-\arraycolsep} \mbox}	
%This gets mboxes back to the left margin in arrays in math mode
%provided that the math mode begins within a paragraph
%what follows is what should be used for displaymath mode
%\newcommand{\Mbox}{\hspace*{-\leftmargin}\hspace*{-\arraycolsep} \mbox}	


\newcommand{\nat}{\mathbb{N}}
\newcommand{\natp}{\mathbb{N}^{>0}}


\newtheorem{Construction}{Construction}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{eq}{Equation}[section]
\newtheorem{Lemma}{Lemma}[section]
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Transform}{Transform}[section]

\setlength{\mathindent}{0 cm}

\begin{document}
\maketitle                      
Keywords: magic squares, pandiagonal squares, combinatorics.  


\begin{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
`most-perfect.' 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 most-perfect squares integers come in
complementary pairs along the diagonals and any $2\times2$ 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.  
\end{abstract}

At least since Euler, and most probably much earlier, there has been an interest in generating `magic
squares' of different sizes~\cite{mp:Kra30}. Let $A$ be an $m \times n$
matrix with entries in $\nat$:
	\[A: \Delta_m \times \Delta_n  \rightarrow \nat 
{\rm\ where\ } \Delta_n = \{k\in\nat | k<n\}. \]
$A(i,j)$, for $(i,j) \in \Delta_m\times\Delta_n$, is the natural number
occurring in row $i$ and column $j$ of $A$, where rows and columns are
numbered from zero.


\begin{defn}
$A$ is {\bf normal} if every natural number less than $nm$ occurs in
the matrix, necessarily exactly once; ie
$A:\Delta_n\times\Delta_m\rightarrow\Delta_{nm}$ is a bijection.
\end{defn}

\begin{defn}
$A$ is a {\bf 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.
\[ \forall (i\in\Delta_n) 
	\Sum_{j\in\Delta_n} A(i,j) = 
	\Sum_{j\in\Delta_n} A(j,i) = 
	\Sum_{j\in\Delta_n} A(j,j) =\Sum_{j\in\Delta_n} A(j,n-1-j). \]
\end{defn}


Methods for generating at least one normal magic square for any size
$n\ge3$ 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\'{e}nicle de Bessey~\cite{mp:Bes93} and
then analytically by Ollerenshaw and Bondi~\cite{mp:OB82}, and for $n =
5$ by exhaustion by Schroeppel~\cite{mp:Gar76}.
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.

\begin{defn} 
A {\bf path} $[i, j]$ is a sequence of positions in an $n\times 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.
\end{defn} 

\begin{defn} 
A {\bf  diagonal} is any $[1, 1]$ or $[1, -1]$ path. 
\end{defn}

\begin{defn} 
A {\bf pandiagonal magic square} is a magic square in which the integers in
every diagonal have the same sum, ie
\[\forall(i\in\Delta_n) 
	\Sum_{j\in\Delta_n} A(i,j) = \Sum_{j\in\Delta_n} A(j,i)
	=\Sum_{j\in\Delta_n} A(j,i+j) = \Sum_{j\in\Delta_n} A(j,i-j). \]
\end{defn}


Pandiagonal magic squares were recognised by Euler~\cite{mp:Eul79} but
interest lay dormant until they were rediscovered in the 1860s by
Frost~\cite{mp:Fro66}, 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~\cite{mp:DK74}~\cite{mp:Bro91}~\cite{mp:BCMMPW}~\cite{mp:XL95}).
However, a large proportion of pandiagonal squares for all values of
$n$ ($n$ not singly even, for which there are no pandiagonal magic squares~\cite{mp:Fro78}) cannot be made using Latin squares. Some -
but not all~\cite{mp:BO98} - of these other pandiagonal squares can be
made by adding a pair of auxiliary squares constructed using two
non-intersecting paths (Frost~\cite{mp:Fro78}, Bellew~\cite{mp:B97}),
eg the chess knight's paths $[1,2]$ and $[2,1]$. Rosser and
Walker~\cite{mp:RW39} have a third method that enables all pandiagonal
squares to be constructed for $n\le 5$, but only some of them for
larger values of $n$. Recently it has been shown~\cite{mp:TB99} 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~\cite{mp:McC97}. 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:

\begin{defn} 
Each integer in a matrix has four {\bf adjacent integers}: to its left
and right in the same row and above and below it in the same column.
\end{defn} 

\begin{defn} 
A {\bf $2\times 2$ block} consists of four adjacent integers, ie the set
\[ \forall (i\in\Delta_m,j\in\Delta_n) \{A(i,j), A(i,j+1), A(i+1,j), A(i+1,j+1)\}\]
\end{defn}
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\times 2$ block of adjacent integers.
 
\begin{defn}
A pair of integers in an $m\times n$ matrix $A$ are {\bf $S$-complements} if their sum is $S = nm-1$.
\end{defn}

\begin{defn} \label{defn:mp} 
When $n$ is doubly even, ie an integral multiple of 4,  {\bf
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\times 2$ block of adjacent
integers within the square is equal to $2S$, ie.
$
\indent  \forall(i\in\Delta_n,j\in\Delta_n) \ \ \ 
	A(i,j) + A(i+n/2,j+n/2) = n^2-1; \\
\indent \forall(i\in\Delta_n,j\in\Delta_n) \ \ \ 
	A(i,j) + A(i,j+1) + A(i+1,j) + A(i+1,j+1) = 2(n^2-1). 
$
\end{defn}

\noindent 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 {\bf essentially different} if one is not the
reflection of the other in either of the central axes or in the {\bf
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\times 8$ pandiagonal magic squares with $n = 4$, all of which
are most-perfect~\cite{mp:RW38}. The number of  most-perfect squares
when $n = 8$ is known to be $368,640\times 8$~\cite{mp:Oll86}.

In this paper, Rosser and Walker's ~\cite{mp:RW39} 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.







\section{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~\ref{defn:mp}, are indeed pandiagonal magic squares.

\subsection{Most-perfect squares are pandiagonal magic squares}
McClintock~\cite{mp:McC97}  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.

\begin{Lemma} 
\label{lem:mp_row_sum} 
The integers in any row of a most-perfect square have the same sum,
$nS/2$.
\end{Lemma}
\noindent\textit{Proof.}
Two adjacent rows of a most-perfect square are made up of $n/2$
$2\times 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~\ref{defn:mp} 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.
\hfill $\Box$\\


\begin{Lemma} \label{lem:mp_col_sum} 
The integers in any column of a most-perfect square have the same sum,
$nS/2$.
\end{Lemma}
\noindent\textit{Proof.}
This is similar to the proof of Lemma~\ref{lem:mp_row_sum} 
\hfill $\Box$\\

\begin{Lemma} 
\label{lem:mp_diag_sum} 
The integers in any diagonal, including broken diagonals, of a
most-perfect square have the same sum, $nS/2$.
\end{Lemma}
\noindent\textit{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$.
\hfill $\Box$\\


\begin{Theorem} 
A most-perfect square is a pandiagonal square.
\end{Theorem}
\noindent\textit{Proof.}
This follows from Lemmas~\ref{lem:mp_row_sum}, \ref{lem:mp_col_sum} and
\ref{lem:mp_diag_sum}, by Definition~\ref{defn:mp}.  
\hfill $\Box$\\
                               

                                
\subsection{Reversible and primitive squares}

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


\begin{defn} 
\label{defn:primitive}
$A$ is  {\bf primitive} if the integers at the opposite corners of any
rectangle within the matrix have equal sums~\cite{mp:RW39}, a property
here called {\bf equal cross sums}, ie\\
$\indent \forall(i,i',j,j' \in\Delta_n)\ \ \ 
	 A(i,j) + A(i',j') = A(i,j') + A(i',j). $
\end{defn}
\begin{defn} 
$A$ is {\bf row reversible} if the sums of pairs of
integers at positions that are reflections in the midpoints of any row
are constant, ie\\
$\indent \forall(j\in\Delta_n)\ \ \  A(i,j) + A(i,n-1-j) $
	 {\rm is constant, for any}  $ i\in\Delta_n. $
\end{defn}
\begin{defn} 
$A$ is {\bf column reversible} if the sums of pairs of
integers at positions that are reflections in the midpoints of any column
are constant, ie\\
$\indent \forall(i\in\Delta_n)\ \ \  A(i,j) + A(n-i-i,j) $
	 {\rm is constant, for any} $ j\in\Delta_n. $
\end{defn}
\begin{defn}\label{defn:rev}
$A$ is {\bf reversible} if it is primitive  and also row and
column reversible.
\end{defn} 

                                                             





\subsection{Transforming reversible squares into most-perfect squares}
It will now be shown that every doubly-even reversible $n\times n$
square will be transformed into a different most-perfect square by
Transform~\ref{trans:rev_to_mp}.

\begin{Transform} 
\label{trans:rev_to_mp}
{\rm~
\begin{enumerate}
\item 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$.
\item 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$.
\item Move every integer from its position $(i,\ j)$ to the position\
$(i+jn/2,\ j +(i+ j)n/2)$ for all $i\times j$, where all position
coordinates are taken modulo $n$.
\end{enumerate}
}
\end{Transform}

\begin{Lemma} 
\label{lem:different}
Every reversible square is transformed into a different square by
Transform~\ref{trans:rev_to_mp}.
\end{Lemma}
\noindent\textit{Proof.}
At every step of Transform~\ref{trans:rev_to_mp}, 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~\ref{trans:rev_to_mp}  generating a different square.
\hfill $\Box$\\

It will now be shown that the square that results from the application
of Transform~\ref{trans:rev_to_mp} to a reversible square has the
defining properties of a most-perfect square
(Definition~\ref{defn:mp}). First some properties of the square
resulting from Steps 1 and 2 will be established.

\begin{defn}
An {\bf intermediary square} is the one formed by applying just  Steps
1 and 2 of the Transform~\ref{trans:rev_to_mp} to a reversible square.
\end{defn} 

\begin{Lemma} 
\label{lem:X_primitive}
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.  
\end{Lemma}
\noindent\textit{Proof.}
Every rectangle in the matrix with a pair of interchanged rows or
columns was also a rectangle in the original matrix~\cite{mp:RW39}.
\hfill $\Box$\\
  
\begin{Lemma} 
\label{lem:inter_is_prim}
An intermediary square is a primitive square. 
\end{Lemma}
\noindent\textit{Proof.}
A reversible square is a primitive matrix (Definition~\ref{defn:rev})
and Steps 1 and 2 of Transform~\ref{trans:rev_to_mp} are simply row or
column interchanges which preserve the property of being a primitive
square (Lemma~\ref{lem:X_primitive}).
\hfill $\Box$\\

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 $S$-complements.


\begin{Lemma}  
\label{lem:refl_in_rev_are_S} 
Any pair of integers that are reflections in the midpoint of a
reversible matrix are $S$-complements.
\end{Lemma}
\noindent\textit{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'\neq 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{center}
\begin{tabular}{lclcl|lclcl}
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\ldots  &$x$    &\ldots  &$u$    &\ldots     &\ldots  &$v$    &\ldots &$y$     &\ldots\\
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &$z$    &\ldots &\vdots  &\ldots\\
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\hline
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\ldots  &\vdots &\ldots  &$z'$   &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\ldots  &$y'$   &\ldots  &$v'$   &\ldots     &\ldots  &$u'$   &\ldots &$x'$    &\ldots\\
\ldots  &\vdots &\ldots  &\vdots &\ldots     &\ldots  &\vdots &\ldots &\vdots  &\ldots\\
\end{tabular}
\end{center}

\begin{tabular}{llcll}
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.
\end{tabular}

\noindent 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' \neq 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$.
\hfill $\Box$\\

\begin{Lemma} 
\label{lem:intermed_nover2_are_S}
Integers that are distant $n/2$ along a diagonal in the intermediary
square will be $S$-complements.
\end{Lemma}
\noindent\textit{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 \le 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~\ref{lem:refl_in_rev_are_S} these integers  are
$S$-complements.
\hfill $\Box$\\

\begin{Lemma} \label{lem:nover2_are_S}
Integers distant $n/2$ along a diagonal in a square obtained by
applying Transform~\ref{trans:rev_to_mp} to a reversible square are
$S$-complements.
\end{Lemma} 
\noindent\textit{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~\ref{lem:intermed_nover2_are_S}). Hence, integers distant $n/2$
along a diagonal in the final square are $S$-complements as well.
\hfill $\Box$\\
                                                               
Lemma~\ref{lem:nover2_are_S} establishes one of the defining properties of a most-perfect square. We now
turn to the other.

\begin{defn} 
A {\bf horizontal couplet} is a pair of adjacent integers in the same row, ie
the pair
$\forall(i\in \Delta m, j\in\Delta n) \{A(i,j), A(i,j+1)\}$. 
\end{defn}



\begin{Lemma} \label{lem:int_2by2}
The four integers in a $2\times 2$ block in a square obtained by
applying Transform~\ref{trans:rev_to_mp} to a reversible square sum to
$2S$.
\end{Lemma}
\noindent\textit{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~\ref{lem:inter_is_prim}). Take one pair of opposite corners of
this rectangle, say at $(i,\ j+1)$ and $(i+1+n/2,\ j)$. By
Lemma~\ref{lem:nover2_are_S}, 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~\ref{trans:rev_to_mp} 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):

\begin{eqnarray*}	
(i,\ j)        &\mbox{to}&(i+jn/2,\  j+(i+j)n/2),\\
               &	&\\
(i+n/2,\ j+1+n/2)&\mbox{to}& (i+(1+j+1+n/2)n/2,   \\
               &	&\hspace{1 cm}  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)  &\mbox{to}  &(i+1+(j+n/2)n/2,  \\
               &	&\hspace{1 cm} j+(1+i+1+j+n/2)n/2)\\
               &=	&(i+1+jn/2,\  j+(i+j)n/2),\\
               &	&\\
(i+1+n/2,\ j+1)&\mbox{to}  & (i+1+(1+j+1)n/2,   \\
               &	&\hspace{1 cm}  j+1+(i+1+n/2+j+1)n/2)\\
               &=	&(i+1+jn/2,\  j+1+(i+j)n/2).\\
\end{eqnarray*}

\noindent 
Hence, the integers in these positions in the transformed square also
sum to $2S$. But note that these four positions form a $2\times 2$
block. This is the other property of most-perfect squares.  Conversely, any
$2\times 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$.
\hfill $\Box$\\

\begin{Theorem}  \label{theorem:T3_to_rev_is_mp}
Every doubly-even reversible square is transformed by Transform~\ref{trans:rev_to_mp} into a different
most-perfect square. 
\end{Theorem}
\noindent\textit{Proof.}
By Lemmas~\ref{lem:nover2_are_S} and \ref{lem:int_2by2}, the
Definition~\ref{defn:mp} of a most-perfect square is satisfied. By
Lemma~\ref{lem:different} each of these most-perfect squares is
different.
\hfill $\Box$\\
                                                               




\section{Correspondence between most-perfect and reversible 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~\ref{trans:rev_to_mp}, 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:

\begin{Transform} 
\label{trans:mp_to_rev} 
{\rm~
\begin{enumerate}
\item 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$.

\item 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$.

\item 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$.

\end{enumerate}
}
\end{Transform}
Note that Step 1 of  Transform~\ref{trans:mp_to_rev} is identical to
Step 3 of Transform~\ref{trans:rev_to_mp}. This is correct as:

\begin{itemize}

\item by Step 3 of Transform~\ref{trans:rev_to_mp}, 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;

\item by Step 1 of Transform~\ref{trans:mp_to_rev},\  this integer,
originally at the position\  $(i+jn/2,\ j +(i+j)n/2)$ in the
most-perfect square, will be moved to: 
\begin{eqnarray*}
\lefteqn{
(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) \mbox{ modulo }n, 
\end{eqnarray*}
\noindent as $n^2/4 = 0$ modulo $n$, since $n$ is doubly even, ie
back to where it came from in the intermediary square.

\end{itemize}

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.


\begin{Lemma}  \label{lem:horiz_couplets} 
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.
\end{Lemma}
\noindent\textit{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\times 2$ block with both the top and bottom couplet. By
Definition~\ref{defn:mp}, the four integers in both these two $2\times
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.
\hfill $\Box$\\

\begin{Lemma} \label{lem:mp_nover2_in_row} 
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$.
\end{Lemma} 
\noindent\textit{Proof.}
Consider a horizontal couplet in the left half of the square. By
Lemma~\ref{lem:horiz_couplets} 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~\ref{defn:mp}, 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:

\begin{center}
\begin{tabular}{lllll|lllll}
     &\multicolumn{2}{c}{$B$} &    &    &    &\multicolumn{2}{c}{$B'$}
& & \\
          \cline{2-3}                             \cline{7-8}
\ldots    &$b$ &$x$ &$c$ &\ldots   &\ldots   &$b'$     &$x$ &$c'$     &\ldots\\
               \cline{3-4}                             \cline{8-9}
          &    &\multicolumn{2}{c}{$C$} & &       &    &\multicolumn{2}{c}{$C'$}\\
\end{tabular}
\end{center}

It has just been shown that $\sum B+\sum B'  = \sum C +\sum C'  = 2S$, where $\sum X$ is the sum of the integers in the pair $X$. Rearranging gives
$\sum B-\sum C  = \sum C'- \sum B'$. Now $\sum B-\sum 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; $\sum C'-\sum 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.
\hfill $\Box$\\

Likewise it can be shown that:
\begin{Lemma} 
\label{lem:mp_nover2_in_col} 
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$.
\end{Lemma}


We now use this property of most-perfect squares to show that they are transformed into reversible squares by Transform~\ref{trans:mp_to_rev}.
We first prove that the transformed square is row and column reversible and then that the square is primitive.

\begin{Lemma}  
\label{lem:rows_rev} 
The rows of the square obtained by applying
Transform~\ref{trans:mp_to_rev} to a most-perfect square are
reversible.
\end{Lemma}
\noindent\textit{Proof.}
Let $Q$ be the square obtained by applying Step 1 of
Transform~\ref{trans:mp_to_rev} to an $n\times n$ most-perfect square
$P$. Then, as Step 1 of Transform~\ref{trans:mp_to_rev} is the same as
Step 3 of Transform~\ref{trans:rev_to_mp}:\\
$\begin{Eqnarray}
     &Q(i,j)  &=   &P(i+jn/2,j + (i+ j)n/2),             \\
\Mbox{ie, } 
     &Q(i,j)  &=   &\left\{\begin{array}{ll} P(i,j+in/2)      &j\mbox{ even;}\\
                         P(i+n/2,j+in/2+n/2)  &j\mbox{ odd.}
                              \end{array}\right.	\\
\multicolumn{3}{l}{\Mbox{Consequently,}}	\\
\multicolumn{3}{l}{\Mbox{}\lefteqn{Q(i,j) + Q(i,j+n/2)  }} \\
      &         &=   &\left\{\begin{array}{l}
			P(i,j+in/2) + P(i,j+in/2 + n/2)
                                          \hfill j\mbox{\ 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))\ \ \ \  
					\hfill j\mbox{\ odd.}
                              \end{array}\right.
\end{Eqnarray}$\\
From Lemma~\ref{lem:mp_nover2_in_row}, $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~\ref{trans:mp_to_rev} 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.
\hfill $\Box$\\


\begin{Lemma}  \label{lem:cols_rev}
The columns of the square obtained by applying
Transform~\ref{trans:mp_to_rev} to a most-perfect square are
reversible.
\end{Lemma}
\noindent\textit{Proof.}
The proof is similar to that of Lemma~\ref{lem:rows_rev}, but using Lemma~\ref{lem:mp_nover2_in_col} instead of Lemma~\ref{lem:mp_nover2_in_row}.
\hfill $\Box$\\


\begin{Lemma} \label{lem:2x2_step1}
Any $2 \times 2$ block in the square obtained by applying Step 1 of
Transform~\ref{trans:mp_to_rev} to a most-perfect square has equal
cross sums.

\end{Lemma}
\noindent\textit{Proof.}
Consider a $2\times 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))$

{\small
$\begin{Eqnarray}
&&= &P(i+jn/2,j+(i+j)n/2) + P(i+1+(j+1)n/2,j+1+(i+j+2)n/2)\\
&&  &\mbox{}- P(i+(j+1)n/2,j+1+(i+ j+1)n/2) \\
&&  &\mbox{}- P(i+1+jn/2,j+(i+j+1)n/2)\\
&&  &	\hfill \mbox{by Step 1 of Transform~\ref{trans:mp_to_rev};}\\
&&= &P(i+jn/2,j+(i+j)n/2) + P(i+1+jn/2+n/2,j+1+(i+j)n/2)\\
&&  &\mbox{}- S + P(i+jn/2,j+1+(i+ j)n/2) \\
&&  &\mbox{}- S + P(i+1+jn/2+n/2,j+(i+j)n/2)\\
&&  &	 \hfill \mbox{by Definition~\ref{defn:mp};}\\
&&=  &P(i+jn/2,j+(i+j)n/2) + P(i+jn/2,j+(i+ j)n/2+1)\\
&&  &\mbox{}+ P(i+jn/2+1+n/2,j+(i+ j)n/2) \\
&&  &\mbox{}+ P(i+jn/2+1+n/2,j+(i+ j)n/2+1) -  2S \\
&&  &	\hfill \mbox{by rearranging terms;}\\
&&= &P(i+jn/2,j+(i+j)n/2) + P(i+jn/2,j+(i+ j)n/2+1)\\
&&  &\mbox{}+ P(i+jn/2+1,j+(i+ j)n/2) \\
&&  &\mbox{}+ P(i+jn/2+1,j+(i+ j)n/2+1) - 2S\\
&&  &	 \hfill \mbox{by Lemma~\ref{lem:horiz_couplets};}\\
&&= &0 \hfill \mbox{by Definition~\ref{defn:mp}.}
\end{Eqnarray}$
}\\
Therefore any $2\times 2$ block in the square $Q$ has equal
cross sums.
\hfill $\Box$\\

\begin{Lemma}  \label{lem:T4_to_mp_is_prim}
The square resulting from applying Transform~\ref{trans:mp_to_rev} to a most-perfect square is
a primitive square.
\end{Lemma}
\noindent\textit{Proof.}
Consider two $2\times 2$ blocks in the square $Q$ with one column in common as shown:

\begin{eqnarray*}
               & \ldots\ a\ c\ e\ \ldots & \mbox{where } a=A(i,j-1), c=A(i,j), e=A(i,j+1) \\
               & \ldots\ b\ d\ f\ \ldots & \mbox{and } b=A(i+1,j-1), d=A(i+1,j), f=A(i+1,j+1). 
\end{eqnarray*}
Note that: $a - b$  =   $c - d = e - f $ by equal cross sums of $2\times 2$ blocks in the intermediary square (Lemma~\ref{lem:2x2_step1}),
so $a + f$      =   $b + e$,
ie the $2\times 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~\ref{lem:X_primitive}), 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~\ref{defn:primitive}.
\hfill $\Box$\\

                                                               
\begin{Theorem} 
\label{theorem:T4_to_mp_is_rev}
The square obtained by applying Transform~\ref{trans:mp_to_rev} to a
most-perfect square is a doubly-even reversible square.
 \end{Theorem}
\noindent\textit{Proof.}
By Lemma~\ref{lem:T4_to_mp_is_prim} the
resulting square is primitive and by Lemmas~\ref{lem:rows_rev} and
\ref{lem:cols_rev}, the rows and columns of the resulting square are
reversible.  Hence, by Definition~\ref{defn:rev}, the resulting square
is a reversible square. All most-perfect squares are doubly even, so
the final square is also doubly even.
\hfill $\Box$\\

\begin{Theorem} \label{theorem:one_to_one}
There is a one-to-one correspondence between most-perfect and doubly-even reversible squares. 
\end{Theorem}
\noindent\textit{Proof.}
It has been shown both that Transform~\ref{trans:rev_to_mp} applied to
a doubly-even reversible square always gives a different most-perfect
square (Theorem~\ref{theorem:T3_to_rev_is_mp}) and that the
Transform~\ref{trans:mp_to_rev} applied to a most-perfect square always
gives a different doubly-even reversible square
(Theorem~\ref{theorem:T4_to_mp_is_rev}).
\hfill $\Box$\\







\section{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.

\subsection{Standardising reversible matrices}
\begin{defn} 
Row and column interchanges applied to a reversible matrix are {\bf
legitimate} if the result is still a reversible matrix.
\end{defn} 
For each group of reversible matrices there is just one matrix that is
considered the standardised form. 


\begin{defn}
$A$ is {\bf monotone} if 
\[ \forall (i,i' \in\Delta_m, j,j' \in\Delta_n) \ \ \ 
	i \le i' \& j \le j' \implies A(i,j) \le A(i',j'). \]
\end{defn}

\begin{defn}
\label{defn:standardized}
$A$ is  {\bf (row) standardised} if it is  monotone and $A(0,1) = 1$.
\end{defn}
\begin{defn}
$A$ is a {\bf column standardised} if $A^t$ is row standardised.
\end{defn}



\begin{Lemma} 
Interchanging any pair of rows or columns of a reversible matrix
results in a primitive matrix.
\end{Lemma} 
\noindent\textit{Proof.}
A reversible matrix is a primitive matrix (Definition~\ref{defn:rev})
and any row or column interchanges applied to a primitive matrix result
in a primitive matrix (Lemma~\ref{lem:X_primitive}).
~~\hfill $\Box$\\

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

\begin{defn} 
{\bf Symmetric rows/columns} are rows/columns that are reflections in the mid horizontal/vertical axis, respectively.
\end{defn}
\begin{Lemma} 
Interchanging a pair of symmetric rows of a reversible matrix retains
the properties of row and column reversibility.
\end{Lemma}
\noindent\textit{Proof.}
Pairs of integers in any column of a reversible matrix that are in
symmetric rows have a constant sum, by Definition~\ref{defn:rev}, so
the interchange of their two rows will still result in the same sum.
Also this interchange does not affect any individual row.
\hfill $\Box$\\

Similarly, 
\begin{Lemma} 
Interchanging a pair of symmetric columns of a reversible matrix
retains the properties of row and column  reversibility.
\end{Lemma}

\begin{Lemma} 
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.
\end{Lemma}
\noindent\textit{Proof.}
If rows $i$ and $h$ are the rows interchanged in one  half of the
matrix (eg $i,h \le 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 \le
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.
\hfill $\Box$\\

Likewise,
\begin{Lemma}
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.
\end{Lemma}

\begin{Lemma}
The transpose of a reversible matrix will be row and column reversible.
\end{Lemma}
\noindent\textit{Proof.}
All the rows and columns are interchanged but their order is retained.
~~\hfill $\Box$\\


Any reversible matrix can be standardised in the following manner:

\begin{Transform} 
\label{trans:standardize} 
{\rm~
\begin{enumerate}

\item 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:

     \begin{enumerate}

     \item 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.

     \item 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.

     \item Update the current integer to the next highest integer in
     	this row.

     \end{enumerate}

\item Repeat Step 1 but with ``rows'' for ``columns''.

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

\end{enumerate}
}
\end{Transform}

\begin{Lemma} 
\label{lem:standardize}
Transform~\ref{trans:standardize} applied to a reversible matrix  will
always terminate.
\end{Lemma}
\noindent\textit{Proof.}
To prove that Transform~\ref{trans:standardize} 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. 

\begin{enumerate}

\item 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
	$ \forall (j\in\Delta_n|j<k)  \ \ \ A(i,j) < c. $
Note that the column interchanges in Steps 1a and 1b preserve row
reversibility. 
	\begin{itemize}
	\item If $k\ge 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$.

	\item If $A(i,k)=c$, no column interchanges are required.

	\item If $k < n/2$, by row reversibility,
		$ \forall (j\in\Delta_n | j<k)\ \ \  A(i,n-1-j) > c. $
	So $c$ must lie between columns $k$ and $n-1-k$:
		\begin{itemize}
		\item 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.

		\item 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.
		\end{itemize}
	In both cases, columns to the left of column $k$ will not be
	disturbed.
	\end{itemize}


\item The proof proceeds likewise with ``rows" substituted for
``columns" in Step 1.

\item 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.
\end{enumerate}
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.
\hfill $\Box$\\

\begin{Theorem} 
\label{theorem:standardize}
Transform~\ref{trans:standardize} will transform any reversible matrix into a
standardised reversible matrix.
\end{Theorem}
\noindent\textit{Proof.} 
Applying Transform~\ref{trans:standardize} to a reversible matrix
terminates (Lemma~\ref{lem:standardize}) and results in a matrix $A'$.
Step 1 of Transform~\ref{trans:standardize} 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~\ref{trans:standardize}  applies only legitimate row and column
interchanges to a reversible matrix, $A'$ is also
reversible (Lemma~\ref{lem:X_primitive}).  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~\ref{defn:standardized}, $A'$ is standardised.
\hfill $\Box$\\

In order to enumerate a set of reversible matrices, it needs to be shown that:
\begin{Theorem}
\label{theorem:legitimate}
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.
\end{Theorem}
\noindent\textit{Proof.}
If a row interchange is required other than a legitimate one,
then let the two rows being interchanged be $i$ and $h
\ (h\ne i,n-1-i)$.  If rows $i$ and $h$ are now interchanged, two
possibilities arise:
\begin{itemize}
	\item 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.

	\item 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) \ne 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.
\end{itemize}
A similar argument holds for two column interchanges.
\hfill $\Box$\\






\subsection{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~\cite{mp:RW39} show that:

\begin{Lemma} \label{lem:consecutive_integers}
The rows of any standardised primitive matrix consist of sequences of
consecutive integers.
\end{Lemma}
\noindent\textit{Proof.}
(Not that given in~\cite{mp:RW39}) Let $c_{1} (c_{1} \le n)$ be the length
of such sequences, if they exist.  Consider placing the integers one by
one consecutively in the $m \times 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} \le 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.

\hfill $\Box$\\

\begin{defn}
A {\bf 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.
\end{defn}
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.

\begin{Theorem}
\label{theorem:2_sequences}
The $m \times 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$.
\end{Theorem}
\noindent\textit{Proof.}
Given in~\cite{mp:TB99} (based on~\cite{mp:OB98}).
\hfill $\Box$\\


If $m=n=12$, the pairs of sequences could be any of the 42 combinations
indicated by a `+' in Table~\ref{tab:sequences}, 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.

\begin{table}
\caption{Permitted combinations of a pair of sequences of proper
factors, $n = 12$}
\label{tab:sequences}
\begin{tabular}{r|cccccccc}
Sequence of proper     
     &\multicolumn{8}{c}{Sequence of proper factors for columns}\\
factors for rows   &[]  &[2] &[4] &[3] &[6] &[2,4] &[2,6] [3,6]\\
\hline
~[]  &+   &+   &+   &+   &+   &    &    &\\
~[2] &    &+   &+   &+   &+   &+   &+   &+\\
~[4] &    &+   &+   &+   &+   &+   &+   &+\\
~[3] &    &+   &+   &+   &+   &+   &+   &+\\
~[6] &    &+   &+   &+   &+   &+   &+   &+\\
~[2,4] &  &    &    &    &    &+   &+   &+\\
~[2,6] &  &    &    &    &    &+   &+   &+\\
~[3,6] &  &    &    &    &    &+   &+   &+\\
\end{tabular}
\end{table}






\subsection{Construction of standardised primitive matrices}
It has just been shown in Theorem~\ref{theorem:2_sequences} that {\sc
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.

\begin{Construction} 
\label{cons:stand_rev_sq}
{\rm (Based on~\cite{mp:OB98}.)
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: \\
\indent $ r_{1} < r_{2} <\ldots < 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:\\
\indent $ c_{1} < c_{2} <\ldots < c_{f} [< c_{f+1}]\ \ \ 
          (1=c_{0} < c_{1},\ c_{f+1} \le 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$:


\begin{enumerate}

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

\item Set $A(0,0) = 0$.

\item Create the top row by, for $h = 0$ step 1 up to $f+1$:
	\begin{itemize}
	\item for $g = 1$ step 1 up to $(c_{h+1} / c_h)-1$:
		\begin{itemize}
		\item let $shift = g*c_h$ and $shiftsize = shift*r_h$;
		\item for $j$ = 0 step 1 up to $c_h-1$, 
			set $A(0, shift + j) = shiftsize + A(0, j)$.
		\end{itemize}
	\end{itemize}

\item  Create the left column by, for $h = 0$ step 1 up to $f$:
	\begin{itemize}
	\item for $g = 1$ step 1 up to $(r_{h+1}/r_h)-1$:
		\begin{itemize}
		\item let $shift = g*r_h$ and $shiftsize = shift*c_{h+1}$;
		\item for $j$ = 0 step 1 up to $r_h-1$, 
			set $A(shift+j, 0) = shiftsize + A(j, 0)$.
		\end{itemize}
	\end{itemize}

\item	Fill in the rest of the matrix by, for $i = 1$ step 1 up to $m-1$:
	\begin{itemize}
	\item for $j = 1$ step 1 up to $n-1$ 
		set $A(i, j) = A(i, 0) + A(0,j)$.
	\end{itemize}

\end{enumerate}
}
\end{Construction} 

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~\ref{tab:12}.

\begin{table}
\caption{A 12 by 12 standardised reversible square}
\label{tab:12}
\begin{tabular}{rrrrrrrrrrrr}
  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\\
\end{tabular}
\end{table}

\begin{Theorem} \label{theorem:sq_is_nps}
Construction~\ref{cons:stand_rev_sq} results in a standardised primitive
matrix.
\end{Theorem}
\noindent\textit{Proof.}
The matrix that results from Construction~\ref{cons:stand_rev_sq} 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~\ref{cons:stand_rev_sq} 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~\ref{defn:primitive}
and~\ref{defn:standardized} the matrix is a standardised primitive
matrix.
\hfill $\Box$\\






\subsection{A standardised primitive matrix is a standardised reversible matrix}
A standardised primitive matrix $A$
will now be shown to be a standardised reversible matrix. Hence, {\sc
all} standardised reversible matrices can be constructed by
Construction~\ref{cons:stand_rev_sq}.

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.

\begin{defn}
Two sequences of integers are {\bf similar} if the difference between
integers in the same relative positions in each sequence is constant.
\end{defn}


\begin{Lemma} \label{lem:rev_row_induction}
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. 
\end{Lemma}
\noindent\textit{Proof.}
From Construction~\ref{cons:stand_rev_sq}, 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:  \\
\indent $ h c_{i-1} r_{i-1} + c_{0,\ j}
\mbox{\ 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: \\
\indent $(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.

\hfill $\Box$\\


\begin{Lemma} \label{lem:rows_reversible}
The rows of the matrix resulting from
Construction~\ref{cons:stand_rev_sq} are reversible.
\end{Lemma}
\noindent\textit{Proof.}
By Construction~\ref{cons:stand_rev_sq}, 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~\ref{lem:rev_row_induction},
the sequences of integers from $(0,\ 0)$ to $(0,\ c_{i}-1)$ are
reversible for all $i \le (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~\ref{theorem:sq_is_nps}) by equal cross sums,
every row of the matrix is reversible.
\hfill $\Box$\\

\begin{Lemma} \label{lem:cols_reversible}
The columns of the matrix resulting from
Construction~\ref{cons:stand_rev_sq} are reversible.
\end{Lemma}
\noindent\textit{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~\ref{lem:rev_row_induction}. For $i = 1$ the
sequence at the top of the left-most column is, by Construction~\ref{cons:stand_rev_sq}:
$0,\ c_{1},\ 2c_{1},\ 3c_{1},\ \ldots, (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~\ref{theorem:sq_is_nps}) by equal cross sums, every column of the
matrix is reversible.
\hfill $\Box$\\

\begin{Theorem} \label{theorem:construction_rev}
Construction~\ref{cons:stand_rev_sq} always results in a  standardised reversible matrix and
every standardised reversible matrix can be constructed using
Construction~\ref{cons:stand_rev_sq}.
\end{Theorem}
\noindent\textit{Proof.}
By Theorem~\ref{theorem:sq_is_nps}, Construction~\ref{cons:stand_rev_sq}
always results in a standardised primitive matrix. By
Lemmas~\ref{lem:rows_reversible} and \ref{lem:cols_reversible} the rows
and columns of these matrices are reversible. This fulfills the
Definition~\ref{defn:standardized} of a standardised reversible matrix and
proves the first half of Theorem~\ref{theorem:construction_rev}. A standardised
reversible matrix is a standardised primitive matrix by
Definitions~\ref{defn:standardized} and~\ref{defn:standardized}. All
standardised primitive matrices can be constructed using
Construction~\ref{cons:stand_rev_sq}, from two sequences of proper
factors of $n$ (Theorem~\ref{theorem:2_sequences}). Therefore all standardised
reversible matrices can be constructed using
Construction~\ref{cons:stand_rev_sq}.
\hfill $\Box$\\






\section{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~\cite{mp:RW39} 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\times 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.

\subsection{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\\
	\indent $ W_f(n) = \sum_{n'\in Z_n} W_{f-1}(n'),$\\
where $Z_n$ is the set of proper factors of $n$, 1 and $n$ excluded, ie\\
	\indent $ Z_n = \{k >0 | k \mbox{\ divides\ } n\} - \{1, n\};\\ 
	\indent W_0(0)=0; W_0(n) = 1, n>0,\ \mbox{ie the empty sequence.} $


\begin{Theorem} \label{theorem:Nmn}
For all $m,n  \in \nat$,
the total number of standardised reversible $m\times n$ matrices is 
\begin{eq} \label{eq:Nmn}
$    N(m,n) = \Sum_{f} W_{f}(m) (W_f(n) + W_{f+1}(n)).$
\end{eq}

\end{Theorem}
\noindent\textit{Proof.}
(By induction on $m$ and $n$.) Assume that for any $m', n'$ which are
proper factors of $m, n$, respectively:\\
	\indent $     N(m',n') = \sum_{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\\
	\indent $ N(1,1) = W_0(1)(W_0(1) + W_1(1)) = 1(1+0) = 1 $\\
as required. A general $m\times n$ standardised reversible matrix has
one of the following structures:
\begin{itemize}

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

\item 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) = \lfloor j/n' \rfloor (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$.

\item 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:\\
$\begin{Eqnarray}
\multicolumn{4}{l}{\sum_{m'\in Z_m} \sum_{n'\in Z_n} \sum_f W_f(m')(W_f(n') + W_{f+1}(n'))}\\
&&=	&\sum_f \sum_{m'\in Z_m} W_f(m') 
		\sum_{n'\in Z_n}  (W_f(n') + W_{f+1}(n')\\
&&=	&\sum_f W_{f+1}(m) (W_{f+1}(n) + W_{f+2}(n))
\end{Eqnarray}$
\end{itemize}
Therefore the total number of standardised reversible squares is:\\
$\begin{Eqnarray}
&N(m,n)	
 &=	&1 + W_1(n) + \sum_f W_{f+1}(m) (W_{f+1}(n) + W_{f+2}(n))\\
&&=	&W_0(m)(W_0(n) + W_1(n)) + \sum_f W_{f+1}(m) (W_{f+1}(n) + W_{f+2}(n))\\
&&=	&\sum_f W_f(m) (W_f(n) + W_{f+1}(n))
\hfill \Box
\end{Eqnarray}$\\

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~\ref{eq:Nmn} is computable. It remains to
find a formula for the non-zero values of $W_f(n)$.



\subsection{When $m=n=2^r$}

\begin{Lemma} \label{n=2r}
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}$. 
\end{Lemma}
\noindent\textit{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.
\hfill $\Box$\\

\noindent Substituting this value for $W_f(n)$ and $W_f(m)$ in Equation~\ref{eq:Nmn} gives:\\
$\begin{Eqnarray}
&N(2^r,2^r)    
 &=   &\sum_{f} \binom{r-1}{f} 
               \left\{\binom{r-1}{f} + \binom{r-1}{f+1} \right\}\\
&&=   &\sum_{f} \binom{r-1}{f} \binom{r}{f+1}
                &\mbox{by Identity 5.8 in~\cite{mp:GKP89},}\\
&&=   &\binom{2r-1}{r}
               &\mbox{\hspace{2 cm}by Identity 5.23 in~\cite{mp:GKP89},}
\end{Eqnarray}$\\
confirming a conjecture by Ollerenshaw~\cite{mp:Oll89}.




\subsection{When $m=n=2^rp^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 \in \nat|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:

\begin{defn} \label{defn:step}
A  {\bf 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.
\end{defn}

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^0p^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^rp^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:

\begin{center}
\begin{tabular}{ll}
Full length sequences		:                 &Steps at:\\
$01,\ 02,\ \ldots,\ 0s,\ 1s,\  \ldots,\ (r-1)s$          &$-$\\
$10,\ 20,\ \ldots,\ r0,\ r1,\  \ldots,\ r(s-1)$          &$r0$\\
$01,\ 02,\ \ldots,\ 0(s-2),\ 1(s-2),\ 1(s-1),\ 1s,\ \ldots (r-1)s$      &$1(s-2)$\\
\footnotesize $01,\ \ldots 0(s-2),\ 1(s-2),\ 2(s-2),\ 2(s-1),\ 3(s-1),\ 3s,\ \ldots (r-1)s$ &\footnotesize$1(s-2),\ 2(s-1)$
\end{tabular}
\end{center}

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}$.

\begin{Lemma} \label{lem:n=2^r.p^s}
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 \in \nat|r>1$, is
$\sum_{i} \binom{r}{i} \binom{s}{i} \binom{r+s-1-i}{f-i}$, where the
summation is over all values of $i$.
\end{Lemma}
\noindent\textit{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\le 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 $\sum_{i} \binom{r}{i} \binom{s}{i} \binom{r+s-1-i}{f-i}$.

\hfill $\Box$\\

Terms in this series are zero for $i < 0$ and $i >$
minimum$[r,\ s,\ f]$. The Zeilberger~\cite{mp:PWZ96} 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~\ref{eq:Nmn}, to obtain a value for~$N(2^rp^s,2^rp^s)$. When
this is done and the result simplified using standard identities
from~\cite{mp:GKP89} (see Table~\ref{tab:n=2^r.p^s}), we get:

\begin{eq}\label{eq:n=2^r.p^s}
$ N(2^rp^s,2^rp^s) = \frac{1}{2} \binom{2s}{s} 
     \sum_{i} \binom{s}{i} \binom{r+s}{r-i}
          \binom{2r+s-i}{r+s}. $
\end{eq}

\begin{table}
\caption{Deriving $N(2^r p^s, 2^r p^s )$}
\label{tab:n=2^r.p^s}
\noindent $N(2^rp^s,2^rp^s)$    

\begin{tabular}{ll}
= &$ \sum_{f} \sum_{i} \binom{r}{i} \binom{s}{i} \binom{t-i}{f-i}
          \left\{ \sum_{j} \binom{r}{j} \binom{s}{j} \binom{t-j}{f-j}
                +\sum_{j} \binom{r}{j} \binom{s}{j} \binom{t-j}{f+1-j}
               \right\} $\\
\multicolumn{2}{r}{ where $t = r+s-1$}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j} 
          \sum_{i} \binom{r}{i} \binom{s}{i}
               \sum_{f} \binom{t-i}{f-i} 
                    \left\{ \binom{t-j}{f-j} + \binom{t-j}{f+1-j}
                         \right\}$ \\
\multicolumn{2}{r}{as $i,\ j$ and  $f$ are independent}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j} 
          \sum_{i} \binom{r}{i} \binom{s}{i}
               \sum_{f} \binom{t-i}{f-i} \binom{t-j+1}{f+1-j}$\\
		\multicolumn{2}{r}{ by Identity 5.8 in~\cite{mp:GKP89}}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j} 
          \sum_{i} \binom{r}{i} \binom{s}{i}
               \binom{2t-i-j+1}{t-i}$\\
		\multicolumn{2}{r}{by Identity 5.23 in~\cite{mp:GKP89}}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j} 
          \sum_{i} \binom{s}{i}
               \sum_{k} \binom{j-s}{k} \binom{t-(j-s)}{t-i-k} 
                    \binom{t+r-i-k}{t}$\\
		\multicolumn{2}{r}{ by Identity 5.28 in~\cite{mp:GKP89}}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j} 
          \sum_{k} \binom{j-s}{k} 
               \sum_{i'} \binom{s}{i'-k} \binom{t+s-j}{t-i'}
                    \binom{t+r-i'}{t}$\\
		\multicolumn{2}{r}{as $i$ and $k$ are independent; let $i' = i-k$}\\
= &$\sum_{j} \binom{r}{j} \binom{s}{j}
          \sum_{i} \binom{t+s-j}{t-i} \binom{t+r-i}{t}
               \sum_{k} \binom{j-s}{k} \binom{s}{i-k}$ \\
                    \multicolumn{2}{r}{let $i = i'$}\\ 
= &$\sum_{j} \binom{r}{j} \binom{s}{j}
          \sum_{i} \binom{t+s-j}{t-i}   \binom{t+r-i}{t} \binom{j}{i}$\\
               \multicolumn{2}{r}{by Identity 5.22 in~\cite{mp:GKP89}}\\
= &$\sum_{i} \binom{t+r-i}{t}
      \sum_{j} \binom{s}{j} \binom{j}{i} \binom{r}{j}
          \binom{t+s-j}{t-i}$\\
               \multicolumn{2}{r}{by rearrangement and as $i$ and $j$ are independent}\\
= &$\sum_{i} \binom{t+r-i}{t}
           \sum_{j} \binom{s}{i} \binom{s-i}{s-j} \binom{r}{j}
               \binom{t+s-j}{t-i}$\\
                    \multicolumn{2}{r}{by Identity 5.21 in~\cite{mp:GKP89}}\\
&\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
           \sum_{j} \binom{r}{j} \binom{s-i}{s-j}
               \binom{t+s-j}{t-i}$	\\
\multicolumn{2}{r}{by rearrangement and Identity 5.4 in~\cite{mp:GKP89}}\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
      \sum_{j} \left\{ \binom{r-1}{j} + \binom{r-1}{j-1} \right\} 
  	\binom{t-i-r+1}{t-i-(r-1-i)-j}
           \binom{t-i+s+i-j}{t-i}$\\
               \multicolumn{2}{r}{by Identity 5.8~\cite{mp:GKP89} \& as $t = r+s-1$}\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
      \sum_{j} \left\{ \binom{r-1}{j} \binom{t-i-(r-1)}{t-i-(r-1-i)-j} 
          \binom{t-i+(s+i)-j}{t-i} \right . $\\
	&\hfill $\left . + \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} \right\}$\\
&\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
      \left\{ \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)} \right\}$ \\
               \multicolumn{2}{r}{by Identity 5.28 in~\cite{mp:GKP89}}\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
           \left\{ \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} \right\} $\\
                    \multicolumn{2}{r}{as $t = r+s-1$}\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} 
      \left\{ \binom{t}{r-i-1} \binom{2s}{s}
          + \binom{t}{r-i} \binom{2s-1}{s-1}
               \right\} $\\
&\\
= &$\sum_{i} \binom{t+r-i}{t} \binom{s}{i} \binom{2s}{s}
      \left\{ \binom{t}{r-i-1} + \frac{1}{2} \binom{t}{r-i} \right\} $\\
          \multicolumn{2}{r}{as $\binom{2s-1}{s-1} = \frac{1}{2}\binom{2s}{s}$}\\
= &$\sum_{i} \frac {(t+r-i)!}{t!(r-i)!} 
     \times \binom{s}{i} \binom{2s}{s} 
          \times \frac{t!(t+1)}{(r-i)!(t-r+i+1)!}
               \times \frac{t+r-i+1}{2(t+1)}$     \\ 
\multicolumn{2}{r}{by expansion of coefficients}\\
= &$\frac{1}{2} \binom{2s}{s} 
     \sum_{i} \binom{s}{i} \binom{t+1}{r-i}
          \binom{t+r-i+1)}{t+1}$ \\
          \multicolumn{2}{r}{by contraction into binomial coefficients}\\
= &$\frac{1}{2} \binom{2s}{s} 
     \sum_{i} \binom{s}{i} \binom{r+s}{r-i}
          \binom{2r+s-i}{r+s}$ \\
               \multicolumn{2}{r}{as $t = r+s-1$.}\\
\end{tabular}
\end{table}


Some of these identities from~\cite{mp:GKP89} have pre-conditions for
their application that are not shown here. We have proved (in chapter 6
of~\cite{mp:OB98}) 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~\cite{mp:GKP89} is non-trivial; see Ollerenshaw
and Br\'{e}e~\cite{mp:OB98} chapter 6 for details on how it has been
applied here.

Even though Zeilberger's algorithm~\cite{mp:PWZ96} finds a recursive
relation for the remaining summation under $i$,
Petkov$\check{\mathrm{s}}$ek's algorithm~\cite{mp:PWZ96}, hyper, shows
that the recursive relation has no closed form solution.
Equation~\ref{eq:n=2^r.p^s} confirms a conjecture of Ollerenshaw
deposited with M.~Gardner in 1992.



\subsection{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= \prod_{p\in P_n} p^{s_p}$ where
$p$ is an index over all different primes $P_n$ of $n$ and the $s_p\in\nat$, 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

\begin{defn} \label{defn:non-decreasing}
A {\bf 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.
\end{defn}
The number of ways of selecting sequences of $f$ non-decreasing  factors of $n$ is: 
\[ W^+_f(n) = \Sum_{n'\in Z^+} W^+_{f-1}(n') \]
where $Z^+_n$ is the set of all factors of $n$, 1 and $n$ included, ie\\
$\begin{Eqnarray}
 &Z^+_n 	&= &\{k\in\nat| k \mbox{ divides } n\}\\
\Mbox{and } &W^+_0(n) 	&= &1 	\mbox{ for } n\in\nat.
\end{Eqnarray}$

Let $G_n$ be the set of functions $g$ with domain $P_n$, such that $0
\le g(p) \le s_p$ for all $p$ in $P_n$.

\begin{Lemma} \label{lem:bernoulli}
For all $f, n \in \nat   $
\[	\prod_{p\in P_n} \binom{s_p+f+1}{f+1} = 
	\sum_{g\in G_n} \prod_{p\in P_n} \binom{g(p)+f}{f}. \]
\end{Lemma}
\noindent\textit{Proof.}\\
$\begin{Eqnarray}
	&\binom{s+f+1}{f+1}	&=	
	&\sum_{s'\in \nat|s'\le s} \binom{s'+f}{f} 
		&\mbox{ by Identity 5.9 in~\cite{mp:GKP89}.}\\
\Mbox{So } &\prod_{p\in P_n}  \binom{s_p+f+1}{f+1}  &=
	&\prod_{p\in P_n} \sum_{s'\in \nat|s'\le s_p} \binom{s'+f}{f}\\
&&=	&\sum_{g\in G_n} \prod_{p\in P_n} \binom{g(p)+f}{f}.
		&\Box
\end{Eqnarray}$

\begin{Lemma} \label{lem:W+}
The number of ways of selecting sequences of $f$ non-decreasing factors
of $n=\prod_{p\in P_n} p^{s_{p}},\ p$ any prime, is $W^+_f (n) = \prod_{p\in P_n}
\binom{s_{p}+f}{f}$.
\end{Lemma}
\noindent\textit{Proof.}
(For all $f$ and for all $n$ is proved by induction on $f$.) \\
For $f=0$, $\prod_{p\in P_n} \binom{s_{p}+0}{0} = 1 = W^+_0(n)$ for
all $n\in\nat$. Assume as the induction hypothesis that for all 
$n' =\prod_{p\in P_{n'}} p^{s'_p}$:\\
\begin{math}
\begin{Eqnarray}
		&W^+_f(n') &= &\prod_{p\in P_{n'}} \binom{s'_p+f}{f}.\\
\Mbox{Let }	&K(g) 	&= 	&\prod_{p\in P_n} p^{g(p)}.\\
\Mbox{Then }	&s'_p	&=	&g(p) &\mbox{ for all } p\in P_n.
\end{Eqnarray}
\end{math}\\
So $K$ gives  a one-to-one correspondence between $G_n$ and $Z^+_n$.\\
\begin{math}
\begin{Eqnarray}
\Mbox{Then } &W^+_{f+1}(n) 
&=	&\sum_{n'\in Z^+_n} W^+_f(n')\\
&&=	&\sum_{g\in G_n} W^+_f(K(g)), 
		&\mbox{ as } Z^+_n =\{K(g) | g \in G_n \},\\
&&=	&\sum_{g\in G_n} \prod_{p\in P_{K(g)}} \binom{g(p)+f}{f} 
		&\mbox{ by the induction hypothesis,}\\
&&=	&\sum_{g\in G_n} \prod_{p\in P_n} \binom{g(p)+f}{f} 
		&\mbox{ as } g(p)=0 \mbox{ for all } p\not\in P_n, \\
&&=	&\prod_{p\in P_n} \binom{s_p+f+1}{f+1}
		&\mbox{ by Lemma~\ref{lem:bernoulli},} 
\end{Eqnarray}
\end{math}\\
which proves the induction hypothesis.
\hfill $\Box$\\



\begin{Lemma} \label{lem:W+toW}
For all $f,n \in \nat$
\[	W^+_f(n)	= \sum_i \binom{f+1}{i+1} W_i(n).\]
\end{Lemma}
\noindent\textit{Proof.}
(By induction on $f$.)
For $f=0$ \\
$\begin{Eqnarray}
	&\sum_i \binom{0+1}{i+1} W_i(n) = \binom{1}{1}W_0(n) =1= W^+_0(n), \\
\end{Eqnarray}$\\
as required. Assume as the induction hypothesis: \\
$\begin{Eqnarray}
	&W^+_f(n)	&=	 &\sum_i \binom{f+1}{i+1} W_i(n).\\
\Mbox{Then }
&W^+_{f+1}(n)	
&=	&\sum_{n'\in Z^+_n} W^+_f(n) 
		&\mbox{ by definition}\\
&&=	&W^+_f(1) + \sum_{n'\in (Z_n \cup \{n\})} W^+_f(n) \\
&&=	&1 + \sum_{n'\in (Z_n \cup \{n\})} \sum_i \binom{f+1}{i+1} W_i(n')\\
&&	&\multicolumn{2}{r}{\mbox{ by the induction hypothesis,}}\\
&&=	&1 + \sum_i \binom{f+1}{i+1} \sum_{n'\in (Z_n \cup \{n\})}  W_i(n')\\
&&=	&\multicolumn{2}{l}
	{1 + \sum_i \binom{f+1}{i+1}\{ \sum_{n'\in Z_n}  W_i(n') + W_i(n)\}}\\
&&=	&1 + \sum_i \binom{f+1}{i+1}\{ W_{i+1}(n) + W_i(n)\}\\
&&=	&\multicolumn{2}{l}
	{1 + \sum_i \binom{f+1}{i} W_i(n) - \binom{f+1}{0} W_0(n) 
		+ \sum_i \binom{f+1}{i+1} W_i(n) }\\
&&=	&1 + \sum_i \{\binom{f+1}{i} +\binom{f+1}{i+1} \}W_i(n) - 1\\
&&=	&\sum_i \binom{f+2}{i+1} W_i(n)  
		& \mbox{ by Identity 5.8 in~\cite{mp:GKP89},}\\
\end{Eqnarray}$\\
which proves the induction hypothesis.
\hfill $\Box$\\


\begin{Theorem} \label{theorem:Wf}
The total number of ways, $W_f(n)$, of selecting sequences of $f$
proper factors of $n=\prod_{p\in P_n} p^{s_{p}},\ p$ any prime, is
given by:\\
\[ W_f(n) = \sum_{i} (-1)^{f+i} \binom{f+1}{i+1} \prod_{p} \binom{s_{p}+i}{i},\]
where the summation is over all integer values of $i$.
\end{Theorem}
\noindent\textit{Proof.}
From Lemma~\ref{lem:W+toW}:\\
$\begin{Eqnarray}
&W^+_f(n)	&=	&\sum_i (-1)^i \binom{f+1}{i+1} (-1)^{-i} W_i(n)\\
&(-1)^f W_f(n)	&=	&\sum_i (-1)^i \binom{f+1}{i+1} W^+_i(n) 
		&\mbox{ by Identity 5.48 in~\cite{mp:GKP89}}\\
&W_f(n)		&=	&\sum_i (-1)^{i+f} \binom{f+1}{i+1} \prod_{p\in P_n} \binom{s_p+f}{f} &\mbox{ by Lemma~\ref{lem:W+}.}
\hfill \Box
\end{Eqnarray}$\\


The Zeilberger algorithm cannot find a general (ie for any number of
primes) closed form solution to the series given in
Theorem~\ref{theorem:Wf}. However, only the terms with $0 \le i \le 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~\ref{theorem:Wf} must then be substituted using
Equation~\ref{eq:Nmn}, to give $N(n,n)$, the total number of
standardised reversible squares.


The formula for $W_f(n)$ when $n = \prod_{p} p^{s_{p}}$ can be specialised by setting $n =
2^r p^s$. $W_f(n)$ is then 
$\sum_{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 $\sum_{i} \binom{r}{i}
\binom{s}{i} \binom{r+s-1-i}{f-i}$ given by Lemma~\ref{lem:n=2^r.p^s}. 





\subsection{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~\ref{theorem:standardize}).

\begin{Theorem} \label{theorem:Mn}
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$. 
\end{Theorem}
\noindent\textit{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~\ref{theorem:legitimate}).

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.
\hfill $\Box$\\



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~\ref{theorem:one_to_one}). It has been shown that $M_{n} =
2^{n+1} (n/2)!^2$ (Theorem~\ref{theorem:Mn}) and that  $N(n,n) =  \sum_{f}
W_f(n)(W_f(n)+W_{f+1}(n))$ (Theorem~\ref{theorem:Nmn}), 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:
\newline

$\begin{array}{lll}
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
               &\sum_{i}\binom{r}{i} \binom{s}{i} \binom{r+s-1-i}{f-i}
&\frac{1}{2} \binom{2s}{s} \sum_{i} \binom{s}{i} \binom{r+s}{r-i} \binom{2r+s-i}{r+s}\\
		&			&\\
\prod_{p\in P_n} p^{s_{p}} ;  s_{2} > 1
               &\sum_{i}(-1)^{f+i} \binom{f+1}{i+1} \prod_{p}
\binom{s_p+i}{i} 
                                   &\sum_{f} W_f(n)(W_f(n) + W_{f+1})\\
\end{array}$\\
where $P_n$ is the set of primes dividing $n$.

\section{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~\cite{mp:RW39} used for constructing pandiagonal magic squares.
It has recently been shown~\cite{mp:TB99} 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.



\begin{thebibliography}{10}


\bibitem{mp:B97}
J. Bellew, 
\newblock Counting the number of compound and Nasik magic squares,
\newblock {\em Math. Today} {\bf 33} (1997) 111-118.

\bibitem{mp:BO98}
D.S. Br\'{e}e and K. Ollerenshaw, 
\newblock Pandiagonal magic squares from mixed auxiliary squares,
\newblock {\em Math. Today} {\bf 34} (1998) 105-111.

\bibitem{mp:Bro91}
A.E. Brouwer, 
\newblock Recursive constructions of mutually orthogonal Latin squares,
\newblock in:  J. D\'{e}nes and A.D. Keedwell, eds, {\em Latin squares: new developments in
the theory and applications}, (North-Holland, Amsterdam, 1991) 149-168.

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

\bibitem{mp:DK74}
J. D\'{e}nes and A.D. Keedwell, 
\newblock {\em Latin squares and their applications}
\newblock (Academic Press, London, 1974).

\bibitem{mp:Eul79}
L. Euler, 
\newblock Recherches sur une nouvelle esp\`{e}ce de quarr\'{e}s magiques. 
\newblock Memoir presented to the Academy of Sciences of St Petersburg on 8 March 1779.
\newblock Republished in {\em Leonhardi Euleri Opera Omnia} (1) {\bf 7} (1923) 291-392.

\bibitem{mp:Bes93}
B. Fr\'{e}nicle de Bessey, 
\newblock Des quarrez ou tables magiques,
\newblock in P. de la Hire, Sedileau and Pothenot, eds, {\em Divers ouvrages de
math\'{e}matique et de physique par messieurs de l'Acad\'{e}mie Royale des Sciences}
(l'Imprimerie Royale, Paris, 1693) 423-507.

\bibitem{mp:Fro66}
A.H. Frost, 
\newblock Invention of magic cubes, and construction of magic squares possessing
additional properties,
\newblock {\em Quarterly J. Math.} {\bf 7} (1866) 92-101.

\bibitem{mp:Fro78}
A.H. Frost, 
\newblock On the general properties of Nasik squares,
\newblock {\em Quarterly J. Math.} {\bf 15} (1878) 34-49.

\bibitem{mp:Gar76}
M. Gardner, 
\newblock Mathematical games: a breakthrough in magic squares and the first perfect
magic cube,
\newblock {\em Scientific American} {\bf 234} (1976) 118-123.

\bibitem{mp:GKP89}
R.L. Graham, D.E. Knuth and O. Patashnik, 
\newblock {\em Concrete mathematics,}  2nd edn (Addison-Wesley, Menlo Park, California,
1989).

\bibitem{mp:Kra30}
M. Kraitchik, 
\newblock {\em La math\'{e}matique des jeux ou r\'{e}cr\'{e}ations math\'{e}matiques}
(Stevens Fr\`{e}res, 
Brussels, 1930).

\bibitem{mp:McC97}
E. McClintock, 
\newblock On the most perfect forms of magic squares, with methods for their
production,
\newblock {\em Am. J. Math.} {\em 19} (1897) 99-120.

\bibitem{mp:Oll86}
K. Ollerenshaw, 
\newblock On `most perfect' or `complete' $8\times 8$ pandiagonal magic squares,
\newblock {\em Proc. Royal Soc.} {\bf A 407} (1986) 259-281.

\bibitem{mp:Oll89}
K. Ollerenshaw, 
\newblock Living mathematics: introduction to the 25th anniversary issue,
\newblock {\em Bulletin of the Institute of Mathematics and its Applications} {\bf 25} (1989)
50-56.

\bibitem{mp:OB82}
K. Ollerenshaw and H. Bondi, 
\newblock Magic squares of order four,
\newblock {\em Philosophical Trans. Royal Soc.} {\bf A 306} (1982) 443-532.

\bibitem{mp:OB98}
K. Ollerenshaw and D.S. Br\'{e}e, 
\newblock {\em Most-perfect pandiagonal magic squares: their construction
     and enumeration}
\newblock (Institute for Mathematics and its Applications, Southend-on-Sea, 1998).

\bibitem{mp:PWZ96}
M. Petkov$\check{\mathrm{s}}$ek, H.S. Wilf and D. Zeilberger, 
\newblock {\em A = B} (Peters, Wellesley Massachusetts, 1996).

\bibitem{mp:RW38}
B. Rosser and R.J. Walker, 
\newblock On the transformation group for diabolic magic squares of order
     four,
\newblock {\em Bull. Am. Math. Soc.} {\bf 44} (1938) 416-420.

\bibitem{mp:RW39}
B. Rosser and R.J. Walker, 
\newblock The algebraic theory of diabolic magic squares,
\newblock {\em Duke Math. J.} {\bf 5} (1939) 705-728.

\bibitem{mp:TB99}
A.Todd and D.S. Br\'{e}e,
\newblock A new method for constructing pandiagonal magic squares.
\newblock In draft.

\bibitem{mp:XL95}
C.-X. Xu and Z.-W. Lu, 
\newblock Pandiagonal magic squares,
\newblock in: D.-Z. Du and M. Li, eds, {\em Computing and combinatorics, Proc. COCOON '95,
Lecture Notes in Computer Science} {\bf 959} (Springer, Berlin, 1995)  388-391.

\end{thebibliography}
\end{document}
