×

Max-algebraic attraction cones of nonnegative irreducible matrices. (English) Zbl 1226.15017

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.

MSC:

15A80 Max-plus and related algebras
15A06 Linear equations (linear algebraic aspects)
15A23 Factorization of matrices
65F30 Other matrix algorithms (MSC2010)
65Y20 Complexity and performance of numerical algorithms
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afriat, S. N., The system of inequalities \(ars > xr - xs\), Proc. Cambridge Philos. Soc., 59, 125-133 (1963) · Zbl 0118.14901
[2] M. Akian, R. Bapat, S. Gaubert, Min-plus methods in eigenvalue perturbation theory and generalized Lidskiı˘-Višik-Ljusternik theorem, 2004-2006 (E-print arXiv:math/0402090v3).; M. Akian, R. Bapat, S. Gaubert, Min-plus methods in eigenvalue perturbation theory and generalized Lidskiı˘-Višik-Ljusternik theorem, 2004-2006 (E-print arXiv:math/0402090v3).
[3] X. Allamigeon, S. Gaubert, E. Goubault, The tropical double description method, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science 2010, Nancy, France (STACS’2010), pp. 47-58. E-print arXiv:1001.4119.; X. Allamigeon, S. Gaubert, E. Goubault, The tropical double description method, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science 2010, Nancy, France (STACS’2010), pp. 47-58. E-print arXiv:1001.4119. · Zbl 1230.52024
[4] Baccelli, F. L.; Cohen, G.; Olsder, G. J.; Quadrat, J. P., Synchronization and Linearity: An Algebra for Discrete Event Systems (1992), Wiley
[5] Balcer, Y.; Veinott, A. F., Computing a graph’s period quadratically by node condensation, Discrete Math., 4, 295-303 (1973) · Zbl 0258.05114
[6] J.G. Braker, Algorithms and Applications in Timed Discrete Event Systems, Ph.D. Thesis, Delft Univ. of Technology, The Netherlands, 1993.; J.G. Braker, Algorithms and Applications in Timed Discrete Event Systems, Ph.D. Thesis, Delft Univ. of Technology, The Netherlands, 1993.
[7] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge Univ. Press · Zbl 0746.05002
[8] Butkovič, P., Max-linear Systems: Theory and Algorithms (2010), Springer · Zbl 1202.15032
[9] Butkovič, P.; Cuninghame-Green, R. A., On matrix powers in max-algebra, Linear Algebra Appl., 421, 370-381 (2007) · Zbl 1131.15008
[10] Butkovič, P.; Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonom.-Mat. Obzornik (Prague), 20, 2, 203-215 (1984)
[11] Butkovič, P.; Schneider, H.; Sergeev, S., Generators, extremals and bases of max cones, Linear Algebra Appl., 421, 394-406 (2007) · Zbl 1119.15018
[12] Butkovič, P.; Schneider, H., Applications of max-algebra to diagonal scaling of matrices, Electron. J. Linear Algebra, 13, 262-273 (2005) · Zbl 1093.15009
[13] P. Butkovič, H. Schneider, On the Visualisation Scaling of Matrices, University of Birmingham, 2007 (preprint 2007/12).; P. Butkovič, H. Schneider, On the Visualisation Scaling of Matrices, University of Birmingham, 2007 (preprint 2007/12).
[14] Carré, B. A., An algebra for network routing problems, J. Inst. Math. Appl., 7 (1971) · Zbl 0219.90020
[15] J. Cochet-Terrasson, G. Cohen, S. Gaubert, M.M. Gettrick, J.P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: Proceedings of the IFAC Conference on Systems Structure and Control, IRCT, Nantes, France, 1998, pp. 699-706.; J. Cochet-Terrasson, G. Cohen, S. Gaubert, M.M. Gettrick, J.P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: Proceedings of the IFAC Conference on Systems Structure and Control, IRCT, Nantes, France, 1998, pp. 699-706.
[16] Cochet-Terrasson, J.; Gaubert, S.; Gunawardena, J., A constructive fixed-point theorem for min-max functions, Dyn. Stab. Syst., 14, 4, 407-433 (1999) · Zbl 0958.47028
[17] G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, Analyse du comportement périodique de systèmes de production par la théorie des dioı¨des, INRIA, Rapport de Recherche No. 191, Février, 1983.; G. Cohen, D. Dubois, J.P. Quadrat, M. Viot, Analyse du comportement périodique de systèmes de production par la théorie des dioı¨des, INRIA, Rapport de Recherche No. 191, Février, 1983.
[18] Cohen, G.; Dubois, D.; Quadrat, J. P.; Viot, M., A linear system theoretic view of discrete event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control, AC-30, 210-220 (1985) · Zbl 0557.93005
[19] Cuninghame-Green, R. A., Minimax Algebra, vol. 166: Lecture Notes in Economics and Mathematical Systems (1979), Springer: Springer Berlin
[20] de Schutter, B., On the ultimate behavior of the sequence of consecutive powers of a matrix in the max-plus algebra, Linear Algebra Appl., 307, 103-117 (2000) · Zbl 0999.15020
[21] T. Dokka, On the Reachability of Max-plus Eigenspaces, Master’s Thesis, University of Birmingham, UK, 2008.; T. Dokka, On the Reachability of Max-plus Eigenspaces, Master’s Thesis, University of Birmingham, UK, 2008.
[22] Elsner, L.; van den Driessche, P., On the power method in max algebra, Linear Algebra Appl., 302-303, 17-32 (1999) · Zbl 0949.65032
[23] Elsner, L.; van den Driessche, P., Modifying the power method in max algebra, Linear Algebra Appl., 332-334, 3-13 (2001) · Zbl 0982.65042
[24] Engel, G. M.; Schneider, H., Cyclic and diagonal products on a matrix, Linear Algebra Appl., 7, 301-335 (1973) · Zbl 0289.15006
[25] Engel, G. M.; Schneider, H., Diagonal similarity and diagonal equivalence for matrices over groups with 0, Czechoslovak Math. J., 25, 100, 387-403 (1975) · Zbl 0329.15007
[26] Fiedler, M.; Pták, V., Diagonally dominant matrices, Czechoslovak Math. J., 17, 92, 420-433 (1967) · Zbl 0178.03402
[27] S. Gaubert, R.D. Katz, The Minkowski theorem for max-plus convex sets, Linear Algebra Appl. 421(2-3) (2007) 356-369 (E-print arXiv:math.GM/0605078).; S. Gaubert, R.D. Katz, The Minkowski theorem for max-plus convex sets, Linear Algebra Appl. 421(2-3) (2007) 356-369 (E-print arXiv:math.GM/0605078). · Zbl 1110.52002
[28] Gavalec, M., Linear matrix period in max-plus algebra, Linear Algebra Appl., 307, 167-182 (2000) · Zbl 0998.15020
[29] M. Gavalec, Periodicity in Extremal Algebra, Gaudeamus, Hradec Králové, 2004.; M. Gavalec, Periodicity in Extremal Algebra, Gaudeamus, Hradec Králové, 2004.
[30] Gondran, M.; Minoux, M., Valeurs propres et vecteurs propres dans les dioı¨des, EDF Bulletin de la Direction des Etudes et Recherches. Ser. Informat. et Math. Appl., 2, 25-41 (1977)
[31] Gondran, M.; Minoux, M., Graphs, Dioids and Semirings: New Applications and Algorithms (2008), Springer · Zbl 1201.16038
[32] Heidergott, B.; Olsder, G.-J.; van der Woude, J., Max-plus at Work (2005), Princeton Univ. Press
[33] Kim, K. H., Boolean Matrix Theory and Applications (1982), Marcel Dekker: Marcel Dekker New York
[34] Mairesse, J., A graphical approach of the spectral theory in the \((\max, +)\) algebra, IEEE Trans. Automat. Control, 40, 10, 1783-1789 (1995) · Zbl 0845.93036
[35] Merlet, G., Semigroup of matrices acting on the max-plus projective space, Linear Algebra Appl., 432, 8, 1923-1935 (2010) · Zbl 1189.15020
[36] Molnárová, M., Generalized matrix period in max-plus algebra, Linear Algebra Appl., 404, 345-366 (2005) · Zbl 1077.15012
[37] Molnárová, M.; Pribiš, J., Matrix period in max-algebra, Discrete Appl. Math., 103, 167-175 (2000) · Zbl 0952.05043
[38] Rothblum, U. G.; Schneider, H.; Schneider, M. H., Scaling matrices to prescribed row and column maxima, SIAM J. Matrix Anal. Appl., 15, 1-14 (1994) · Zbl 0833.15006
[39] Schneider, H.; Schneider, M. H., Max-balancing weighted directed graphs, Math. Oper. Res., 16, 208-222 (1991) · Zbl 0729.90085
[40] Semančı´ková, B., Orbits in max-min algebra, Linear Algebra Appl., 414, 38-63 (2006) · Zbl 1125.15020
[41] Semančı´ková, B., Orbits and critical components of matrices in max-min algebra, Linear Algebra Appl., 426, 415-447 (2007) · Zbl 1128.15008
[42] Sergeev, S., Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes, Linear Algebra Appl., 431, 6, 1325-1339 (2009) · Zbl 1175.15027
[43] S. Sergeev, H. Schneider, CSR expansions of matrix powers in max algebra, 2009 (E-print arxiv:0912.2534).; S. Sergeev, H. Schneider, CSR expansions of matrix powers in max algebra, 2009 (E-print arxiv:0912.2534).
[44] S. Sergeev, H. Schneider, P. Butkovič, On visualization scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra Appl. 431(12) (2009) 2395-2406 (E-print arxiv:0808.1992).; S. Sergeev, H. Schneider, P. Butkovič, On visualization scaling, subeigenvectors and Kleene stars in max algebra, Linear Algebra Appl. 431(12) (2009) 2395-2406 (E-print arxiv:0808.1992).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.