11
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ $A = \begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$. What would you like to know? $\endgroup$ – Vidit Nanda Nov 29 '14 at 19:04
  • $\begingroup$ 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. $\endgroup$ – Noah Snyder Nov 29 '14 at 19:25
  • 1
    $\begingroup$ Gantmacher's book The Theory of Matrices has a section on reducible non-negative matrices. $\endgroup$ – Anthony Quas Nov 29 '14 at 20:53
  • 2
    $\begingroup$ Seneta's book on Nonnegative Matrices has all the gory details if memory serves. $\endgroup$ – Douglas Lind Nov 29 '14 at 22:36
  • $\begingroup$ 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. $\endgroup$ – Ilya Kapovich Nov 30 '14 at 23:17
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.