Perron-Frobenius theorem for reducible non-negative matrices

350 Views Asked by At

Let $M$ be a non-negative matrix ($M_{ij}\geq 0$ for all $i,j$). If $M$ is irreducible, then we know that there exists an eigenvalue $\lambda$ of $M$ that equals the spectral radius $\rho(M)$ and has geometric and algebraic multiplicity of one. The corresponding eigenvector $v$ is strictly positive, i.e. $v_i>0$. If $M$ is reducible, then one may find a permutation matrix $P$ such that: \begin{equation} \widetilde{P}M\widetilde{P}^T = \left[ \begin{array}{cccc} A_{11} & 0 & \cdots & 0\\ A_{21} & A_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ A_{K1} & A_{K2} & \cdots & A_{KK} \end{array}\right] \end{equation} where each of the diagonal blocks $A_{ii}$ is either an irreducible matrix or a 1$\times$1 zero-matrix. This is the Frobenius normal form of $M$. What can be said about the eigenspace $E$ associated to $\rho(M)$. In the book "Nonnegative Matrices in the Mathematical Science" there is a theorem stating that:

Theorem: Let $M$ be a non-negative matrix with spectral radius $r$ and $m$ blocks whose Perron-Frobenius eigenvalues equal $r$. The algebraic eigenspace of $M$ contains spanning vectors $x^{(1)}, \dots, x^{(m)}$, such that $x^{(j)}_i>0$ iff $i$ has access to the block $j$ (there is a directed path from $i$ to the subgraph induced by the block $j$).

They use the convention that there is an edge from $i$ to $j$ iff $M_{ij}>0$. By algebraic eigenspace they mean the set of generalized eigenvectors. I'm not quite sure what they are.

Either I'm misunderstanding this theorem, or I have a few counter examples. What about the unweighted graph with 4 nodes and the following directed graph with edges $\{(1,2), (2,1), (1,3), (3,4),(4,3)\}$. The eigenvectors to $\lambda=\rho(M)=1$ (when written in their convention) has support only node 1 and 2. But the theorem says that there should be another generalized eigenvector with support on the other block (with nodes 3 and 4). Similar counter-examples can be constructed on demand.

So what is the correct reading of this theorem or the correct statement about the structure of the eigenvectors to $\rho(M)$ ... and what is the relation to the algebraic eigenspace? In short what should be the correct form of this extension of the Perron-Frobenius theorem to general non-negative matrices.

1

There are 1 best solutions below

0
On BEST ANSWER

Taking your example, the geometric eigenspace $Z_1$ for the eigenvalue 1 is $Z_1=\ker (M-I)$. It is one dimensional and generated by e.g. the column vector $v$ with components $\pmatrix{1 & 1 & 0 & 0}$.

The algebraic eigenspace is $Z_2=\ker((M-I)^2)$. It is two dimensional and generated by the above $v$ and e.g. the column vector $w$ with components $\pmatrix{0.5 & 0 & 1 & 1}$. It is not an eigenvector in the usual sense. Instead you have $Mw = w + v/2$ where the last part comes from the connection from the lower block to the upper one. There is no (generalized or not) eigenvector only with support on the lower block.

In general you would look at the 'increasing' sequence $Z_k=\ker ((M-I)^k)$, $k\geq 1$ for which $Z_1\subset Z_2\subset ...Z_K = Z_{K+1}$. It eventually saturates. $Z_1$ corresponds to the genuine eigenvectors and $Z_K$ to the generalized or algebraic eigenspace.

Hope this suffices for you to figure out how it works.

In your example, $M$ is b.t.w. upper and not lower block diagonal.