Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes

Research output: Contribution to journalArticle

16 Citations (Scopus)

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 X-1 AX, called visualization scaling, and to study the role of cyclic classes of the critical graph. (C) 2009 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)1325-1339
Number of pages15
JournalLinear Algebra and its Applications
Volume431
Issue number8
DOIs
Publication statusPublished - 1 Sep 2009

Keywords

  • Max-plus 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.

Cite this