An algorithm to describe the solution set of any tropical linear system A circle dot x = B circle dot x

作者：Lorenzo E; de la Puente M J^*

来源：Linear Algebra and Its Applications, 2011, 435(4): 884-901.

DOI：10.1016/j.laa.2011.02.014

• Tropical linear system
• Algorithm

An algorithm to give an explicit description of all the solutions to any tropical linear system A circle dot x = B circle dot x is presented. The given system is converted into a finite (rather small) number p of pairs (S, T) of classical linear systems: a system S of equations and a system T of inequalities. The notion, introduced here, that makes p small, is called compatibility. The particular feature of both S and T is that each item (equation or inequality) is bivariate, i.e., it involves exactly two variables; one variable with coefficient 1 and the other one with -1. S is solved by Gaussian elimination. We explain how to solve T by a method similar to Gaussian elimination. To achieve this, we introduce the notion of sub-special matrix. The procedure applied to T is, therefore, called sub-specialization.

• 出版日期2011-8-15