Eigenvectors to the largest eigenvalue $\lambda_1$ of $A\geq 0$ are non-zero only at the end of the longest chains when $\lambda_1=0$?

457 Views Asked by At

Let $n>0$ and $A\in M_{n\times n}(\{0,1\})$. Suppose the largest eigenvalue $\lambda_{1}=0$ vanishes. Then there is no closed path in the graph, only chains. I have read the claim that only the end points of the longest chains in the graph have strictly positive entries in the "Perron-Frobenius" eigenvector, i.e. the eigenvector that is associated to the largest eigenvalue (in our case $\lambda_1=0$). Is this true? If so, how is it shown? (In this question I'm more specific than in an older post. I don't mind when that older post is being put on hold)

Edit I use the convention that there is an arrow from $i$ to $j$ iff $A_{ji}>0$. (I noticed from the feedback that this seems to be an uncommon convention).

1

There are 1 best solutions below

4
On BEST ANSWER

First of all, notice that the eigenvalue $0$ may not be simple, so there's no thing as "the" nonnegative eigenvector for $\lambda =0$. Nonetheless, for nonnegative matrices, we can prove that ALL nonnegative eigenvectors for $\lambda =0$ must have the value 0 in certain entries and may have any value on other entries.

Suppose now that $i$ is NOT the endpoint of a chain, meaning that there is at least an out edges from $i$. In the associated matrix you have, by definition, $A_{ji}=1$ for at least a node $j$.

Suppose now that $v$ is ANY eigenvector for $\lambda=0$ with $v\ge 0$, meaning that $Av=0$. If you restrict on row $j$, you have $$ \sum_{k} A_{jk}v_k = 0 $$ but all the elements of $A$ and $v$ are nonnegative, and $A_{ji}=1$, so necessarily $v_i=0$, otherwise $$ v_i>0 \implies \sum_{k} A_{jk}v_k \ge v_i > 0. $$ Consequently, ALL nonnegative eigenvectors for $\lambda=0$ have value 0 on the $i$-th component, that is a generic node that is not an endpoint for a chain.

Suppose now that $\hat i$ is an endpoint of a chain, or equivalently, has no out edges. By definition, $A_{j\hat i}=0$ for every node $j$, so the $\hat i$-th column is 0. This means that the $\hat i$-th component of any nonnegative eigenvectors for $\lambda=0$ may be any nonnegative value, since $$ \sum_{k} A_{jk}v_k = \sum_{k\ne \hat i} A_{jk}v_k\qquad \forall j. $$ In particular, there exists an eigenvector $v$ such that $$ v_i = \begin{cases} 1 & i \text{ is an endpoint of a chain}\\ 0 & i \text{ is not an endpoint of a chain} \end{cases} $$