On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra
type: Item
instance of: scholarly article
title: On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra
zbMATH Open document ID: 0999.15020
DOI: 10.1016/S0024-3795(00)00013-6
published in: Linear Algebra and its Applications
publication date: 2002-11-28T00:00:00Z
review text: A max-plus algebra is defined on \(\mathbb{R}_{\varepsilon}:=\mathbb{R\cup \{-\infty\}}\) by introducing two new operations: \(x\oplus y:=\max(x,y)\) and \(x\otimes y:=x+y\). The identity for \(\oplus\) is \(\varepsilon:=-\infty\), and the identity for \(\otimes\) is \(0\). Using these new operations we can define a matrix addition and multiplication in \(\mathbb{R}^{n\times n}\) (also denoted by \(\oplus\) and \(\otimes\)) where the ``zero'' is the matrix with all entries \(\varepsilon\) and the ``identity'' is the matrix with \(0's\) on the diagonal and \(\varepsilon's\) elsewhere. These algebras arise in the modelling of discrete event systems. The author is interested in investigating the sequence \(\{A^{\otimes^{k}}\}\) of successive \(\otimes \)-powers of a matrix \(A\) in \(\mathbb{R}^{n\times n}\). An unpublished result of S. Gaubert shows that if \(A\) is irreducible, then this series is eventually geometric (recall that a matrix \(A\in\mathbb{R}^{n\times n}\) is called irreducible if the graph of the corresponding adjacency matrix is strongly connected). More precisely, there exists \(\lambda\in\mathbb{R}_{\varepsilon }\) such that for all large \(k\): \(A^{\otimes^{k+c}}=\lambda^{\otimes^{c} }\otimes A^{\otimes^{k}}=(c\lambda)\otimes A^{\otimes^{k}}\) where \(c\) is the cyclicity of the graph. The present paper extends and corrects earlier work [see \textit{M. Wang, Y. Li} and \textit{H. Liu}, ``On periodicity analysis and eigen-problem of matrix in max-algebra'' in Proc. IFAC Workshop on Discrete Event System Theory and Applications to Manufacturing and Social Phenomena, Shenyang, China, June 1991, pp. 44-48 (1991)] and gives a complete description of the ultimate behaviour of \(\{A^{\otimes^{k}}\}\) in the general case. In particular, it shows that this series need not be ultimately geometric when \(A\) is reducible.
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 15A30
Mathematics Subject Classification ID: 15A78
zbMATH DE Number: 1441334
zbMATH Keywords: sequence of consecutive powers
zbMATH Keywords: irreducible matrix
zbMATH Keywords: max-plus algebra
zbMATH Keywords: discrete event systems
author: Bart De Schutter
describes a project that uses: UMDES
MaRDI profile type: Publication
cites work: Q4304869
cites work: A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring
cites work: Combinatorial matrix theory
cites work: A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
cites work: Minimax algebra
cites work: Q4763580
cites work: A graph theoretic approach to matrix inversion by partitioning
cites work: Q3907580
Wikidata QID: Q127725631
description: scientific article; zbMATH DE number 1441334