Projects per year
Abstract
In max algebra it is well known that the sequence of max algebraic powers A(k), with A an irreducible square matrix, becomes periodic after a finite transient time T(A), and the ultimate period gamma is equal to the cyclicity of the critical graph of A.
In this connection, we study computational complexity of the following problems: (1) for a given k, compute a periodic power A(r) with r equivalent to k(mod gamma) and r >= T(A), (2) for a given x, find the ultimate period of {A' circle times x}. We show that both problems can be solved by matrix squaring in O(n(3) log n) operations. The main idea is to apply an appropriate diagonal similarity scaling A bar right arrow X1 AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. (C) 2009 Elsevier Inc. All rights reserved.
Original language  English 

Pages (fromto)  13251339 
Number of pages  15 
Journal  Linear Algebra and its Applications 
Volume  431 
Issue number  8 
DOIs  
Publication status  Published  1 Sep 2009 
Keywords
 Maxplus algebra
 Tropical algebra
 Imprimitive matrix
 Cyclicity
 Diagonal similarity
Fingerprint
Dive into the research topics of 'Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes'. Together they form a unique fingerprint.Projects
 1 Finished

Feasibility and Reachability in MaxLinear Systems
Butkovic, P.
Engineering & Physical Science Research Council
1/02/08 → 30/04/11
Project: Research Councils