Strongly connected multivariate digraphs

Yaokun Wu¹ ; Zeying Xu ; Yinfeng Zhu

¹Shanghai Jiao Tong University

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

Generalizing the idea of viewing a digraph as a model of a linear map, we suggest a multi-variable analogue of a digraph, called a hydra, as a model of a multi-linear map. Walks in digraphs correspond to usual matrix multiplication while walks in hydras correspond to the tensor multiplication introduced by Robert Grone in 1987. By viewing matrix multiplication as a special case of this tensor multiplication, many concepts on strongly connected digraphs are generalized to corresponding ones for hydras, including strongly connectedness, periods and primitiveness, etc. We explore the structure of all possible periods of strongly connected hydras, which turns out to be related to the existence of certain kind of combinatorial designs. We also provide estimates of largest primitive exponents and largest diameters of relevant hydras. Much existing research on tensors are based on some other definitions of multiplications of tensors and so our work here supplies new perspectives for understanding irreducible and primitive nonnegative tensors.

Détail

DOI : 10.37236/6539

Classification : 05C20, 05C40
Mots-clés : de Bruijn form, cyclic decomposition, diameter, Markov operator, period, phase space, primitive exponent, hydra, tensor multiplication