On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

Abstract

We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T₁, T₂}, where T₁ is the weak CSR threshold and T₂ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T₁ and T₂, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T₁, which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.

Keywords:

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

AMS Classifications:

• 15A18
• 15A23
• 90B35

Acknowledgments

We are grateful to Stéphane Gaubert and anonymous referees of the paper for many constructive and helpful suggestions and comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partially supported by Agence Nationale de la Recherche (ANR) Perturbations [grant number ANR-10-BLAN0106]. The work of S. Sergeev was also supported by Engineering and Physical Sciences Research Council (EPSRC) [grant number EP/P019676/1].