Article
Full entry |
PDF
(1.1 MB)
Feedback
PDF
(1.1 MB)
Feedback
Keywords:
matrix; characteristicpolynomial; characteristic equation
matrix; characteristicpolynomial; characteristic equation
Summary:
No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and characteristic equation of a matrix in max- algebra. The following are proved: (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a $\lbrace 0,-\infty \rbrace $ matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a $\lbrace 0,-\infty \rbrace $ matrix can be converted to that of finding the conventional characteristic equation for a $\lbrace 0,1\rbrace $ matrix and thus it is solvable in polynomial time.
References:
[1] Ahuja R. K., Magnanti, T., Orlin J. B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, N.J. 1993 MR 1205775 | Zbl 1201.90001
[2] Baccelli F. L., Cohen G., Olsder G.-J., Quadrat J.-P.: Synchronization and Linearity. Wiley, Chichester 1992 MR 1204266 | Zbl 0824.93003
[3] Butkovič P., Murfitt L.: Calculating essential terms of a characteristic maxpolynomial. Central European Journal of Operations Research 8 (2000), 237–246 MR 1799201 | Zbl 0982.90042
[4] Cuninghame–Green R. A.: Minimax Algebra (Lecture Notes in Economics and Mathematical Systems 166). Springer, Berlin 1979 MR 0580321
[5] Cuninghame–Green R. A.: The characteristic maxpolynomial of a matrix. J. Math. Anal. Appl. 95 (1983), 110-116 DOI 10.1016/0022-247X(83)90139-7 | MR 0710423 | Zbl 0526.90098
[6] Klinz B.: Private communication (2002.
[7] (Ed.) J. van Leeuwen: Handbook of Theoretical Computer Science – Vol. A: Algorithms and Complexity. Elsevier, Amsterdam and MIT Press, Cambridge, MA 1990 MR 1127166 | Zbl 0714.68001
[8] Murfitt L.: Discrete-Event Dynamic Systems in Max-Algebra: Realisation and Related Combinatorial Problems. Thesis. The University of Birmingham, 2000
[9] Zimmermann U.: Linear and Combinatorial Optimization in Ordered Algebraic Structures (Annals of Discrete Mathematics 10). North Holland, Amsterdam 1981 MR 0609751
Search
Partner of
