# Perron-Frobenius theory for reducible matrices

Can someone suggest some sources/references dealing with the Perron-Frobenius theory for nonnegative matrices that are reducible?

Specifically, if $A\ge 0$ is a $d\times d$ matrix with no assumptions about irreducibility, I am interested the precise description of

a) the set of all non-negative eigenvectors $v\ge 0$ in $R^d$ for $A$; and b) the dynamics of the action of $A$ on the non-negative quadrant $W=\{w\in R^d | w\ge 0\}$, particularly the limiting behavior (up to projectivization) of the sequences $A^nw$ where $w\in W$ and $n=1,2,3,...$.

The standard sources on the Perron-Frobenius theory only deal with primitive and irreducible nonnegative matrices, and I could not find any sources that treat in detail the case of an arbitrary $d\times d$ matrix $A\ge 0$.

• $A = \begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$. What would you like to know? – Vidit Nanda Nov 29 '14 at 19:04
• Have you looked at the beginning of Goodman, de la Harpe, Jones? I forget the exact details, but I recall that they need to do a little more generality than a lot of sources due to the bipartite nature of principal graphs. – Noah Snyder Nov 29 '14 at 19:25
• Gantmacher's book The Theory of Matrices has a section on reducible non-negative matrices. – Anthony Quas Nov 29 '14 at 20:53
• Seneta's book on Nonnegative Matrices has all the gory details if memory serves. – Douglas Lind Nov 29 '14 at 22:36
• Of course, Seneta and Gantmacher were the first places where I looked. Seneta's book has almost nothing about non-irreducible matrices and Gantmacher has a bit more but still rather little. The thing that I would really like to see is some sort of a detailed structural theorem which explains the possible limiting behavior of $A^nw/||A^nw||$ for nonzero vectors $w\ge 0$ such that $A^nw$ remains nonzero for all $n\ge 1$. For a nonnegative $d\times d$ matrix $A$ which is not irreducible the answer to this question seems to be much more messy and complicated than in the irreducible case. – Ilya Kapovich Nov 30 '14 at 23:17

I copy here a few selected results relating Perron-Frobenius and nonnegative matrices. They all come from the book Matrix Analysis of R. Horn and C. Johnson.

For $x\in \Bbb R^d$, $x\geq 0$ ($x>0$) means $x_i\geq 0$ (resp. $x_i>0$) for every $i=1,\ldots,d$.

Perron Frobenius:

Theorem 8.3.1. If $A\in \Bbb R^{d\times d}$ is a nonnegative matrix, then the spectral radius $\rho(A)$ of $A$ is an eigenvalue of $A$ and there exists $x\geq 0, x \neq 0$ such that $Ax=\rho(A)x$.

Theorem 8.3.4. Let $A\in \Bbb R^{d\times d}$ be nonnegative. Suppose that there exists $x>0$ and $\lambda\in \Bbb R$ such that either $Ax=\lambda x$ or $x^TA=\lambda x^T$, then $\lambda = \rho(A)$.

Collatz-Wielandt ratios:

Theorem 8.1.26 Let $A\in \Bbb R^{d\times d}$ be nonnegative, then for any $x>0$, we have $$\min_{1\leq i \leq d}\frac{(Ax)_i}{x_i}\ \leq\ \rho(A) \ \leq\ \max_{1\leq i \leq d}\frac{(Ax)_i}{x_i}.$$

Corollary 8.3.3. If $A\in \Bbb R^{d\times d}$ is nonnegative, then $$\rho(A)=\displaystyle\max_{\substack{x\geq 0\\ x \neq 0}}\min_{\substack{1\leq i \leq d\\ x_i \neq 0}}\frac{(Ax)_i}{x_i}.$$

Now, you ask for the behavior of the iterates of the function $$T:\Bbb R^d \to \Bbb R^d, \quad x\mapsto \dfrac{Ax}{\|Ax\|},$$ this is known as the power method (or power iteration). A convergence theorem for this method can be found here. I copy it for the convenience of the reader. (The exercise under comes from the book cited above.)

Power method

Theorem 6.2. Let the eigenvalues of $A\in \Bbb R^{d\times d}$ be arranged such that $|\lambda_1|>|\lambda_2|\geq |\lambda_3|\geq \ldots \geq |\lambda_d|$. Let $u$ and $v$ be right and left eigenvectors of $A$ corresponding to $\lambda_1$, respectively. Let $x^{k+1}:= T(x^{k})$ for $k\in \Bbb N$, then $$\sin\big( \angle(x^k,u)\big)\leq c\left|\frac{\lambda_2}{\lambda_1}\right|^k\qquad \forall k\in \Bbb N$$ provided that $\langle v , x^0\rangle\neq 0$.

Exercise 8.3.P14 Let $A\in \Bbb R^{d\times d}$ be nonnegative, then:

• $\rho(A)$ can have geometric multiplicity greater than $1$ only if every minor of $\rho(A)I-A$ is zero.

• $\rho(A)$ can have algebraic multiplicity greater than $1$ only if every principal minor of $\rho(A)I-A$ is zero.

I recently ran into a similar problem. Something that helped me a lot was Chapter 9 of the first edition of the Handbook of Linear Algebra (which seems to be Chapter 10 of the second edition---just look for something written by Rothblum), edited by Professor Hogben.