A method to find all solutions of a system of multivariate polynomial equalities and inequalities in the max algebra (Q1916031)

In this well-written paper, systems of multivariate polynomial equalities and inequalities in the max-plus algebra are considered. This max-plus algebra is different from the conventional ``plus-times'' algebra in the sense that addition is replaced by maximization and multiplication by addition. The authors show that finding solutions of such a system is equivalent to solving an Extended Linear Complementary Problem (ELCP). This ELCP is an extension of the well-known Linear Complementary Problem. Various problems in the max-plus algebra, or min-max-plus algebra, can be transformed into the problem of finding a solution of such a system of multivariate polynomial equalities and inequalities and hence into an ELCP. The paper starts with a brief introduction in, and overview of, the max-plus algebra and the ELCP. A geometrical insight in the structure of the solution set (which may be empty) is given. The following problems/applications are dealt with in this set-up: -- Matrix decompositions. If \(A\) is an \(m\times n\) matrix in the max-plus algebra, find \(B\) and \(C\), of sizes \(m\times p\) and \(p\times n\) respectively such that \(A = B\otimes C\) (\(p\) is given); or show that no such \(B\) and \(C\) exist. -- Transformation of state space models. Linear models of different dimension may have the same input-output behaviour. -- State space realization of minimal dimension. Essentially one starts with a trial dimension of the state space. If a solution to an appropriate ELCP exists (does not exist) try a smaller (larger) dimension. -- Construction of matrices with a given characteristic polynomial. -- Min-max-plus problems. In the conclusion, the authors express their concern about large computation times and storage requirements if the number of variables and equations and/or inequalities is large.