Return to Revisions

Every $n\times n$ matrix with integer entries and all row sums and all column sums equal ("semi-magic square") can be written as an integer linear combination of at most $n^2-2n+2$ permutation matrices. Almost all such matrices can't be written as integer linear combinations of fewer permutation matrices – the ones that can be so written form a finite union of lower dimensional sets. Yet it's not so easy to find, say, a $4\times4$ integer matrix with, say, two- or three-digit entries that can't be written as an integer linear combination of nine or fewer permutation matrices.