Solving linear equations over maxmin-ω systems

Maxmin-omega dynamical systems were previously introduced as an all-in-one package that can yield a solely min-plus, a solely max-plus, or a max-min-plus dynamical system by varying a parameter omega is an element of (0,1]. With such systems in mind, it is natural to introduce and consider maxmin-omega linear systems of equations of the type A circle times(omega) x = b. However, to our knowledge, such maxmin-omega linear systems have not been studied before and in this paper we present an approach to solve them. We show that the problem can be simplified by performing normalization and then generating a canonical matrix which we call the principal order matrix. Instead of directly trying to find the solutions, we search the possible solution indices which can be identified using the principal order matrix and the parameter omega. The fully active solutions are then immediately obtained from these solution indices. With the fully active solutions at hand, we then present the method to find other solutions by applying a relaxation, i.e., increasing or decreasing some components of fully active solutions. This approach can be seen as a generalization of an approach that could be applied to solve max-plus or min-plus linear systems. Our results also shed more light on an unusual feature of maxmin-omega linear systems, which, unlike in the usual linear algebra, can have a finite number of solutions in the case where their solution is non-unique.(c) 2023 Elsevier Inc. All rights reserved.

Automated summary

This paper presents an approach to solve maxmin-omega linear systems by performing normalization and generating a principal order matrix. The possible solution indices can be identified using the principal order matrix and the parameter omega, and the fully active solutions can be obtained from these indices. Other solutions can be found by applying a relaxation to the fully active solutions. This approach can be seen as a generalization of solving max-plus or min-plus linear systems. The paper also highlights the unusual feature of maxmin-omega linear systems having a finite number of solutions when the solution is non-unique.