Extremal eigenproblem for bivalent matrices (Q1894469)

Introducing a maximum operation on a linearly ordered multiplicative group \(G\), the matrix-vector algebra over \(G\) may be defined by direct analogy to conventional linear algebra. An analog to the eigenproblem may be considered that is also called extremal eigenproblem with a reference to the operation that replaces summation in the standard linear algebra. For the additive group of real numbers in place of \(G\), an algorithm exists that can find the solution of the extremal eigenproblem in \(O(n^3)\) operations. The authors first develop an algorithm that can find the solution of the extremal eigenproblem for any bivalent matrix with entries equal to zero or one in \(O(m + n)\) operations, and then they extend this result to bivalent matrices over any linearly ordered, commutative radicable group.