Cyclic classes and attraction cones in max algebra - Mathematics > Rings and AlgebrasReportar como inadecuado

Cyclic classes and attraction cones in max algebra - Mathematics > Rings and Algebras - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In max algebra it is well-known that the sequence A^k, with A an irreduciblesquare matrix, becomes periodic at sufficiently large k. This raises a numberof 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 cones in max algebra, by which wemean sets of vectors whose ultimate orbit period does not exceed a givennumber. This paper shows that some of these questions can be solved by matrixsquaring A,A^2,A^4,

., analogously to recent findings concerning the orbitperiod in max-min algebra. Hence the computational complexity of such problemsis of the order On^3 log n. The main idea is to apply an appropriate diagonalsimilarity scaling A -> X^{-1}AX, called visualization scaling, and to studythe role of cyclic classes of the critical graph. For powers of a visualizedmatrix in the periodic regime, we observe remarkable symmetry described bycirculants and their rectangular generalizations. We exploit this symmetry toderive a concise system of equations for attraction cpne, and we present analgorithm which computes the coefficients of the system.

Autor: Sergei Sergeev


Documentos relacionados