Kybernetika 49 no. 4, 636-643, 2013

An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form

Peter Szabó

Abstract:

The paper presents an iterative algorithm for computing the maximum cycle mean (or eigenvalue) of $n\times n$ triangular Toeplitz matrix in max-plus algebra. The problem is solved by an iterative algorithm which is applied to special cycles. These cycles of triangular Toeplitz matrices are characterized by sub-partitions of $n-1$.

Keywords:

max-plus algebra, eigenvalue, sub-partition of an integer, Toeplitz matrix

Classification:

90C27, 15B05, 15A80

paper.pdf

References:

  1. P. Butkovič: Max-linear Systems: Theory and Algorithms. Springer-Verlag, London 2010.   CrossRef
  2. R. A. Cuninghame-Green: Minimax Algebra. Springer-Verlag, Berlin 1979.   CrossRef
  3. B. Heidergott, G. J. Olsder and J. van der Woude: Max Plus at Work. Modeling and Analysis of Synchronized Systems. Princeton University Press 2004.   CrossRef
  4. G. Heinig: Not every matrix is similar to a Toeplitz matrix. Linear Algebra Appl. 332-334 (2001), 519-531.   CrossRef
  5. R. M. Karp: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23 (1978), 309-311.   CrossRef
  6. H. J. Landau: Tile inverse eigenvalue problem for real symmetric Toeplitz matrices. J. Amer. Math. Soc. 7 (1994), 749-767.   CrossRef
  7. J. Plavka: Eigenproblem for monotone and Toeplitz matrices in a max-algebra. Optimization 53 (2004), 95-101.   CrossRef
  8. P. Szabó: A short note on the weighted sub-partition mean of integers. Oper. Res. Lett. 37(5) (2009), 356-358.   CrossRef
  9. K. Zimmermann: Extremální algebra (in Czech). Ekonomický ústav SAV, Praha 1976.   CrossRef