Max-linear systems. Theory and algorithms.

*(English)*Zbl 1202.15032
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.

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 |