Eigenproblem for monotone and Toeplitz matrices in a max-algebra. (English) Zbl 1079.93033

Plavka, Ján

Optimization 53, No. 1, 95-101 (2004).

Summary: The eigenproblem for monotone and Toeplitz matrices in a max-algebra is shown to be solvable in \(O(n^2)\) time. Two algorithms are described which, for a given \(n \times n\) real monotone and for a given \(n\times n\) real Toeplitz matrix compute an eigenvalue \({\lambda}\); and all eigenvectors of the form \(x = (x_1, x_2, \dots , x_n)\) such that
\[ \max (a_{ij} + x_j) = \lambda + x_i \text{ for \;all } i = 1,2,\dots,n. \]
These results improve standard \(O(n^3)\) algorithms used in the general case.

MSC:

93C65	Discrete event control/observation systems
05B35	Combinatorial aspects of matroids and geometric lattices
90C27	Combinatorial optimization

Keywords:

monotone matrix; Toeplitz matrix

References:

[1]	DOI: 10.1016/0166-218X(92)90039-D · Zbl 0776.05070 · doi:10.1016/0166-218X(92)90039-D
[2]	DOI: 10.1057/jors.1962.10 · doi:10.1057/jors.1962.10
[3]	Cuninghame-Green RA, Minimax Algebra (1979)
[4]	Dantzig GB, Theory of Graphs, Gordon and Breach (1967)
[5]	DOI: 10.1007/BF01386390 · Zbl 0092.16002 · doi:10.1007/BF01386390
[6]	DOI: 10.1016/S0166-218X(02)00395-5 · Zbl 1041.90045 · doi:10.1016/S0166-218X(02)00395-5
[7]	Karp RM, Discrete Math 23 pp 309– (1978)
[8]	Lawler EL, Combinatorial Optimization: Networks and Matriods, Holt, Rinehart and Wilston (1976)
[9]	DOI: 10.1080/02331930108844576 · Zbl 1005.90054 · doi:10.1080/02331930108844576
[10]	Vorobyev NN, Elektron. Informationsverarbeitung und Kybernetic 3 pp 39– (1967)
[11]	Zimmermann U, Ann. Discrete Math. (1981)