Math Thesis Archive

Home Personnel Programs Jobs Computing Organization Information Research menubar


Magic square subclasses as linear Diophantine systems


Ezra Q. Halleck

The solution space of a system of linear homogeneous equations with integer coefficients over the integers is a $\D{Z}$-module. Geometrically, the solutions form a lattice, the integral points in a subspace of $\D Q^n$. Magic squares are $n \times n$ matrices with equal row and column sums; a basis consists of a subset of the permutation matrices. Pandiagonal squares or $P$-squares are magic squares with equal broken diagonal sums; we show that a basis consists of a subset of ``octagons", introduced by \cite{Andress}.

Requiring the solutions of a system of equations to be nonnegative as well as integral earns the modifier \emph{Diophantine}. Geometrically, such a Diophantine set consists of the integral points of a pointed convex polyhedral cone: the intersection of the non-Diophantine lattice of integer solutions with the $n$-dimensional generalization of the nonnegative octant.

Take each solution of a Diophantine set $\ga=(\ga_1,\ga_2,\dots,\ga_n)$ and form the monomial $x^\ga=x_1^{\ga_1}x_2^{\ga_2}\dots x_n^{\ga_n}$. The formal power series in $n$ variables formed by summing all such monomials is a rational function \cite[Section 4.6]{Stanley:E}.

The solutions appearing in the denominators of a generating function are \emph{extreme} or \emph{completely fundamental} solutions. There is a one-to-one correspondence between these solutions and the extreme rays emanating from the point of the cone.

For magic squares, the extreme solutions are the $n \times n$ permutation matrices, but the generating function of solutions is unknown in full generality. For $P$-squares, even the extreme points are unknown. Our computer investigations have yielded the extreme points for pandiagonal systems for all $n\leq 7$.

Our investigation has included other Diophantine sets of matrices, including $W$-squares. We have the generating function for one subclass of $P$-squares, the linear span of cyclic matrices.

To decompose a matrix from a magic square subclass, extract as large a copy as possible of $J$, the matrix of 1's. The residue is a square on the boundary of the cone. We decompose the boundary by looking at a cross section polytope.

The ability to immediately move to the boundary is related to the fact that the associated Diophantine ring is Gorenstein.

Home | Personnel | Programs |Jobs | Computing | Organization | Department | Research