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.
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.
@article{KYB_2003_39_2_a2,
author = {Butkovi\v{c}, Peter},
title = {On the coefficients of the max-algebraic characteristic polynomial and equation},
journal = {Kybernetika},
pages = {129--136},
year = {2003},
volume = {39},
number = {2},
mrnumber = {1996551},
zbl = {1249.90213},
language = {en},
url = {http://geodesic.mathdoc.fr/item/KYB_2003_39_2_a2/}
}
TY - JOUR
AU - Butkovič, Peter
TI - On the coefficients of the max-algebraic characteristic polynomial and equation
JO - Kybernetika
PY - 2003
SP - 129
EP - 136
VL - 39
IS - 2
UR - http://geodesic.mathdoc.fr/item/KYB_2003_39_2_a2/
LA - en
ID - KYB_2003_39_2_a2
ER -
%0 Journal Article
%A Butkovič, Peter
%T On the coefficients of the max-algebraic characteristic polynomial and equation
%J Kybernetika
%D 2003
%P 129-136
%V 39
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2003_39_2_a2/
%G en
%F KYB_2003_39_2_a2
Butkovič, Peter. On the coefficients of the max-algebraic characteristic polynomial and equation. Kybernetika, Tome 39 (2003) no. 2, pp. 129-136. http://geodesic.mathdoc.fr/item/KYB_2003_39_2_a2/
[1] Ahuja R. K., Magnanti, T., Orlin J. B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, N.J. 1993 | MR | Zbl
[2] Baccelli F. L., Cohen G., Olsder G.-J., Quadrat J.-P.: Synchronization and Linearity. Wiley, Chichester 1992 | MR | Zbl
[3] Butkovič P., Murfitt L.: Calculating essential terms of a characteristic maxpolynomial. Central European Journal of Operations Research 8 (2000), 237–246 | MR | Zbl
[4] Cuninghame–Green R. A.: Minimax Algebra (Lecture Notes in Economics and Mathematical Systems 166). Springer, Berlin 1979 | MR
[5] Cuninghame–Green R. A.: The characteristic maxpolynomial of a matrix. J. Math. Anal. Appl. 95 (1983), 110-116 | DOI | MR | Zbl
[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 | Zbl
[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
