Strongly Connected Multivariate Digraphs

  • Yaokun Wu
  • Zeying Xu
  • Yinfeng Zhu
Keywords: De Bruijn form, Cyclic decomposition, Diameter, Markov operator, Period, Phase space, Primitive exponent, Hydra, Tensor multiplication


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.

Article Number