Max-linear systems. Theory and algorithms. (English) Zbl 1202.15032

Butkovič, Peter

Springer Monographs in Mathematics. London: Springer (ISBN 978-1-84996-298-8/hbk; 978-1-4471-2583-9/pbk; 978-1-84996-299-5/ebook). xvii, 272 p. (2010).

The book is concerned with the introduction to the subject of max-plus linear algebra, and in particular algorithmic problems. It is organized in 10 chapters and a final section containing a brief summary of the book and a list of open problems.
Chapter 1 presents essential definitions, examples and basic results used throughout the book.
Chapter 2 explains two special features of max-algebra: the possibility of efficiently describing the set of all solutions to a problem, respectively, the ability to describe a class of problems in combinatorics or combinatorial optimization in algebraic terms.
Chapter 3 contains results on: a straightforward way of solving one-sided systems of equations and inequalities both algebraically and combinatorially, characterization of basses of max-algebraic subspaces and a proof that finitely generated max-algebraic subspaces have an essentially unique basis.
Chapter 4 presents the max-algebraic eigenproblem. It contains characterization and efficient methods for finding all eigenvalues and describing all eigenvectors for any square matrix. In Chapter 5 the question of factorization of max-algebraic polynomials and the characteristic max-algebraic polynomial are studied. Chapter 6 provides a unifying overview of the results published in various research papers on linear independence and simple image sets. It is proved that three types of regularity of matrices (including strong regularity and Gondran-Minoux regularity) can be checked in \({\mathcal{O}}(n^3)\) time. In Chapter 7, an account of the existing methodology for solving two-sided systems (homogeneous, nonhomogeneous, or with separated variables) is given. The main emphasized ideas are those of the alternating method and symmetrized semirings.
Chapter 8 deals with the problem of reachability of eigenspaces by matrix orbits. It is shown that matrix scaling can be useful in visualizing spectral properties of matrices. Moreover, the classical theory of the periodic behavior of matrices in max-algebra is presented and it is shown how the reachability question for irreducible matrices can be answered in polynomial time. Chapter 9 contains an account of results on the area of generalized eigenproblem, together with an algorithm for narrowing the search for generalized eigenvalues. Chapter 10 presents theoretical aspects and algorithms for solving max-linear programs subject to one or two-sided max-linear constraints (both minimization and maximization).
The book provides the fundamentals of max-algebraic theory in a comprehensive and unified form, and assumes no prior knowledge in this field. It is useful for undergraduate and postgraduate students of mathematics or a related field, mathematics researchers and mathematicians working in industry or management.

Reviewer: Constantin Popa (Constanţa)

MSC:

15A80	Max-plus and related algebras
15-02	Research exposition (monographs, survey articles) pertaining to linear algebra
90C27	Combinatorial optimization
15A18	Eigenvalues, singular values, and eigenvectors
15A06	Linear equations (linear algebraic aspects)
15A39	Linear inequalities of matrices
12D05	Polynomials in real and complex fields: factorization
15A03	Vector spaces, linear dependence, rank, lineability
16Y60	Semirings
65F15	Numerical computation of eigenvalues and eigenvectors of matrices
90C05	Linear programming

Keywords:

max-plus linear algebra; algorithmic problems; combinatorics; combinatorial optimization; max-algebraic; max-algebraic polynomials; linear independence; matrix regularity; spectral properties; max-linear programs; monograph; eigenvalues; eigenvectors; factorization of polynomials; Gondran-Minoux regularity; semirings; irreducible matrices; algorithm