On the ultimate behaviour of the sequence of consecutive powers of a matrix in the max-plus algebra (Q1973921)

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.