Finding all essential terms of a characteristic maxpolynomial Original Research Article

Let us denote a⊕b=max(a,b) and a⊗b=a+b for a,b∈R=R∪{−∞} and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n2(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over R with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k∈{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.