Balancing permuted copies of multigraphs and integer matrices

Given a square matrix Α over the integers, we consider the Z-module M_A generated by the set of all matrices that are permutation-similar to A. Motivated by analogous problems on signed graph decompositions and block designs, we are interested in the completely symmetric matrices aI + bJ belonging to M_A. We give a relatively fast method to compute a generator for such matrices, avoiding the need for a very large canonical form over Z. We consider several special cases in detail. In particular, the problem for symmetric matrices answers a question of Cameron and Cioabǎ on determining the eventual period for integers λ such that the λ-fold complete graph λK_n has an edge-decomposition into a given (multi)graph.