CSR expansions of matrix powers in max algebra
From MaRDI portal
Publication:2844737
DOI10.1090/S0002-9947-2012-05605-4zbMATH Open1307.15036arXiv0912.2534OpenAlexW2082297369MaRDI QIDQ2844737FDOQ2844737
Authors: Hans Schneider, Sergey M. Sergeev 
Publication date: 19 August 2013
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Abstract: We study the behavior of max-algebraic powers of a reducible nonnegative n by n matrix A. We show that for t>3n^2, the powers A^t can be expanded in max-algebraic powers of the form CS^tR, where C and R are extracted from columns and rows of certain Kleene stars and S is diadonally similar to a Boolean matrix. We study the properties of individual terms and show that all terms, for a given t>3n^2, can be found in O(n^4 log n) operations. We show that the powers have a well-defined ultimate behavior, where certain terms are totally or partially suppressed, thus leading to ultimate CS^tR terms and the corresponding ultimate expansion. We apply this expansion to the question whether {A^ty, t>0} is ultimately linear periodic for each starting vector y, showing that this question can be also answered in O(n^4 log n) time. We give examples illustrating our main results.
Full work available at URL: https://arxiv.org/abs/0912.2534
Recommendations
- On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra
- A note on the sequence of consecutive powers of a nonnegative matrix in max algebra
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Weak CSR expansions and transience bounds in max-plus algebra
- On matrix powers in max-algebra
Factorization of matrices (15A23) Canonical forms, reductions, classification (15A21) Max-plus and related algebras (15A80)
Cites Work
- Title not available (Why is that?)
- Max-linear systems. Theory and algorithms.
- Title not available (Why is that?)
- Combinatorial matrix theory
- Minimax algebra
- On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra
- On visualization scaling, subeigenvectors and Kleene stars in max algebra
- Cyclic and diagonal products on a matrix
- Max-algebra: The linear algebra of combinatorics?
- On the power method in max algebra
- Reducible spectral theory with applications to the robustness of matrices in max-algebra
- Generalized matrix period in max-plus algebra
- Orbits in max--min algebra
- Unzerlegbare, nicht negative Matrizen
- A constructive fixed point theorem for min-max functions
- Powers of matrices over an extremal algebra with applications to periodic graphs
- Computational Complexity of Nachtigall's Representation
- Diagonally dominant matrices
- Modifying the power method in max algebra
- Linear matrix period in max-plus algebra
- Computing a graph's period quadratically by node condensation
- 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
- Orbits and critical components of matrices in max-min algebra
Cited In (18)
- Weak CSR expansions and transience bounds in max-plus algebra
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Fiedler-Pták scaling in max algebra
- Title not available (Why is that?)
- New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
- On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs
- Max-algebraic attraction cones of nonnegative irreducible matrices
- Tropical halfspaces
- Generalizations of bounds on the index of convergence to weighted digraphs
- The geometric structure of max-plus hemispaces
- Tropical linear algebra with the Łukasiewicz t-norm
- Computing transience bounds of emergency call centers: a hierarchical timed Petri net approach
- On the max-algebraic core of a nonnegative matrix
- Max-plus automata
- The ultimate rank 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
- Two cores of a nonnegative matrix
- On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
This page was built for publication: CSR expansions of matrix powers in max algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2844737)
