New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank

DOI10.1016/J.LAA.2020.10.032zbMATH Open1458.15046arXiv2005.05390OpenAlexW3095061826MaRDI QIDQ2228503FDOQ2228503

Authors: Arthur Kennedy-Cochran-Patrick, Glenn Merlet, Thomas Nowak, Sergey M. Sergeev 

Publication date: 17 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Building on the weak CSR approach developed in a previous paper by Merlet, Nowak and Sergeev, 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 Gregory-Kirkland-Pullman, 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.

Full work available at URL: https://arxiv.org/abs/2005.05390

Recommendations

• On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
• Weak CSR expansions and transience bounds in max-plus algebra
• Bounds for the completely positive rank of a symmetric matrix over a tropical semiring
• The ultimate rank of tropical matrices
• CSR expansions of matrix powers in max algebra

zbMATH Keywords

transientdigraphsmax-plus algebraperiodicitymatrix powers

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Factorization of matrices (15A23) Miscellaneous inequalities involving matrices (15A45) Max-plus and related algebras (15A80) Foundations of tropical geometry and relations with algebra (14T10)

Cites Work

• Max-linear systems. Theory and algorithms.
• Linear independence over tropical semirings and beyond
• Combinatorial matrix theory
• Max-Balancing Weighted Directed Graphs and Matrix Scaling
• Title not available (Why is that?)
• Title not available (Why is that?)
• Unzerlegbare, nicht negative Matrizen
• An extension of the Dulmage-Mendelsohn theorem
• Gaps in the exponent set of primitive matrices
• Powers of matrices over an extremal algebra with applications to periodic graphs
• Transience bounds for long walks
• CSR expansions of matrix powers in max algebra
• Weak CSR expansions and transience bounds in max-plus algebra
• Title not available (Why is that?)
• New transience bounds for max-plus linear systems
• On a sharp estimation in the theory of binary relations on a finite set
• Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
• A bound on the exponent of a primitive matrix using Boolean rank
• Generalizations of bounds on the index of convergence to weighted digraphs
• On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

Cited In (6)

• Linear transformations of tropical matrices preserving the cyclicity index
• Weak CSR expansions and transience bounds in max-plus algebra
• Title not available (Why is that?)
• Linear Transformations Preserving the Minimal Values of the Cyclicity Index of Tropical Matrices
• On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
• Non-surjective linear transformations of tropical matrices preserving the cyclicity index

This page was built for publication: New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228503)