\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Problem Set 8}
\centerline{\it Due: April 22, 2005}
\bigskip
\noindent
I.  A {\it magic square\/} is an $n\times n$ integer matrix $M = (m_{ij})$
with the property that the sum of the entries in each row 
and in each column is the same.   For instance, a famous 
$4\times 4$ magic square appears in the engraving {\it Melencolia I\/} by Albrecht 
D\"urer:
$$\pmatrix{16&3&2&13\cr
          5&10&11&8\cr
          9&6&7&12\cr
          4&15&14&1\cr}$$
(see link on course homepage).  
The row and column sums in this array all equal $34$.  Although the extra
condition that the $m_{ij}$ are the {\it distinct\/}
integers $1,2,\ldots,n^2$ (as in D\"urer's magic
square) is often
included, we will {\it not\/} make that part of the definition.
Also, many familiar examples of magic squares
have equal diagonal sums and other interesting properties; 
we will not require that either.  An interesting problem is this:
{\it Given positive integers $s, n$, how
many different $n \times n$ magic squares with row and column sum equal to $s$
and $m_{ij} \ge 0$ for all $i,j$ are there?}
\bigskip
\item{A)}  In class, using Hall's Theorem, we showed that any $(0,1)$-matrix
with equal row and column sums $d$ is a sum of $d$ distinct permutation
matrices.  Adapt the proof to show that any integer $n\times n$ magic square
is a linear combination of $n \times n$ permutation matrices with nonnegative integer
coefficients.  
\bigskip
\item{}
From now on, we will restrict to the case $n = 3$ for 
simplicity.  By part A, we know that any $3\times 3$ non-negative integer 
magic square can be written as
$$M = aI + bS + cS^2 + dT_{12} + eT_{13} + fT_{23}$$
where $a,b,c,d,e,f$ are non-negative integers,  
$s = a + b + c + d + e + f$, and 
$$\eqalign{I   &=\pmatrix{1&0&0\cr
                             0&1&0\cr
                             0&0&1\cr} \qquad
               S = \pmatrix{0&0&1\cr
                         1&0&0\cr
                         0&1&0\cr}\qquad
           S^2 =\pmatrix{0&1&0\cr
                          0&0&1\cr
                          1&0&0\cr}\cr
           T_{12} &= \pmatrix{0&1&0\cr
                              1&0&0\cr
                              0&0&1\cr}\qquad
             T_{13} = \pmatrix{0&0&1\cr
                              0&1&0\cr
                              1&0&0\cr}\qquad
           T_{23} = \pmatrix{1&0&0\cr
                              0&0&1\cr
                              0&1&0\cr}\cr}$$
are the $3\times 3$ permutation matrices.

\bigskip
\item{B)} Exhibit an explicit linear dependence relation between
the 6 $3\times 3$ permutation matrices and show that they only span 
a 5-dimensional subspace of the vector space of $3\times 3$ matrices.

\bigskip
\item{C)} Taking the linear dependence from B into account, how 
many distinct integer $3\times 3$ magic squares are there 
with $s = 2$, $s = 3$, $s = 4$?

\bigskip
\item{D)}  Find and prove a general formula for the 
number of distinct non-negative integer
$3\times 3$ magic squares with row and column sum $s$.
\bigskip
\noindent
{\it From the Text:} Chapter 11/22, 23, 24, 28, 29, 57.
\bye