2003/12/31 by M. Develin, F. Santos, B. Sturmfels
Mathematics · #math.CO #math.AG #msc:15A33 #msc:15A03 #msc:52A30
published as In "Discrete and Computational Geometry" (E. Goodman, J. Pach and E. Welzl, eds), MSRI Publications, Cambridge Univ. Press, 2005. ISBN-10: 0521848628 · 20 pages, 1 figure
arxiv created 2004/05/23 · arxiv updated 2009/12/01
This is a foundational paper in tropical linear algebra, which is linear algebra over the min-plus semiring. We introduce and compare three natural definitions of the rank of a matrix, called the Barvinok rank, the Kapranov rank and the tropical rank. We demonstrate how these notions arise naturally in polyhedral and algebraic geometry, and we show that they differ in general. Realizability of matroids plays a crucial role here. Connections to optimization are also discussed.