Kybernetika 55 no. 1, 12-23, 2019

A bound for the rank-one transient of inhomogeneous matrix products in special case

Arthur Kennedy-Cochran-Patrick, Sergeĭ Sergeev and Štefan BerežnýDOI: 10.14736/kyb-2019-1-0012


We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.


max-plus algebra, matrix product, rank-one, walk, Trellis digraph


15A80, 68R99, 16Y60, 05C20, 05C22, 05C25


  1. F. L. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley and Sons, Hoboken 1992.   CrossRef
  2. P. Butkovic: Max-linear Systems: Theory and Algorithms. Springer Monographs in Mathematics, London 2010.   DOI:10.1007/978-1-84996-299-5
  3. B. Kersbergen: Modeling and Control of Switching Max-Plus-Linear Systems. Ph.D. Thesis, TU Delft 2015.   CrossRef
  4. G. Merlet, T. Nowak and S. Sergeev: Weak CSR expansions and transience bounds in max-plus algebra. Linear Algebra Appl. 461 (2014), 163-199.   DOI:10.1016/j.laa.2014.07.027
  5. G. Merlet, T. Nowak, H. Schneider and S. Sergeev: Generalizations of bounds on the index of convergence to weighted digraphs. Discrete Appl. Math. 178 (2014), 121-134.   DOI:10.1016/j.dam.2014.06.026
  6. L. Shue, B. D. O. Anderson and S. Dey: On steady state properties of certain max-plus products. In: Proc. American Control Conference, Philadelphia, Pensylvania 1998, pp. 1909-1913.   DOI:10.1109/acc.1998.707354