# Perron-Frobenius for a “maximum” of matrices

Consider a set of positive matrices $(P_k)_{k\in K}$ in $\mathbb R^{p\times p}_{++}$ ($P_k$ is positive in the sense that all entries of $P_k$ are positive).

Let $X_0\in\mathbb R_{++}^p$ and define for every $n\ge0$ $X_{n+1}=\max_{k\in K}\{ P_kX_n\}$, where the max operator has to be understood element-wise: for all $i\in\{1,\ldots,p\}$, $[X_{n+1}]_i=\max\{k\in K:[P_kX_n]_i\}$.

Do the following statements hold?

• There exists a positive matrix $P$ and $n_0\ge0$ such that for all $n\ge n_0$, $X_{n+1}=PX_n$.
• The matrix $P$ is constructed as follows. Consider the set of matrices, such that every row $i\in\{1,\ldots,p\}$ of a matrix $M$ in that set is the row $i$ of a matrix $P_k$. (There are $(Card\ K)^p$ such matrices.) The matrix $P$ is the element of this set, which has the largest Perron-Frobenius eigenvalue, denoted $\lambda_{PF}$.
• $(X_n)_n$ converges to the Perron-Frobenius eigenvector. More precisely, $\lim_{n\rightarrow\infty} X_n/||X_n||$ exists and is denoted $x$. It is such that: $Px = \lambda_{PF} x$.

I inferred the previous properties from the case $p=2$ but even in that simple case, I do manage to prove any of the above statements.

Thanks for any help or useful reference.

• Is $K$ a finite set? – Pietro Majer Dec 5 '16 at 17:35
• Yes, no problem to assume $K$ finite (more general would be nice obviously but I would be very happy with the finite case first). – isanco Dec 5 '16 at 18:12

## 1 Answer

The answer is no, as the map you define is not linear.

For example consider the matrices $$P_1 = \begin{bmatrix} 2 & 1 \\ 2 & 1 \end {bmatrix},\quad P_2 = \begin{bmatrix} 1 & 2 \\ 1 & 2 \end {bmatrix}.$$ For simplicity, I'll call the map in question $F(x) := \max\{P_1x,P_2x\}$, where as you say the maximum is taken componentwise, i.e. with respect to the order induced by the cone of nonegative vectors.

Then for the vectors $$x_1 = \begin{bmatrix} 2 \\ 1 \end {bmatrix},\quad x_2 = \begin{bmatrix} 1 \\ 2 \end {bmatrix}$$ we have $$F(x_1) = P_1 x_1 = \begin{bmatrix} 5 \\ 5 \end {bmatrix}, \quad F(x_2) = P_2 x_2 = \begin{bmatrix} 5 \\ 5 \end {bmatrix}.$$ On the other hand $$F(x_1+x_2) = F\left( \begin{bmatrix} 3 \\ 3 \end {bmatrix}\right) = \begin{bmatrix} 9 \\ 9 \end {bmatrix},$$ which is clearly not equal to $F(x_1) + F(x_2)$. Now if there were a matrix $P$ as in your first question then the map $F$ would have to be linear. As the matrix $P$ does not exist your second and third question are no longer relevant.

All is maybe not lost though. If what you are interested in is a Perron-Frobenius result, then you can use the nonlinear Perron-Frobenius theory. At least your map is homogeneous, i.e. $F(\alpha x) = \alpha F(x)$ for $\alpha > 0$. In addition, your map is monotone, i.e. if $x \leq y$, then $F(x) \leq F(y)$. Finally, the induced graph of your map is full (for details on that see the paper below). So Theorem 2 in

S. Gaubert, J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions

shows that you have an eigenvector. For the convergence property that you want, I suggest to refer to the paper by Nussbaum cited in that paper.

• Thanks for your answer and the reference! In your counter example, the four matrices that can be build from $P_1$ and $P_2$ (i.e. $P_1$, $P_2$, first row of $P_1$-second row of $P_2$ and vice-versa) all have the same PF eigenvalue. Indeed, there is no $P$ and $(X_n)_n$ exhibits a circle. Should $P_1$ be modified such that there is only one matrix with the largest PF value (e.g. let change the first 2 of $P_1$ by a 3), it seems that there is a convergence. – isanco Dec 5 '16 at 20:06
• I do not see what you mean with $(X_n)_n$ exhibits a circle. In the example both matrices are rank one and project (obliquely) to the common eigenspace $\mathrm{span}\begin{bmatrix} 1 & 1 \end{bmatrix}^T$. If the first component of $x$ exceeds the second, then $F(x) = P_1 x$, else $F(x) = P_2(x)$. So it seems to me that the example is really trivial in that you jump to the eigenspace in one step. Where is the circle? – Fabian Wirth Dec 5 '16 at 20:13
• Sorry. You're right after one step, $P_1x=P_2x$. I will think more about the case when the PF value of $P_1$ is strictly greater than the one of $P_2$. – isanco Dec 5 '16 at 20:27