Monotone eigenspace structure in max-min algebra (Q1347952)

For a given \(n\times n\) matrix \(A\) in a max-min algebra, the set of all increasing eigenvectors, in notation \({\mathcal F}^\leq(A)\) is studied. It is shown that \({\mathcal F}^\leq(A)\) is a union of at most \(2^{n-1}\) intervals, and an explicit formula for the intervals is given. Moreover, it is shown that the endpoints of these intervals can be computed in \(O(n^2)\) time or in \(O(n)\) time, if an auxiliary \(n\times n\) matrix \(C(A)\) has been previously computed. The results enable a complete description of the structure of the whole eigenspace \({\mathcal F}(A)\).