General Transience Bounds in Tropical Linear Algebra via Nachtigall Decomposition

By Bernadette Charron-Bost, Thomas Nowak

We present general transience bounds in tropical linear algebra based on Nachtigall's matrix decomposition. Our approach is also applicable to reducible matrices. The core technical novelty are general bounds on the transient of the maximum of two eventually periodic sequences. Our proof is algebraic in nature, in contrast to the existing purely graph-theoretic approaches.