On eigenproblem for circulant matrices in max-algebra

The eigenproblem for circulant matrices in max-algebra is shown to be solvable in O(n(2)) time. An algorithm is described which for a given n x n real circulant matrix (a(ij)) computes an eigenvalue lambda and all eigenvectors x = (x(1),...,x(n)) such that max(j=1,...,n) (a(y) + x(j)) = lambda + x(i) (i = 1,...,n). The results improve the standard O(n(3)) algorithm used in the general case.