Geodesic
On the coefficients of the max-algebraic characteristic polynomial and equation
Kybernetika, Tome 39 (2003) no. 2, p. [129]

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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]},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2003},
     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]
VL  - 39
IS  - 2
PB  - mathdoc
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]
%V 39
%N 2
%I mathdoc
%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, p. [129]. http://geodesic.mathdoc.fr/item/KYB_2003__39_2_a2/