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.

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

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.

| cite | improve this answer | | | | |
  • $\begingroup$ 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. $\endgroup$ – isanco Dec 5 '16 at 20:06
  • $\begingroup$ 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? $\endgroup$ – Fabian Wirth Dec 5 '16 at 20:13
  • $\begingroup$ 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$. $\endgroup$ – isanco Dec 5 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.