Balanced integer arrays: A matrix packing theorem

AbstractLet tn be a vector of n positive integers that sum to 2n − 1. Let u denote a vector of n or more positive integers that sum to n2, and call u, n-universal if for every possible choice of t1, t2,…, tn, the components of the ti can be arranged in the successive rows of an n-row matrix (with 0 in each unused cell) so that u is the vector of column sums.It is shown that (n,…, n)(n times) is n-universal for every n. More generally, for odd n, any choice of t1, t3,…, tn can be placed in rows so that the column sums are (n, n−1,…, 2, 1); for even n, any choice of t2, t4,…, tn can be placed in rows so that the column sums are (n, n −1,…, 2, 1). Hence, any u that can be obtained from the sum of two rows whose nonzero components are, respectively, n, n −1,…, 2, 1 and n −1, n −2,…, 2, 1 (in any order, with 0's elsewhere) is n-universal.The problem examined is closely related to the graph conjecture that trees on 2, 3,…, n + 1 vertices can be superposed to yield the complete graph on n + 1 vertices