# power bounded adjacency matrices

A bounded linear operator $T$ on a Banach space $X$ is called power bounded if $\|T^k\|\le M$ for some $M>0$ and all $k\in \mathbb N$.

A classical result of Lorch says that if $X$ is reflexive, then each power bounded operator $T$ on it is mean ergodic, meaning that the sequence $$C_n x:= \frac{1}{n} \sum_{k=1}^n T^k x,\qquad n=1,2,\ldots,$$ of its Cesaro sums converges for all $x\in X$. (Actually, also the converse implication holds).

Now, take a simple digraph (possibly infinite, but uniformly locally finite) and consider its adjacency matrix $A$. It would be nice to know whether $(A^n)_{n\in \mathbb N}$ converges, but this seems to be usually hopeless. Hence an more pragmatic approach would be to investigate whether $A$ is at least mean ergodic. By the above result by Lorch, it would be sufficient to show power boundedness.

Hence my question:

Is it possibly known whether $A$ is power bounded for certain classes of digraphs?

EDIT: As Robert Israel points out in his answer, the question is trivial if the graph is not oriented. Therefore, I have restricted the question to digraphs.

-
add comment

## 1 Answer

$(A^n)_{i,j}$ is the number of (directed) walks of length $n$ from $i$ to $j$. Only in rather special circumstances can that be uniformly bounded. It is not true in an undirected graph with at least one vertex of degree $\ge 2$. It is not true in a directed graph if there are two cycles with one accessible from the other.

-
Yes, you are right. The undirected case is actually trivial. In the undirected case I still see some margin of action. –  Delio M. Feb 28 '13 at 0:08
It is rather trivially true for directed trees (or directed forests). –  Robert Israel Feb 28 '13 at 3:43
...and also for cycles of course. Would it hold for general circulant digraphs? Or for eulerian digraphs? –  Delio M. Mar 3 '13 at 13:56
Not if there are at least two cycles (in the same strongly connected component, in the circulant case). –  Robert Israel Mar 3 '13 at 20:46
add comment