A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices

Catalano, Costanza;Azfar, Umer;Charlier, Ludovic;Jungers, Raphaël
(2021) Fundamenta Informaticae — Vol. 180, n° 4, p. 289-314 (2021)

Files

190310421.pdf
  • Open Access
  • Adobe PDF
  • 1.99 MB
Download

Details

Authors
  • Catalano, CostanzaBanca d’Italia (Central Bank of Italy), Roma
    Author
  • Azfar, UmerICTEAM, Université Catholique de Louvain, Belgium.
    Author
  • Charlier, LudovicICTEAM, Université Catholique de Louvain, Belgium.
    Author
  • Jungers, RaphaëlUCLouvain
    Author
Abstract
A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the length of the shortest product of a primitive set having a column or a row with k positive entries, called its k-rendezvous time (k-RT), in the case of sets of matrices having no zero rows and no zero columns. We prove that the k-RT is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We provide two upper bounds on the k-RT: the second is an improvement of the first one, although the latter can be written in closed form. We then report numerical results comparing our upper bounds on the k-RT with heuristic approximation methods.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Catalano, C., Azfar, U., Charlier, L., & Jungers, R. (2021). A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices. Fundamenta Informaticae, 180(4), 289-314. https://doi.org/10.3233/fi-2021-2043 (Original work published 2021)