Title: On the coefficients of the max-algebraic characteristic polynomial and equation.
Abstract: 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 {0, -∞} matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a {0, -∞} matrix can be converted to that of finding the conventional characteristic equation for a {0, 1} matrix and thus it is solvable in polynomial time.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 7
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot