EXTREMAL EIGENPROBLEM FOR BIVALENT MATRICES

For a general n x n real matrix (a(ij)), standard O (n(3)) algorithms exist to find lambda, x(1),..., x(n) such that max (a(ij) + x(j)) = la mbda + x(i) (i = 1,..., n). j = 1,..., n It is known that lambda is un ique and equals the maximum cycle mean of(a(ij)). We consider the case when all the elements a(ij) take values in the real binary set (0, 1) , and we present algorithms which determine lambda, x(1),..., x(n) in O (m + n) time, where m is the number of nonzero elements of (a(ij)). We show that these algorithms may in fact be applied to bivalent matri ces over any linearly ordered, commutative radicable group.