On eigenproblem for circulant matrices in max-algebra. (English) Zbl 1005.90054

Summary: The eigenproblem for circulant matrices in max-algebra is shown to be solvable in \(O(n^2)\) time. An algorithm is described which for a given \(n\times n\) real circulant matrix \((a_{ij})\) computes an eigenvalue \(\lambda\) and all eigenvectors \(x= (x_1,\dots, x_n)\) such that \[ \max_{j=1,\dots, n} (a_{ij}+ x_j)= \lambda+ x_i,\quad i= 1,\dots, n. \] The results improve the standard \(O(n^3)\) algorithm used in the general case.


90C27 Combinatorial optimization
05B35 Combinatorial aspects of matroids and geometric lattices
Full Text: DOI


[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, R.A. 1979. ”Minimax Algebra Lecture, Notes in Econ. and Math. Systems 166”. Berlin: Springer-Verlag. · Zbl 0399.90052
[4] Dantzig G.B., Theory of graphs (1967) · Zbl 0178.22701
[5] DOI: 10.1007/BF01386390 · Zbl 0092.16002 · doi:10.1007/BF01386390
[6] DOI: 10.1287/opre.25.5.741 · Zbl 0387.90080 · doi:10.1287/opre.25.5.741
[7] Gavalec M., Eigenproblem for Monge Matrices in max-Algebra · Zbl 0984.65042
[8] DOI: 10.1007/BF01399312 · Zbl 0541.65009 · doi:10.1007/BF01399312
[9] Karp R.M., Discrete Math 23 pp 309– (1978)
[10] Lawler E.L., Combinatorial Optimization: Networks and Matroids Holt (1976) · Zbl 0413.90040
[11] DOI: 10.1080/02331939408843990 · Zbl 0815.68080 · doi:10.1080/02331939408843990
[12] DOI: 10.1137/0201010 · Zbl 0251.05107 · doi:10.1137/0201010
[13] Vorobyev N.N., Elektron. Informationsverarbeitung und Kybernetik 3 pp 39– (1967)
[14] Zimmermann U., Linear and Combinatorial Optimization in Ordered .Algebraic Structures (1981) · Zbl 0466.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.