A semi-magic square is a square array of nonnegative integers with all row sums and all column sums equal.
By a theorem of Konig, every semi-magic square can be decomposed into a linear combination of permutation matrices with positive integer coefficients. The decomposition is not, in general, unique. Among all the decompositions of a semi-magic square AA, we may ask for one that minimizes the number of distinct permutation matrices; that number,
we call β(A)β(A). We discuss some results concerning β(A)β(A), and some open questions. We also widen the topic to discuss matrices with entries that are arbitrary integers, not just nonnegative ones, and to discuss matrices where the entries are taken from the integers modulo nn.
Tue, 10/05/2016 - 12:00pm to 1:00pm
RC-4082, The Red Centre, UNSW