Projects per year
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 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 GregoryKirklandPullman, 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.
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 GregoryKirklandPullman, 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.
Original language  English 

Pages (fromto)  279309 
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
 Maxplus
 digraphs
 matrix powers
 periodicity
 transient
Fingerprint
Dive into the research topics of 'New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank'. Together they form a unique fingerprint.Projects
 1 Finished

Tropical Optimisation
Engineering & Physical Science Research Council
1/04/17 → 31/08/19
Project: Research Councils