A max version of the Perron-Frobenius theorem (Q1307193): Difference between revisions

In one variant of max algebra, the two binary operations are multiplication and maximization. There is a corresponding matrix theory, wherein the maximum takes the place of the sum in all matrix operations. In this context one can speak of maxeigenvalues and maxeigenvectors, and the purpose of this (largely expository) paper is to put some already-known maxeigentheory into a coherent framework, and to trace out more clearly its connections to the traditional eigentheory. Of particular concern is the max version of the Perron-Frobenius theorem, namely, for any nonnegative irreducible matrix \(A=(a_{ij})\), there is a positive vector \(x\) such that \(\max_j a_{ij} x_j = \mu(A)x_i\) for i=1,2,\dots,n, where \(\mu(A)\) is the maximum geometric mean of a circuit in the weighted directed graph corresponding to \(A\). The paper offers five different proofs of this result, some of them new, reflecting the various methods of proof which have been applied to the classical Perron-Frobenius theorem. It also presents two different generalizations which unify the traditional and the max forms of this theorem. One of these, in particular, allows for an interpolation between the two by defining a matrix product with the traditional \(\sum_{j=1}^n a_{ij} b_{jr}\) replaced by the sum of the k largest products \(a_{ij} b_{jr}\), for \(k\) a number between 1 and \(n\). If \(k\) is 1, this is the max product, while \(k=n\) yields the traditional product.