Geodesic
On the coefficients of the max-algebraic characteristic polynomial and equation
Kybernetika, Tome 39 (2003) no. 2, pp. 129-136 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
Classification : 15A15, 90C27, 93C65
Keywords: matrix; characteristicpolynomial; characteristic equation 
@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