Limit of an absorbing random walk. (Limit of power of real symmetric matrix)

Question

I have a problem that comes from absorbing random walks on a connected undirected graph $G$ with two types of nodes, absorbing nodes and free nodes. We randomly pick a node to start, once the random walk reaches an absorbing node, it will never leave the node again. But if we are at a free node, we will pick an outgoing edge with probability proportional to the edge weight and go to one of the neighbouring nodes. With proper labelling of the nodes, the transition matrix $T(G)$ can be written as $$T = \begin{pmatrix} T_{aa} & T_{af} \\ T_{fa} & T_{ff} \end{pmatrix}, $$ where the matrix $T_{aa}$ corresponds to the block of probabilities corresponding to transitions from an absorbing node to another absorbing node, and so on. For the computation of the overall limiting distribution, I need to show that $\lim_{n \rightarrow \infty}{T_{ff}^{n} = 0}$ so that I can have a nice looking result $$\lim_{n \rightarrow \infty}{T^n} = \begin{pmatrix} I & 0 \\ (I-T_{ff})^{-1}T_{fa} & 0 \end{pmatrix}$$

I now believe that the limit is indeed zero and I think the easiest way is probably proving that all eigenvalues have absolute value strictly smaller than 1. And I can already show that the absolute values of all eigenvalues are no larger than 1. Can somebody help me to prove that there cannot be an eigenvalue whose absolute value is 1? Also, once we know no eigenvalue of $T_{ff}$ is 1, we would immediately have the fact that $I-T_{ff}$ is invertible. Other approaches are also welcome. Thanks.

Answer 1

I may be missing something on the conditions: what about $$A=\begin{pmatrix} 0 & 1 & 0\\ 1& 0 & 0\\ 0&0&0\end{pmatrix}?$$ You have $A^3 = A$, so its powers cannot converge to $0$.

Answer 2

Just come up with an argument from another direction.

Let the number of columns in $T_{ff}$ be $k$. Suppose, to derive a contradiction, that for any given $i$, $0\le i\le k$, the sum of entries of $i$-th row in $T_{ff}^{n}$ is positive when $n$ goes to infinity. And let us agree for the time being that the limit exists since the absolute values of all eigenvalues are no larger than 1. In other words, we are trying to derive a contradiction starting from the assumption that for any given vertex $v_i$, there is a random walk starting $v_i$, such that with a positive probability, it will never terminate. Since the graph is connected, there are some node(s) that have a absorbing neighbour. We denote by $B$ the set of nodes that are connected to at least one absorbing nodes. Let $B = \{ b_1, b_2, ..., b_k \}.$ At any $b_i$, let $p_i$ be the probability of the random walk staying within the subgraph $H$ that is induced by the free nodes. Since $p_i<1$, for a random walk of arbitrary length $n$, if it arrives at some node in $B$ for infinite number of times as $n$ goes to infinity, the probability it stays within $H$ will go to $0$. Therefore, all vertices in $B$ are visited only a finite number of times in order for the ith row in $T_{ff}^{n}$ to sum up to a positive value. When $n$ goes beyond a certain threshold, the nodes in $B$ will no longer be visited. Inductively, we can treat the nodes in $B$ as absorbing and apply the argument above. Eventually, we will be confined at a free node and have no where to go, which contradicts to the assumption. Thus the limit of $T_{ff}^{n}$ goes to the zero matrix.