On cyclic classes and attraction spaces in max algebra Export

@article{citeulike:4232858, abstract = {In max algebra it is well-known that the sequence A^k, with A an irreducible square matrix, becomes periodic at sufficiently large k. This raises a number of questions on the periodic regime of A^k and A^k x, for a given vector x. Also, this leads to the concept of attraction spaces in max algebra, by which we mean spaces of vectors with prescribed orbit period. This paper shows that some of these questions can be solved by matrix squaring (A,A^2,A^4, ...), analogously to recent findings of Semancikova concerning the orbit period in max-min algebra. Hence the computational complexity of such problems is of the order O(n^3 log n). The main idea is to apply an appropriate diagonal similarity scaling A -\> X^{-1}AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. For powers of a visualized matrix in the periodic regime, we observe remarkable symmetry described by circulants and their rectangular generalizations. We exploit this symmetry to derive a more concise system of equations for attraction space, and we present an algorithm which computes the coefficients of the system.}, archivePrefix = {arXiv}, author = {Sergeev, Sergei}, citeulike-article-id = {4232858}, citeulike-linkout-0 = {http://arxiv.org/abs/0903.3960}, citeulike-linkout-1 = {http://arxiv.org/pdf/0903.3960}, day = {25}, eprint = {0903.3960}, keywords = {tropical}, month = {Mar}, posted-at = {2009-03-27 16:23:08}, priority = {2}, title = {On cyclic classes and attraction spaces in max algebra}, url = {http://arxiv.org/abs/0903.3960}, year = {2009} }

TY - JOUR ID - citeulike:4232858 L3 - citeulike-article-id:4232858 N2 - In max algebra it is well-known that the sequence A^k, with A an irreducible square matrix, becomes periodic at sufficiently large k. This raises a number of questions on the periodic regime of A^k and A^k x, for a given vector x. Also, this leads to the concept of attraction spaces in max algebra, by which we mean spaces of vectors with prescribed orbit period. This paper shows that some of these questions can be solved by matrix squaring (A,A^2,A^4, ...), analogously to recent findings of Semancikova concerning the orbit period in max-min algebra. Hence the computational complexity of such problems is of the order O(n^3 log n). The main idea is to apply an appropriate diagonal similarity scaling A -> X^{-1}AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. For powers of a visualized matrix in the periodic regime, we observe remarkable symmetry described by circulants and their rectangular generalizations. We exploit this symmetry to derive a more concise system of equations for attraction space, and we present an algorithm which computes the coefficients of the system. TI - On cyclic classes and attraction spaces in max algebra KW - tropical AU - Sergeev, Sergei PY - 2009/Mar/25/ UR - http://arxiv.org/abs/0903.3960 ER -