An algorithm to describe the solution set of any tropical linear system $A\odot x=B\odot x$

Abstract

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.

24 pages, no pictures. The third version slightly improves the second one; one example is made in great detail; some bibliographic items added; some tedious (not too interesting computations found in earlier versions) have been removed