## Abstract

Building on the weak CSR approach developed in a previous paper by Merlet, Nowak and Sergeev [15], 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

The new bounds on

*T = max(T*, where_{1},T_{2})*T*is a bound on the time after which the weak CSR expansion starts to hold and_{1}*T*is a bound on the time after which the first CSR term starts to dominate._{2}The new bounds on

*T*and_{1}*T*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_{2}*T*, 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_{1}*T*, we introduce the novel concept of walk reduction threshold and establish bounds on it that use both cyclicity and factor rank._{2}Original language | English |
---|---|

Pages (from-to) | 279-309 |

Number of pages | 31 |

Journal | Linear Algebra and its Applications |

Volume | 611 |

Early online date | 29 Oct 2020 |

DOIs | |

Publication status | Published - 15 Feb 2021 |

## Keywords

- Max-plus
- matrix powers
- transient
- periodicity
- digraphs