Modifying the power method in max algebra Original Research Article

In the max algebra system, the eigenequation for an n×n irreducible nonnegative matrix A=[aij] is A x=μ(A)x. Here (A x)i=maxjaijxj and μ(A) is the maximum circuit geometric mean. The complexity of the power method given in [L. Elsner, P. van den Driessche, Linear Algebra Appl., to appear] to compute μ(A) and x is considered. Under some assumptions on the critical matrix, it is shown that the algorithm may have time complexity O(n4). A modified power method, based on Karpʹs formula, is presented. For this new algorithm, with no assumptions on the critical matrix, μ(A) and x can be computed in O(n3) time. Furthermore, this algorithm can be used to compute all linearly independent eigenvectors corresponding to μ(A).