New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
Preprint
Abstract
Building on the weak CSR approach developed in a previous paper by Merlet, Nowak and Sergeev, we establish new bounds for the periodicity threshold of the powers of a tropical matrix. According to that approach, bounds on the ultimate periodicity threshold take the form of T=max(T_1,T_2), where T_1 is a bound on the time after which the weak CSR expansion starts to hold and T_2 is a bound on the time after which the first CSR term starts to dominate. The new bounds on T_1 and T_2 established in this paper make use of the cyclicity of the associated graph and the (tropical) factor rank of the matrix, which leads to much improved bounds in favorable cases. For T_1, in particular, we obtain new extensions of bounds of Schwarz, Kim and Gregory-Kirkland-Pullman, previously known as bounds on exponents of digraphs. For similar bounds on T_2, we introduce the novel concept of walk reduction threshold and establish bounds on it that use both cyclicity and factor rank.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Generalizations of bounds on the index of convergence to weighted digraphsDiscrete Applied Mathematics, 2014
- Weak CSR expansions and transience bounds in max-plus algebraLinear Algebra and its Applications, 2014
- New transience bounds for long walks in weighted digraphs2013
- Max-linear Systems: Theory and Algorithms2010
- Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classesLinear Algebra and its Applications, 2009
- Powers of matrices over an extremal algebra with applications to periodic graphsMathematical Methods of Operations Research, 1997
- A bound on the exponent of a primitive matrix using Boolean rankLinear Algebra and its Applications, 1995
- Combinatorial Matrix Theory1991
- On the exponent of a primitive digraphLinear Algebra and its Applications, 1985
- Unzerlegbare, nicht negative MatrizenMathematische Zeitschrift, 1950