The ultimate rank of tropical matrices - Université Pierre et Marie Curie
Journal Articles Journal of Algebra Year : 2015

The ultimate rank of tropical matrices

Pierre Guillon
Jean Mairesse
Glenn Merlet

Abstract

A tropical matrix is a matrix defined over the max-plus semiring. For such matrices, there exist several non-coinciding notions of rank: the row rank, the column rank, the Schein/Barvinok rank, the Kapranov rank, or the tropical rank, among others. In the present paper, we show that there exists a natural notion of ultimate rank for the powers of a tropical matrix, which does not depend on the underlying notion of rank. Furthermore, we provide a simple formula for the ultimate rank of a matrix, which can therefore be computed in polynomial time. Then we turn our attention to finitely generated semigroups of matrices, for which our notion of ultimate rank is generalized naturally. We provide both combinatorial and geometric characterizations of semigroups having maximal ultimate rank. As a consequence, we obtain a polynomial algorithm to decide if the ultimate rank of a finitely generated semigroup is maximal.
Fichier principal
Vignette du fichier
1305.4260v1.pdf (311.99 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01194760 , version 1 (21-05-2024)

Identifiers

Cite

Pierre Guillon, Zur Izhakian, Jean Mairesse, Glenn Merlet. The ultimate rank of tropical matrices. Journal of Algebra, 2015, 437, pp.222-248. ⟨10.1016/j.jalgebra.2015.02.026⟩. ⟨hal-01194760⟩
239 View
22 Download

Altmetric

Share

More