×

On the rank of a tropical matrix. (English) Zbl 1095.15001

Goodman, Jacob Eli (ed.) et al., Combinatorial and computational geometry. Cambridge: Cambridge University Press (ISBN 0-521-84862-8/hbk). Mathematical Sciences Research Institute Publications 52, 213-242 (2005).
Three natural definitions of the rank of a matrix are given and compared in the case of matrices over the tropical semiring \((\mathbb{R}, \oplus, \odot)\), where \(a\oplus b:=\min (a,b)\) and \(a\odot b:=a+b\). The Barvinok rank of a matrix \(M\in\mathbb{R}^{d\times n}\) is the smallest integer \(r\) for which \(M\) can be written as the tropical sum of \(r\) matrices, each of them being the tropical product of a \(d\times1\) matrix and an \(1\times n\) matrix. The Kapranov rank of \(M\) is the smallest dimension of any tropical linear space containing the columns of \(M\) and the tropical rank of \(M\) is the largest integer \(r\) such that \(M\) has a nonsingular \(r\times r\) minor.
These notions are examined in detail and some equivalent characterizations are proved. It is emphasized that the Barvinok rank arises in the context of combinatorial optimization, the Kapranov rank is the most natural one from the point of view of algebraic geometry, while the tropical rank is the best notion from a geometric and combinatorial perspective. The main theorem shows that \[ \text{tropical rank}(m)\leq \text{Kapranov rank} (M)\leq \text{Barvinok rank} (M) \] and these inequalities can be strict. Two cases when the Kapranov and tropical ranks agree are studied. A theorem about tropical representations of matroids is given. In the final section some related results from literature are discussed and a list of open questions is presented.
For the entire collection see [Zbl 1076.51500].

MSC:

15A03 Vector spaces, linear dependence, rank, lineability
15B57 Hermitian, skew-Hermitian, and related matrices
15A45 Miscellaneous inequalities involving matrices
90C27 Combinatorial optimization
05B35 Combinatorial aspects of matroids and geometric lattices
15B33 Matrices over special rings (quaternions, finite fields, etc.)
PDF BibTeX XML Cite
Full Text: arXiv Link