Mathematics 357 – Combinatorics Problem Set 8 Due: April 22, 2005

I. A magic square is an n × 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 × 4 magic square appears in the engraving Melencolia I by Albrecht Dürer:

( \begin{matrix}16 & 3 & 2 & 13 \\ 5 & 10 & 11 & 8 \\ 9 & 6 & 7 & 12 \\ 4 & 15 & 14 & 1 \end{matrix} )

(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 distinct integers 1, 2, …, n^{2} (as in Dürer’s magic square) is often included, we will 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: Given positive integers s, n, how many different n × n magic squares with row and column sum equal to s and m_{ij} ≥ 0 for all i, j are there?

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 × n magic square is a linear combination of n × n permutation matrices with nonnegative integer coefficients.

From now on, we will restrict to the case n = 3 for simplicity. By part A, we know that any 3 × 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

\begin{aligned}I & = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )  S = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} )  S^{2} = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) \\ T_{12} & = ( \begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} )  T_{13} = ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} )  T_{23} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ) \end{aligned}

are the 3 × 3 permutation matrices.

B) Exhibit an explicit linear dependence relation between the 6 3×3 permutation matrices and show that they only span a 5-dimensional subspace of the vector space of 3 × 3 matrices.

C) Taking the linear dependence from B into account, how many distinct integer 3 × 3 magic squares are there with s = 2, s = 3, s = 4?

D) Find and prove a general formula for the number of distinct non-negative integer 3×3 magic squares with row and column sum s.

From the Text: Chapter 11/22, 23, 24, 28, 29, 57.