%% load in the RoseHulman Undergraduate Mathematics Journal Class
\documentclass{rhumj}
\pagestyle{empty}
%% You may add any additional packages and commands your paper uses here
%% If you use a separate file containing such commands, you will need to send this to the editor
%% in order for your paper to be properly typeset
%% PLEASE  Do not add formatting commands. These are already included in the rhumj.cls file
%Please fill in the fields below with your information in
%the order shown.
%\title{
%A Proof of the ``Magicness'' of the Siam Construction of a Magic Square
%}
%\author{
%Joshua Arroyo\affiliation{RoseHulman Institute of Technology}
%If there is more than one author use the following commands for
%each additional name
%Repeat the names of the authors here
%\authornames{
%Joshua Arroyo}
%Use the following command only if you need to make acknowledgement
%\acknowledgement{
%I would like to thank Dr. Holder for all of her help with the mathematics and grammar in this paper. I would also like to thank the RoseHulman Mathematics Department for the funding to present this work at the University of Dayton's Undergraduate Mathematics Day.\\*[\parskip]
%\hspace*{1.5em}}
%\abstract{
%A magic square is an $n \times n$ array filled with $n^2$ distinct positive integers $1, 2, \dots, n^2$ such that the sum of the $n$ integers in each row, column, and each of the main diagonals are the same. A Latin square is an $n\times n$ array consisting of $n$ distinct symbols such that each symbol appears exactly once in each row and column of the square. Many articles dealing with the construction of magic squares introduce the Siam method as a ``simple'' construction for magic squares. Rarely, however, does the article actually prove that the construction yields a magic square. In this paper, we describe how to decompose a magic square constructed by the Siam method into two orthogonal Latin squares, which in turn, leads us to a proof that the Siam construction produces a magic square.}
%\vol{19, No. 1}
%\date{Spring 2018}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{caption}
\usepackage{multicol}
\usepackage{placeins}
\usepackage{indentfirst}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{exmp}{Example}[section]
%Use \maketitle conmmand right after \begin{document}
\begin{document}
%\maketitle
%% keep the following line commented out
%\setcounter{page}{19}
%%
%% Your Paper goes here
\FloatBarrier
\section{Background}
{\em Magic squares} of order $n$ are $n \times n$ arrays filled with distinct positive integers $1, 2, \ldots, n^2$ arranged in such a way that the sum of the integers in each row, column, and main diagonals are all the same. The sum of the entries in each row, column, and main diagonals is $\dfrac{n(n^2+1)}{2}$, which is called the {\em magic sum}.
Magic squares have a long history with the earliest known magic square being the LoShu tortoise from ancient China. Over the years, many algorithms have been made to create magic squares. Usually these algorithms only work for certain order squares. For instance, the Siam method (which is discussed in the next section) only works for odd orders.
\begin{figure}[h]
\centering
$\vcenter{\hbox{\includegraphics[height=4cm]{LoShu_Tortoise.png}}}$
\hspace{2cm}
$\begin{bmatrix}
4 & 9 & 2 \\
3 & 5 & 7 \\
8 & 1 & 6 \\
\end{bmatrix} $
\caption{LoShu Tortoise, the earliest known magic square. The number of dots on the tortoise correspond to the magic square on the right.}
\end{figure}
{\em Latin squares} of order $n$ are $n \times n$ arrays with $n$ distinct elements where each row and column have exactly one of each element. Two Latin squares are considered {\em orthogonal mates} if when superimposed, each of the possible $n^2$ ordered pairs occurs exactly once. That is, if $L_{1}$ and $L_{2}$ are two Latin squares of order $n$, then the $n \times n$ array $(L_{1}, L_{2})$ contains $n^2$ distinct entries given by
\begin{equation}
(L_{1},L_{2})_{i,j}=(L_{1}(i,j),L_{2}(i,j)).
\end{equation}
\noindent This array is known as a GraecoLatin square.
\begin{exmp}
Consider the two Latin squares $L_{1}$ and $L_{2}$ given below.
\[
L_{1}=\begin{bmatrix}
{3} & {4} & {0} & {1} & {2} \\
{4} & {0} & {1} & {2} & {3} \\
{0} & {1} & {2} & {3} & {4} \\
{1} & {2} & {3} & {4} & {0} \\
{2} & {3} & {4} & {0} & {1} \\
\end{bmatrix}
\hspace{1cm}
L_{2}=\begin{bmatrix}
{1} & {3} & {0} & {2} & {4} \\
{2} & {4} & {1} & {3} & {0} \\
{3} & {0} & {2} & {4} & {1} \\
{4} & {1} & {3} & {0} & {2} \\
{0} & {2} & {4} & {1} & {3} \\
\end{bmatrix}
\]
\pagebreak
If we superimpose $L_{1}$ and $L_{2}$ to obtain
\[
(L_{1},L_{2})=
\begin{bmatrix}
{(3,1)} & {(4,3)} & {(0,0)} & {(1,2)} & {(2,4)} \\
{(4,2)} & {(0,4)} & {(1,1)} & {(2,3)} & {(3,0)} \\
{(0,3)} & {(1,0)} & {(2,2)} & {(3,4)} & {(4,1)} \\
{(1,4)} & {(2,1)} & {(3,3)} & {(4,0)} & {(0,2)} \\
{(2,0)} & {(3,2)} & {(4,4)} & {(0,1)} & {(1,3)} \\
\end{bmatrix}
\]
\noindent then we see that each ordered pair $(a,b)$ with $0\leq a,b\leq 4$ appears exactly once. For instance, observe that $(L_{1},L_{2})_{1,1}=(L_{1}(1,1),L_{2}(1,1))=(3,1)$ which appears exactly once in the GraecoLatin square.
\end{exmp}
A {\em transversal} is a set of $n$ cells on a Latin square of order $n$ where each cell contains a different element and no two share a row or column. {\em Disjoint transversals} are transversals that do not overlap. A set of $n$ disjoint transversals on a Latin square of order $n$ can be relabeled to be a new Latin square. We use this fact in Section 3 to show that a magic square can be decomposed into two Latin squares. Finally, for any array, the diagonal containing the top left entry and the bottom right entry is referred to as the {\em main front diagonal}. Similarly, the diagonal containing the top right entry and the bottom left entry is referred to as the {\em main back diagonal}.
\vspace{.5in}
\FloatBarrier
\section{The Siam Method}
The {\em Siam method} (also known as the Siamese method or the De la Loub\`ere method) is an algorithm used to create magic squares of odd order. To create a magic square using this method, one places elements on an array starting with 1 and increasing by one until $n^2$ is reached. The first element is placed in the middle of the top row. Then elements are placed diagonally up and to the right (with the array looping around itself) until an already occupied location is encountered. When that happens, place the element one below where the last element was placed, and continue as before. The element you place will be the starting element of the next loop which we will refer to as a back diagonal.\\
\begin{exmp}
We show how to construct a magic square of order 5 using the Siam method by referring to the square in Figure 2. First the 1 is placed. Then, we follow the arrow up and to the right, looping down to the bottom right to place the 2. Following the arrow again, it loops to the middle left, which is where the 3 goes. Since, if we move diagonally again, we encounter an occupied cell containing a 1, we must instead place the 4 directly below the 3. The process is then repeated until the array is filled. Once the array is filled, the Siam method is finished and the result should be a magic square.
\end{exmp}
\begin{figure}[!ht]
\centering
\includegraphics[]{Siam_Method_Example.jpg}
\caption{This magic square was created by the Siam method.}
\end{figure}
\FloatBarrier
\section{Deconstruction into Latin Squares}
We claimed that the Siam method is an algorithm that constructs a magic square of odd order. By splitting this constructed square into two orthogonal Latin squares and an array of 1s, we can show that the Siam method does, in fact, create a magic square of odd order.\\
Let $S$ be an array of order $n$ created by the Siam method, and let $M=SJ_{n}$ where $J_{n}$ is the $n \times n$ array of all 1s. Note that $M$ consists of the $n^2$ distinct entries $0,1,\ldots,n^21$. We then split $M$ into two Latin squares.\\
\begin{exmp}
When $n=5$ and
\[
S=
\begin{bmatrix}
17 & 24 & 1 & 8 & 15 \\
23 & 5 & 7 & 14 & 16 \\
4 & 6 & 13 & 20 & 22 \\
10 & 12 & 19 & 21 & 3 \\
11 & 18 & 25 & 2 & 9 \\
\end{bmatrix}
\]
\[
SJ_n=
\begin{bmatrix}
17 & 24 & 1 & 8 & 15 \\
23 & 5 & 7 & 14 & 16 \\
4 & 6 & 13 & 20 & 22 \\
10 & 12 & 19 & 21 & 3 \\
11 & 18 & 25 & 2 & 9 \\
\end{bmatrix}

\begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]
\[
=\begin{bmatrix}
16 & 23 & 0 & 7 & 14 \\
22 & 4 & 6 & 13 & 15 \\
3 & 5 & 12 & 19 & 21 \\
9 & 11 & 18 & 20 & 2 \\
10 & 17 & 24 & 1 & 8 \\
\end{bmatrix}
=M
\]
\end{exmp}
Now, each element can be uniquely expressed as $m_{i,j}=nb_{i,j}+u_{i,j}$ where $b_{i,j}=\left \lfloor{\frac{m_{i,j}}{n}}\right \rfloor$ and $u_{i,j}=m_{i,j}$ mod $n$. We then form the arrays $L_{b}$ and $L_u$ by assigning $L_b (i,j)=b_{i,j}$ and $L_u (i,j)=u_{i,j}$. We can then show that both of these arrays are Latin squares. Given that $S$ was constructed by increasing along the back diagonals as we move along the back diagonal, $u_{i,j}$ will increase, that is $u_{i,j}+1 \equiv u_{i1,j+1}$ (mod $n$). Since each back diagonal has exactly $n$ elements, elements will not be repeated in the same back diagonal. The starting element of each back diagonal starts one column to the left and two rows down of the back diagonal before it. Since the Siam method only works for odd orders, the start of each back diagonal will be in a different row (and each will start in a different column as there are $n$ back diagonals). Thus, the starting element of each back diagonal will be in a different row and column from the starting element of another back diagonal. This means that each element of the any back diagonal will be in a different row and column from that element in another back diagonal. Therefore, $L_{u}$ will be a Latin square. Since each back diagonal has $n$ different elements and do not overlap they will form a set of $n$ disjoint transversals on $L_{u}$. If we reassign these transversals to their corresponding back diagonals (starting with 0) we obtain $L_{b}$ (as the elements of each back diagonal are the elements of the last back diagonal plus $n$). Thus, $L_{b}$ will also be a Latin square. Since $M$ has elements 0,\ldots, $n^21$, every $(b_{i,j},u_{i,j})$ pair is different. Thus the Latin squares $L_{b}$ and $L_{u}$ are orthogonal mates.\\
\begin{exmp}
When $n=5$, we have that the Siam method produced the square
\[
S=
\begin{bmatrix}
17 & 24 & 1 & 8 & 15 \\
23 & 5 & 7 & 14 & 16 \\
4 & 6 & 13 & 20 & 22 \\
10 & 12 & 19 & 21 & 3 \\
11 & 18 & 25 & 2 & 9 \\
\end{bmatrix}
\]
which in turn yields the squares
\[
S=
\begin{bmatrix}
16+1 & 23+1 & 0+1 & 7+1 & 14+1 \\
22+1 & 4+1 & 6+1 & 13+1 & 15+1 \\
3+1 & 5+1 & 12+1 & 19+1 & 21+1 \\
9+1 & 11+1 & 18+1 & 20+1 & 2+1 \\
10+1 & 17+1 & 24+1 & 1+1 & 8+1 \\
\end{bmatrix}
\]
\[
S=
\begin{bmatrix}
16 & 23 & 0 & 7 & 14 \\
22 & 4 & 6 & 13 & 15 \\
3 & 5 & 12 & 19 & 21 \\
9 & 11 & 18 & 20 & 2 \\
10 & 17 & 24 & 1 & 8 \\
\end{bmatrix}
+
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]
\[
S=
5
\begin{bmatrix}
3 & 4 & 0 & 1 & 2 \\
4 & 0 & 1 & 2 & 3 \\
0 & 1 & 2 & 3 & 4 \\
1 & 2 & 3 & 4 & 0 \\
2 & 3 & 4 & 0 & 1 \\
\end{bmatrix}
+
\begin{bmatrix}
1 & 3 & 0 & 2 & 4 \\
2 & 4 & 1 & 3 & 0 \\
3 & 0 & 2 & 4 & 1 \\
4 & 1 & 3 & 0 & 2 \\
0 & 2 & 4 & 1 & 3 \\
\end{bmatrix}
+
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 \\
\end{bmatrix}
\]
\[
S=5L_b+L_u+J_5
\]
\end{exmp}
\FloatBarrier
\section{Proof that the Siam Method Creates a Magic Square}
In order to prove that a square constructed by the Siam Method is a magic square, we must show that each row, column, and main diagonals sum to the magic sum.\\
Label the rows and columns of all arrays of order n from 0 to $n1$, from top to bottom and left to right, like the example below.\\
\[
\begin{bmatrix}
{(0,0)} & {(0,1)} & \ldots & {(0,n1)} \\
{(1,0)} & {(0,1)} & \ldots & {(1,n1)} \\
\vdots & \vdots & \ddots & \vdots \\
{(n1,0)} & {(n1,1)} & \ldots & {(n1,n1)} \\
\end{bmatrix}
\]
For $S$, let each back diagonal followed by the Siam method be given a number $b$, $b=0, \ldots ,n1$, in the order that they were created. Let each element in each of those back diagonals be given a number $u$, $u=0, \ldots ,n1$ in the order that they were created. Each new back diagonal starts 2 below and 1 to the left of the last one, each new entry of the back diagonal is up 1 and to the right 1. Since the first entry is at $(0,\frac{n1}{2})$, we can define the position of any $m_{i,j}\in S$ as
\begin{equation}
(i,j)=(2,1)b+(1,1)u+\left(0,\frac{n1}{2}\right).
\end{equation}
\begin{lemma}
The sum of the entries of the main front diagonal of $S$ is the magic sum $\dfrac{n(n^2+1)}{2}$.
\end{lemma}
\begin{proof}
The square $L_{b}$ is equivalent to a matrix created from the $b$ values while $L_{u}$ is equivalent to a matrix created from the $u$ values. Thus, if we set $(i,j)=(k,k)$ we discover the nature of the main front diagonal of both our Latin squares.\\
\begin{equation}
\begin{gathered}
k=2bu,\\
k=b+u+\frac{n1}{2}.
\end{gathered}
\end{equation}
When this system of equations is solved for $b$ and $u$ then we get (in mod $n$)
\begin{equation}
\begin{gathered}
b=2k+\frac{1n}{2},\\
u=3kn+1.
\end{gathered}
\end{equation}
\noindent This gives us the values of $L_{b}$ and $L_{u}$ on their main front diagonals. Thus we can sum up the entries of the main front diagonal of $S=nL_b+L_u+J_n$ as follows by ranging $k$ from $0$ to $n1$. Given $b=2k+\frac{1n}{2}$, $u=3kn+1$, and $nL_{b}+L_{u}+J_{n}=S$ the sum of the main front diagonal will be\\
\begin{align*}
\sum_{k=0}^{n1}S_{k,k}
&=n\sum_{k=0}^{n1}\left(2k+\frac{1n}{2}\right)+\sum_{x=0}^{n1}(3kn+1)+\sum_{k=0}^{n1}1\\
&=\frac{n^2(n1)}{2}+\frac{n(n1)}{2}+n\\
&=\frac{n(n^2+1)}{2}.\\
\end{align*}
Thus, the main front diagonal of $S$ sums up to the magic sum.
\end{proof}
\begin{lemma}
The sum of the entries of the main back diagonal of $S$ is the magic sum $\dfrac{n(n^2+1)}{2}$.
\end{lemma}
\begin{proof}
To get the entries of the main back diagonal set $(i,j)=(k,n1k)$
\begin{equation}
\begin{gathered}
k=2bu,\\
n1k=b+u+\frac{n1}{2}.
\end{gathered}
\end{equation}
When this system of equations is solved for $b$ and $u$, we find that (in mod $n$)
\begin{equation}
\begin{gathered}
b=\frac{n1}{2},\\
u=n1k.
\end{gathered}
\end{equation}
We can then similarly sum up the main back diagonal by ranging $k$ from $0$ to $n1$. Given $b=\frac{n1}{2}$, $u=n1+k$, and $nL_{b}+L_{u}+J_{n}=S$ the sum of the main back diagonal will be
\begin{align*}
\sum_{k=0}^{n1}S_{k,n1k}
&=n\sum_{k=0}^{n1}\frac{n1}{2}+\sum_{k=0}^{n1}(n1k)+\sum_{k=0}^{n1}1\\
&=\frac{n^2(n1)}{2}+\frac{n(n1)}{2}+n\\
&=\frac{n(n^2+1)}{2}.
\end{align*}
Thus, the main back diagonal sums up to the magic sum.
\end{proof}
Finally, we need to show that the sum of the rows and columns of $M$ are also equal to the magic sum.
\begin{lemma}
The sum of the entries of the rows and columns of $S$ is the magic sum $\dfrac{n(n^2+1)}{2}$.
\end{lemma}
\begin{proof}
By the creation of the Latin squares, $L_b$ and $L_u$, each row and column of the Latin squares contain the distinct entries $0,\ldots,n1$ exactly once. By our construction, $S=nL_{b}+L_{u}+J_{n}$. Thus, the sum of each row and column is
\begin{align*}
n\sum_{k=0}^{n1}k+\sum_{k=0}^{n1}k+\sum_{k=0}^{n1}1&=\frac{n^2(n1)}{2}+\frac{n(n1)}{2}+n\\
&=\frac{n(n^2+1)}{2}.
\end{align*}
Thus all the rows and columns sum up to the magic sum.
\end{proof}
\begin{theorem}
The Siam method produces a magic square.
\end{theorem}
\begin{proof}
The previous three lemmas prove that each row, column, and main diagonal sum to the magic sum of $\frac{n^2(n^2+1)}{2}$. Therefore, the magic square we constructed using the Siam method is in fact a magic square.
\end{proof}
\begin{thebibliography}{9}
\bibitem{Textbook}
Charles F. Laywine, and Gary L. Mullen.
\textit{Discrete Mathematics Using Latin Squares}.
John Wiley \& Sons Inc., 1998.
\bibitem{Image}
Thoth Adan The Power of Symbols,
\\\texttt{http://www.thothadan.com/en/symbolslen/loshu.html}
\end{thebibliography}
\end{document}