On the solvability of homogeneous two-sided systems in max-algebra
Abdulhadi Aminu · 2010
Let a b = max(a;b) and a b = a+b for a;b2 R and extend the pair of operations to matrices and vectors in the same way as in linear algebra. The homogeneous twosided system in max-algebra is of the form A x = B x. No polynomial method for solving homogeneous system is known. In this paper, we consider homogeneous twosided linear systems in max-algebra in a special case. We show that it can be checked in O(n 3 ) time whether a given two-sided homogeneous system belongs to this special case. Solvability can be decided in O(n 3 ) time and in the positive case a solution can be found in O(n 3 ).