CSR expansions of matrix powers in max algebra
From MaRDI portal
Publication:2844737
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.
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
Cites work
- scientific article; zbMATH DE number 3779513 (Why is no real title available?)
- scientific article; zbMATH DE number 627763 (Why is no real title available?)
- A constructive fixed point theorem for min-max functions
- Combinatorial matrix theory
- Computational Complexity of Nachtigall's Representation
- Computing a graph's period quadratically by node condensation
- Cyclic and diagonal products on a matrix
- Diagonally dominant matrices
- Generalized matrix period in max-plus algebra
- Linear matrix period in max-plus algebra
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Max-algebra: The linear algebra of combinatorics?
- Max-linear systems. Theory and algorithms.
- Minimax algebra
- Modifying the power method in max algebra
- On a sharp estimation in the theory of binary relations on a finite set
- On the power method in max 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
- Orbits and critical components of matrices in max-min algebra
- Orbits in max--min algebra
- Powers of matrices over an extremal algebra with applications to periodic graphs
- Reducible spectral theory with applications to the robustness of matrices in max-algebra
- Unzerlegbare, nicht negative Matrizen
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
- scientific article; zbMATH DE number 7670358 (Why is no real title available?)
- 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)
