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

Glenn Merlet, Thomas Nowak, Sergei Sergeev

Research output: Contribution to journalArticlepeer-review

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{T1,T2}, where T1 is the weak CSR threshold and T2 is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T1 and T2, 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 T1, 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.
Original languageEnglish
JournalLinear and Multilinear Algebra
Early online date3 Feb 2021
DOIs
Publication statusE-pub ahead of print - 3 Feb 2021

Fingerprint

Dive into the research topics of 'On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers'. Together they form a unique fingerprint.

Cite this