Basic solutions of systems with two max-linear inequalities

DOI10.1016/J.LAA.2011.02.033MaRDI QIDQ550677zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 13 July 2011

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.0758

zbMATH Keywords

basic solutionsextremal rayKleene starsmax algebramultiorder principletropical algebra

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Linear inequalities of matrices (15A39) Max-plus and related algebras (15A80)

Abstract: We give an explicit description of the basic solutions of max-linear systems with two inequalities.

Review text

Given the max-linear systems of two inequalities \(A \otimes x \leqslant B \otimes x\), the proposed procedure consists firstly in representing the set of all solutions as the union of cones generated by certain Kleene stars and then in selecting basic solutions by means of the criterion of minimality (multiorder principle). Two examples illustrate this procedure.

Recommendations

• scientific article; zbMATH DE number 5773726
• Solving systems of two-sided (max, min)-linear equations
• Solvability and its application for max-plus mixed linear inequality systems
• Systems of linear inequalities and linear optimization
• Max-min interval systems of linear equations with bounded solution
• scientific article; zbMATH DE number 1538845
• scientific article; zbMATH DE number 3847215
• scientific article; zbMATH DE number 5026402
• Simultaneous solution of linear equations and inequalities in max-algebra
• scientific article; zbMATH DE number 3609

Cites work

• A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces
• Generators, extremals and bases of max cones
• scientific article; zbMATH DE number 3869093 (Why is no real title available?)
• Max-plus convex sets and max-plus semispaces. II
• Moduloïds and pseudomodules. I: Dimension theory
• Multiorder, Kleene stars and cyclic projectors in the geometry of max cones
• The Minkowski theorem for max-plus convex sets
• The tropical double description method
• Tropical cones defined by max-linear inequalities
• Tropical convexity
• Tropical linear maps on the plane

Cited in

(10)

• On \(2 \times 2\) tropical commuting matrices
• Weakly linear systems for matrices over the max-plus quantale
• An improved algorithm for finding the generators of the solution space for \(A\otimes \mathbf{x}\ge \mathbf{x} \)
• Complete solution of tropical vector inequalities using matrix sparsification.
• Tropical cones defined by max-linear inequalities
• scientific article; zbMATH DE number 5773726 (Why is no real title available?)
• The generators of the solution space for a system of inequalities
• An algorithm to describe the solution set of any tropical linear system A x = B x
• On max-plus two-sided linear systems whose solution sets are min-plus linear
• Solving two-sided system of equations in max-plus algebra

This page was built for publication: Basic solutions of systems with two max-linear inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550677)