We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvatal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with
similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.
This paper studies commuting matrices in max algebra and nonnegative linear algebra. Our starting point is the existence of a common eigenvector, which directly leads to max analogues of some classical results for complex matrices. We also investigat
e Frobenius normal forms of commuting matrices, particularly when the Perron roots of the components are distinct. For the case of max algebra, we show how the intersection of eigencones of commuting matrices can be described, and we consider connections with Boolean algebra which enables us to prove that two commuting irreducible matrices in max algebra have a common eigennode.
We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which app
eared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.
We study the max-plus or tropical analogue of the notion of polar: the polar of a cone represents the set of linear inequalities satisfied by its elements. We establish an analogue of the bipolar theorem, which characterizes all the inequalities sati
sfied by the elements of a tropical convex cone. We derive this characterization from a new separation theorem. We also establish variants of these results concerning systems of linear equalities.
