Generators, extremals and bases of max cones

Abstract

Max cones are max-algebraic analogs of convex cones. In the present paper we develop a theory of generating sets and extremals of max cones in ${\mathbb{R}}_{+}^n$. This theory is based on the observation that extremals are minimal elements of max cones under suitable scalings of vectors. We give new proofs of existing results suitably generalizing, restating and refining them. Of these, it is important that any set of generators may be partitioned into the set of extremals and the set of redundant elements. We include results on properties of open and closed cones, on properties of totally dependent sets and on computational bounds for the problem of finding the (essentially unique) basis of a finitely generated cone.

15 pages, 1 figure; v2: new layout, several new references, renumbering of results

References in corpus (2)

• The Minkowski Theorem for Max-plus Convex Sets
• Max-plus definite matrix closures and their eigenspaces

Cited by in corpus (34)

• Tropical polyhedra are equivalent to mean payoff games
• The Minkowski Theorem for Max-plus Convex Sets
• On visualisation scaling, subeigenvectors and Kleene stars in max algebra
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Minimal half-spaces and external representation of tropical polyhedra
• The number of extreme points of tropical polyhedra
• Tropical matrix duality and Green's D relation
• The tropical analogue of polar cones
• Pure Dimension and Projectivity of Tropical Polytopes
• The tropical double description method
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Tropical linear algebra with the Lukasiewicz T-norm
• Two cores of a nonnegative matrix
• On tropical Kleene star matrices and alcoved polytopes
• Cyclic projectors and separation theorems in idempotent convex geometry
• Characterization of tropical hemispaces by (P,R)-decompositions
• Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
• Basic solutions of systems with two max-linear inequalities
• X-simple image eigencones of tropical matrices
• Six combinatorial clases of maximal convex tropical polyhedra
• On $2\times 2$ Tropical Commuting Matrices
• Quasi--Euclidean classification of Alcoved Convex Polyhedra
• Tropical Gaussians: A Brief Survey
• On common eigenvectors for semigroups of matrices in tropical and traditional mathematics
• Cyclic classes and attraction cones in max algebra
• Idempotent tropical matrices and finite metric spaces
• Signed tropical convexity
• On the max-algebraic core of a nonnegative matrix
• Independence and orthogonality of algebraic eigenvectors over the max-plus algebra
• An algorithm for finding the scaled basis of the supereigenvector space in max-plus algebra
• On max-plus two-sided linear systems whose solution sets are min-plus linear
• Matrices commuting with a given normal tropical matrix
• Extremals of the supereigenvector cone in max algebra: a combinatorial description