Max-algebraic attraction cones of nonnegative irreducible matrices
type: Item
instance of: scholarly article
title: Max-algebraic attraction cones of nonnegative irreducible matrices
zbMATH Open document ID: 1226.15017
author: Yong-Cai Geng
author: Sumit K. Garg
published in: Linear Algebra and its Applications
publication date: 2011-07-13T00:00:00Z
review text: The max-algebraic cyclicity theorem states that if \(A\in {\mathbb R}^{n\times n}_+\) is irreducible and its maximal cyclic geometric mean \(\lambda(A)\) equals 1 then the sequence of max-algebraic powers \(A^k\) becomes periodic after some finite transient time \(T(A)\) and that the ultimate period of \(A^K\) is equal to the cyclicity of the critical graph. The cyclicity theorem naturally leads to the concept of attraction cone \(\mathrm{Attr}(A,T)\) which is the solution set of a two-sided system \(\lambda^t (A) A^r \otimes x=A^{r+y}\otimes x\) for any \(r\geq T(A)\). The author finds a complete description of \(\mathrm{Attr}(A,t)\) by a concise system of equations without knowing \(T(A)\). In addition the extremals of such attraction cones are investigated and the computational complexity for finding the coefficients of the system describing the attraction cones is examined.
Mathematics Subject Classification ID: 15A80
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 15A23
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5919622
zbMATH Keywords: max-plus algebra
zbMATH Keywords: tropical algebra
zbMATH Keywords: diagonal similarity
zbMATH Keywords: cyclicity
zbMATH Keywords: imprimitive matrix
zbMATH Keywords: irreducible
zbMATH Keywords: cyclic geometric mean
zbMATH Keywords: critical graph
zbMATH Keywords: attraction cone
zbMATH Keywords: computational complexity
reviewed by: Alexander Guterman
MaRDI profile type: Publication
full work available at URL: j.laa.2011.02.038
OpenAlex ID: W1975343887
cites work: Q5728868
cites work: Q3113735
cites work: Q4304869
cites work: Computing a graph's period quadratically by node condensation
cites work: Combinatorial matrix theory
cites work: Max-linear Systems: Theory and Algorithms
cites work: On matrix powers in max-algebra
cites work: Q3337246
cites work: Generators, extremals and bases of max cones
cites work: Applications of max algebra to diagonal scaling of matrices
cites work: An Algebra for Network Routing Problems
cites work: A constructive fixed point theorem for min-max functions
cites work: A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
cites work: Minimax algebra
cites work: On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra
cites work: On the power method in max algebra
cites work: Modifying the power method in max algebra
cites work: Cyclic and diagonal products on a matrix
cites work: Diagonal similarity and equivalence for matrices over groups with 0
cites work: Diagonally dominant matrices
cites work: The Minkowski theorem for max-plus convex sets
cites work: Linear matrix period in max-plus algebra
cites work: Graphs, dioids and semirings. New models and algorithms.
cites work: Q3958592
cites work: A graphical approach of the spectral theory in the (max,+) algebra
cites work: Semigroup of matrices acting on the max-plus projective space
cites work: Generalized matrix period in max-plus algebra
cites work: Matrix period in max-algebra
cites work: Scaling Matrices to Prescribed Row and Column Maxima
cites work: Max-Balancing Weighted Directed Graphs and Matrix Scaling
cites work: Orbits in max--min algebra
cites work: Orbits and critical components of matrices in max-min algebra
cites work: Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
cites work: On visualization scaling, subeigenvectors and Kleene stars in max algebra
DOI: 10.1016/J.LAA.2011.02.038
description: scientific article; zbMATH DE number 5919622