Institution: | a Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010, Graz, Austria b School of Mathematics and Statistics, The University of Birmingham, Birmingham B15 2TT, UK |
Abstract: | Let us denote a b=max(a,b) and a b=a+b for
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
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. |