A linear bound on the k-rendezvous time for primitive sets of NZ matrices
This work addresses a theoretical problem in matrix theory and automata synchronization, offering incremental progress by extending known results to specific matrix sets.
The paper tackles the problem of bounding the k-rendezvous time for primitive sets of nonnegative matrices without zero rows or columns, proving it is at most linear in matrix size for small k, and provides improved upper bounds with numerical comparisons to heuristic methods.
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.