On integer eigenvectors and subeigenvectors in the max-plus algebra
type: Item
instance of: scholarly article
title: On integer eigenvectors and subeigenvectors in the max-plus algebra
zbMATH Open document ID: 1267.15023
published in: Linear Algebra and its Applications
publication date: 2013-04-12T00:00:00Z
review text: The max-plus ring consists of the extended reals \(\bar \mathbb{R}:=\) \(\left\{ -\infty\right\} \cup\mathbb{R} \) with operations \(\oplus\) and \(\otimes\) where \(a\oplus b:=\max(a,b)\) and \(a\otimes b:=a+b\) (\(-\infty\) is the zero and \(0\) is the unity element of this ring). These operations are extended to matrices in a natural way and (confusingly) the multiplication symbol \(\otimes\) will be omitted. Matrix algebras over the max-plus ring arise naturally in various combinatorial scheduling problems and other applications (see, for example [\textit{C. A. Brackley} et al., J. Theoretical Biology 303, 128 (2011)]). The authors are interested in determining when an \(n\times n\) matrix \(A=[a_{ij}]\) (over the max-plus ring) has integer eigenvectors or, more generally, integer subeigenvectors (a subeigenvector \(x\) satisfies \(Ax\leq\lambda x\) for some \(\lambda\in\) \(\bar \mathbb{R} \)). The second problem is much easier than the first, and a simple algorithm for determining whether \(A\) has an integer subeigenvector for \(\lambda\) (and, if so, describing them all) is provided. The question of integer eigenvectors is much more complicated, but the following result gives a flavour of what is proved. Associate with \(A\) a directed graph with adjacency matrix \(B:=[b_{ij}]\) where \(b_{ij}=0\) if \(a_{ij}=-\infty\) and \(b_{ij}=1\) otherwise, and call \(A\) irreducible when this graph is strongly connected. Now define \(\lambda(A):=\max(a_{i_{1}i_{2}}+\dots+a_{i_{k}i_{1}})/k\) where the maximum is over all \(k=1,\dots,n\) and all \(k\)-cycles \((i_{1},\dots,i_{k})\). Corollary 3.5: If \(A\) is irreducible and the entries of \(A\) lie in the extended integers \(\bar \mathbb{Z}:=\left\{ -\infty\right\} \cup \mathbb{Z}\), then \(A\) has an integer eigenvector if and only if \(\lambda(A)\in \mathbb{Z}\). The last two sections of the paper investigate algorithms for determining whether for a matrix \(A\) over the max-plus ring there is an integer vector \(x\)…
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 15A80
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 6153418
zbMATH Keywords: max-plus algebra
zbMATH Keywords: subeigenvector
zbMATH Keywords: integer points
zbMATH Keywords: column space
zbMATH Keywords: matrix algebras
zbMATH Keywords: max-plus ring
zbMATH Keywords: algorithm
zbMATH Keywords: integer eigenvectors
zbMATH Keywords: directed graph
zbMATH Keywords: irreducible
author: Peter Butkovič
author: Marie MacCaig
MaRDI profile type: Publication
full work available at URL: j.laa.2012.12.017
OpenAlex ID: W2080527305
cites work: Q4304869
cites work: A MAX-plus model of ribosome dynamics during mRNA translation
cites work: Max-linear Systems: Theory and Algorithms
cites work: Q3964346
cites work: Bases in max-algebra
DOI: 10.1016/J.LAA.2012.12.017
Recommended article: Q2992126
Recommended article: Eigenvectors of interval matrices over max--plus algebra
Recommended article: On Eigenproblem for Circulant Matrices in Max-Algebra
Recommended article: A generalized eigenvalue problem in the max algebra
Recommended article: Q4984008
Recommended article: EIGENVALUES AND EIGENVECTORS OF LATIN SQUARES IN MAX-PLUS ALGEBRA
Recommended article: Q3112153
Recommended article: Eigenproblem for monotone and toeplitz matrices in a Max-algebra
Recommended article: Q5490299
Recommended article: Structure of the eigenspace of a Monge matrix in max-plus algebra
description: scientific article; zbMATH DE number 6153418