  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.
