Extremal eigenproblem for bivalent matrices Original Research Article

For a general n × n real matrix (aij), standard O(n3) algorithms exist to find λ, x1, …, xn such that image It is known that λ is unique and equals the maximum cycle mean of (aij). We consider the case when all the elements aij take values in the real binary set {0, 1}, and we present algorithms which determine λ, x1, …, xn in O(m + n) time, where m is the number of nonzero elements of (aij). We show that these algorithms may in fact be applied to bivalent matrices over any linearly ordered, commutative radicable group.