Primitive Sets of Nonnegative Matrices and Synchronizing Automata
(2018) SIAM Journal on Matrix Analysis and Applications — Vol. 39, n° 1, p. 83-98 (2018)
Files
16m1094099.pdf
Open Access - Adobe PDF
- 268.16 KB
Details
- Authors
Gerencsér, Balázs 
- Abstract
- A set of nonnegative matrices M = {M1, M2, . . . , Mk} is called primitive if there exist possibly equal indices i1, i2, . . . , im such that Mi1Mi2 · · · Mim is entrywise positive. The length of the shortest such product is called the exponent of M. Recently, connections between synchronizing automata and primitive sets of matrices were established. In the present paper, we strengthen these links by providing equivalence results, both in terms of combinatorial characterization and computational complexity. We pay special attention to the set of matrices without zero rows and columns, denoted by NZ, due to its intriguing connections to the Cern´y conjecture. We rely on syn- ˇ chronizing automata theory to derive a number of results about primitive sets of matrices. Making use of an asymptotic estimate by Rystsov [Cybernetics, 16 (1980), pp. 194–198], we show that the maximal exponent exp(n) of primitive sets of n × n matrices satisfy limn→∞ log exp(n) n = log 3 3 and that the problem of deciding whether a given set of matrices is primitive is PSPACE-complete, even in the case of two matrices. Furthermore, we characterize the computational complexity of different problems related to the exponent of NZ matrix sets and present a bound of 2n 2 − 5n + 5 on the exponent when considering the subclass of matrices having total support.
- Affiliations
Citations
Gerencsér, B., Gusev, V., & Jungers, R. (2018). Primitive Sets of Nonnegative Matrices and Synchronizing Automata. SIAM Journal on Matrix Analysis and Applications, 39(1), 83-98. https://doi.org/10.1137/16m1094099 (Original work published 2018)