Balancing permuted copies of multigraphs and integer matrices

Given a square matrix A over the integers, we consider the Z-module MA 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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2023-08, Vol.198, p.105756, Article 105756
Main Authors: del Valle, Coen, Dukes, Peter J.
Format: Article
Language:English
Subjects:
Combinatorial matrix theory
Graph decomposition
Permutation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a square matrix A over the integers, we consider the Z-module MA 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 MA. We give a relatively fast method to compute a generator for such matrices, avoiding the need for a very large canonical form over Z. Several special cases are considered. 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 λKn has an edge-decomposition into a given (multi)graph.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2023.105756