A linear bound on the k-rendezvous time for primitive sets of NZ matrices

03/25/2019

∙

by   Umer Azfar, et al.

∙

0

∙

share

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 (the k-RT). We prove that this value is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We then report numerical results comparing our upper bound on the k-RT with heuristic approximation methods.