zbMATH — the first resource for mathematics

A constructive fixed point theorem for min-max functions. (English) Zbl 0958.47028
This lengthy but highly readable paper covers a large amount of very interesting ground ranging from abstract algebraic ideas to modern applications in digital circuits. The authors show that there are two ways in which their work can be viewed as non-linear generalizations of the classical Perron-Frobenius theory for non-negative matrices. The first is that if $$\vec{x} \in \mathbb R^n$$ then $$\exp(\vec{x}) \in \mathbb R^{n+}$$. Throughout, functions work co-ordinatewise so that $$\exp(\vec{x})$$ is the vector whose $$i$$th coordinate is $$\exp(x_i)$$. If $$A$$ is a positive matrix then we may consider $${\mathcal E}(A)$$ defined by $${\mathcal E}(A)(\vec{x}):= \log(A(\exp(\vec{x})))$$. Then the fact that $$A$$ has a positive eigenvector $$\vec{u}$$ with positive eigenvalue $$\lambda$$ translates into the statement that $${\mathcal E}(A)$$ has a fixed vector $$\vec{x} := \log(\vec{u})$$ and an additive eigenvalue $$h:= \log \lambda$$ such that $${\mathcal E}(A)(\vec{x}) = \vec{x} + h$$ (again the addition works co-ordinatewise). The second is to consider $$\mathbb R \cup \{-\infty\}$$ as a semi-ring closed under the operations of $$\vee$$ and $$+$$; ($$\vee$$ plays the role of sum and $$-\infty$$ the neutral element; + plays the role of product and $$0$$ the identity element). Then certain functions from $$\mathbb R^n \mapsto \mathbb R^n$$ defined in terms of the operations $$\vee$$ and addition of numbers can be viewed as matrices acting on this semi-ring. These ideas motivate the following definitions.
A min-max function $$F: \mathbb R^n \mapsto \mathbb R^n$$ is one that is built from terms of the form $$x_i + a_i$$ using finitely many $$\vee$$ and $$\wedge$$ operations. A fixed point is a vector $$\vec{x}$$ for which there is an $$h \in \mathbb R$$ such that $$F(\vec{x}) = \vec{x} + h$$. The cycle time vector $${\mathcal X}(F) := \lim_{k \rightarrow\infty} F^k(\vec{x})/k$$. This last (if the limit exists) plays the role of the spectral radius in the Frobenius theory. The class of min-max functions is closed under composition, $$\vee$$, $$\wedge$$ and addition by vectors. Every such function is homogeneous (i.e. $$F(\vec{x} + h) = F(\vec{x}) + h)$$, monotone (with respect to the usual order on $$\mathbb R^n$$) and non-expansive (with respect to the $$\ell_{\infty}$$-norm). The more general class of topical functions from $$\mathbb R^n$$ to $$\mathbb R^n$$ are those that are homogeneous and monotone. The function $${\mathcal E}(A)$$ is an example of a topical function. Such functions are automatically also non-expansive and play important roles in various applications. The present investigation is an important step towards understanding them because, although special, the min-max functions are dense in the topical functions in both a topological and an order theoretic sense. The main theorem gives necessary and sufficient conditions for a min-max function to have a fixed point with corresponding eigenvalue $$h$$. The conditions are in terms of the cycle times of special representations of the function. The authors also give an algorithm for finding such a fixed point and the corresponding $$h$$. The paper, however, is also interesting for the broad point of view that it adopts and the insights into various areas of mathematics that it affords.

MSC:
 47H10 Fixed-point theorems
Full Text: