An algorithm to describe the solution set of any tropical linear system $A\odot x=B\odot x$
Lorenzo Garcia, Elisa ; de la Puente, Maria Jesus
HAL, hal-01619443 / Harvested from HAL
An algorithm to give an explicit description of all the solutions to any tropical linear system $A\odot x=B\odot 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.
Publié le : 2011-07-04
Classification:  Algorithm,  Tropical linear system,  15-04, 15A06, 15A39,  [MATH.MATH-RA]Mathematics [math]/Rings and Algebras [math.RA]
@article{hal-01619443,
     author = {Lorenzo Garcia, Elisa and de la Puente, Maria Jesus},
     title = {An algorithm to describe the solution set of any tropical linear system $A\odot x=B\odot x$},
     journal = {HAL},
     volume = {2011},
     number = {0},
     year = {2011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01619443}
}
Lorenzo Garcia, Elisa; de la Puente, Maria Jesus. An algorithm to describe the solution set of any tropical linear system $A\odot x=B\odot x$. HAL, Tome 2011 (2011) no. 0, . http://gdmltest.u-ga.fr/item/hal-01619443/