New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank

Arthur Kennedy-Cochran-Patrick, Glenn Merlet, Thomas Nowak, Sergei Sergeev

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
23 Downloads (Pure)

Abstract

Building on the weak CSR approach developed in a previous paper by Merlet, Nowak and Sergeev [15], we establish new bounds for the periodicity threshold of the powers of a tropical matrix. According to that approach, bounds on the ultimate periodicity threshold take the form of T = max(T1,T2), where T1  is a bound on the time after which the weak CSR expansion starts to hold and T2  is a bound on the time after which the first CSR term starts to dominate.

The new bounds on T1 and T2  established in this paper make use of the cyclicity of the associated graph and the (tropical) factor rank of the matrix, which leads to much improved bounds in favorable cases. For T1, in particular, we obtain new extensions of bounds of Schwarz, Kim and Gregory-Kirkland-Pullman, previously known as bounds on exponents of digraphs. For similar bounds on T2, we introduce the novel concept of walk reduction threshold and establish bounds on it that use both cyclicity and factor rank.
Original languageEnglish
Pages (from-to)279-309
Number of pages31
JournalLinear Algebra and its Applications
Volume611
Early online date29 Oct 2020
DOIs
Publication statusPublished - 15 Feb 2021

Keywords

  • Max-plus
  • matrix powers
  • transient
  • periodicity
  • digraphs

Fingerprint

Dive into the research topics of 'New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank'. Together they form a unique fingerprint.

Cite this