Applications of max algebra to diagonal scaling of matrices.
On the coefficients of the max-algebraic characteristic polynomial and equation
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 matrix can be converted to the assignment problem....
Page 1