Affiliations: [a] Department of Economics, Statistics and Research, Banca d’Italia (Central Bank of Italy), Largo Guido Carli 1, 00044 Frascati, Roma, Italy. [email protected] | [b] ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium. [email protected] | [c] ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium. [email protected] | [d] ICTEAM, Université Catholique de Louvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Economics, Statistics and Research, Banca d’Italia (Central Bank of Italy), Largo Guido Carli 1, 00044 Frascati, Roma, Italy
Note: [†] R. M. Jungers is a FNRS Research Associate. He is supported by the French Community of Belgium, the Walloon Region and the Innoviris Foundation.
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.
Keywords: Primitive set of matrices, matrix semigroups, synchronizing automaton, Černý conjecture
