Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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.

share|improve this answer
    
Yes, you are right. The undirected case is actually trivial. In the undirected case I still see some margin of action. –  Delio Mugnolo 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 Mugnolo 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.