On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

Glenn Merlet; Thomas Nowak; Sergei Sergeev

doi:10.1080/03081087.2021.1878995

On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

Glenn Merlet, Thomas Nowak, Sergei Sergeev

Mathematics

Research output: Contribution to journal › Article › peer-review

79 Downloads (Pure)

Abstract

We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T₁,T₂}, where T₁ is the weak CSR threshold and T₂ is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T₁ and T₂, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T₁, which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.

Original language	English
Journal	Linear and Multilinear Algebra
Early online date	3 Feb 2021
DOIs	https://doi.org/10.1080/03081087.2021.1878995
Publication status	E-pub ahead of print - 3 Feb 2021

Bibliographical note

Funding
This work was partially supported by Agence Nationale de la Recherche (ANR) Perturbations [grant number ANR-10-BLAN0106]. The work of S. Sergeev was also supported by Engineering and Physical Sciences Research Council (EPSRC) [grant number EP/P019676/1].

Keywords

15A18
15A23
90B35
Max-plus
digraphs
matrix powers
periodicity
transient

ASJC Scopus subject areas

Algebra and Number Theory

Access to Document

10.1080/03081087.2021.1878995

MerletG2021tightness
This is an Accepted Manuscript version of the following article, accepted for publication in Linear and Multilinear Algebra. Glenn Merlet, Thomas Nowak & Sergeĭ Sergeev (2021) On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers, Linear and Multilinear Algebra, DOI: 10.1080/03081087.2021.1878995. It is deposited under the terms of the Creative Commons Attribution-NonCommercial License (http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Accepted author manuscript, 412 KBLicence: Creative Commons: Attribution-NonCommercial (CC BY-NC)

Tropical Optimisation
Sergeev, S. (Principal Investigator)
Engineering & Physical Science Research Council
1/04/17 → 31/08/19
Project: Research Councils

Cite this

@article{51c91541f2da4f15b0c7ef03484691b7,

title = "On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers",

abstract = "We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T1,T2}, where T1 is the weak CSR threshold and T2 is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T1 and T2, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T1, which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.",

keywords = "15A18, 15A23, 90B35, Max-plus, digraphs, matrix powers, periodicity, transient",

author = "Glenn Merlet and Thomas Nowak and Sergei Sergeev",

note = "Funding This work was partially supported by Agence Nationale de la Recherche (ANR) Perturbations [grant number ANR-10-BLAN0106]. The work of S. Sergeev was also supported by Engineering and Physical Sciences Research Council (EPSRC) [grant number EP/P019676/1].",

year = "2021",

month = feb,

day = "3",

doi = "10.1080/03081087.2021.1878995",

language = "English",

journal = "Linear and Multilinear Algebra",

issn = "0308-1087",

publisher = "Taylor & Francis",

}

TY - JOUR

T1 - On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

AU - Merlet, Glenn

AU - Nowak, Thomas

AU - Sergeev, Sergei

N1 - Funding This work was partially supported by Agence Nationale de la Recherche (ANR) Perturbations [grant number ANR-10-BLAN0106]. The work of S. Sergeev was also supported by Engineering and Physical Sciences Research Council (EPSRC) [grant number EP/P019676/1].

PY - 2021/2/3

Y1 - 2021/2/3

N2 - We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T1,T2}, where T1 is the weak CSR threshold and T2 is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T1 and T2, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T1, which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.

AB - We study the transients of matrices in max-plus algebra. Our approach is based on the weak CSR expansion. Using this expansion, the transient can be expressed by max{T1,T2}, where T1 is the weak CSR threshold and T2 is the time after which the purely pseudoperiodic CSR terms start to dominate in the expansion. Various bounds have been derived for T1 and T2, naturally leading to the question which matrices, if any, attain these bounds. In the present paper, we characterize the matrices attaining two particular bounds on T1, which are generalizations of the bounds of Wielandt and Dulmage–Mendelsohn on the indices of non-weighted digraphs. This also leads to a characterization of tightness for the same bounds on the transients of critical rows and columns. The characterizations themselves are generalizations of those for the non-weighted case.

KW - 15A18

KW - 15A23

KW - 90B35

KW - Max-plus

KW - digraphs

KW - matrix powers

KW - periodicity

KW - transient

UR - http://www.scopus.com/inward/record.url?scp=85100412993&partnerID=8YFLogxK

U2 - 10.1080/03081087.2021.1878995

DO - 10.1080/03081087.2021.1878995

M3 - Article

SN - 0308-1087

JO - Linear and Multilinear Algebra

JF - Linear and Multilinear Algebra

ER -

On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

Tropical Optimisation

Cite this