I am reading a proof (theorems about shifts) in an introductory dynamical systems book which uses the following fact:

Definitions: Let $A$ be an $m\times m$ adjacency matrix $(a_{ij})$ and $\Sigma_m=\mathcal{A}_m^\mathbb{Z}$ be the set of infinite two-sided sequences of symbols in $\mathcal{A}_m:=\{1,\dots,m\}$. Now, we let $\Sigma_m^+=\mathcal{A}_m^\mathbb{N}$ be the infinite one-sided sequences. We say that a word or infinite sequence $x$ in the alphabet $\mathcal{A}_m$ is allowed if $a_{x_i,x_{i+1}}>0$. Hence we let $\Sigma_A\subset\Sigma_m$ be the set of allowed two-sided sequences and $\Sigma_A^+\subset\Sigma_m^+$ the set of allowed one-sided sequences.

Now, they say that if all entries of some power of $A$ is positive, then in the product topology $\Sigma_A^+$ and $\Sigma_A$, periodic points are dense and there are dense orbits.

They don't explain why this is true and since I failed proving this by myself, I was wondering whether someone can help me.

Any hints are appreciated.


Suppose $x\in \Sigma_A$ and suppose we want to find a periodic point which agrees with $x$ on the first $N$ entries. The word $x_0\ldots x_N$ can be extended to an admitted word $x_0\ldots x_N x_{N+1}\ldots x_{N+k}$ such that $x_{N+k}=x_0$ (this is precisely because $A$ has a power $k$ such that the $(x_N,x_0)$ entry is positive.

Then this means the periodic sequence $$(x_0\ldots x_{N+k-1})(x_0\ldots x_{N+k-1})\ldots$$ is admitted.

It follows that to any admitted sequence, there are admitted periodic sequences arbitrarily close to it, and so the periodic sequences are dense.

The way to view this in terms of the graph associated to the adjacency matrix is that every admitted word has an associated path in the graph, and such a path can be extended to a cycle because the graph is strongly connected (implied by the matrix having a power whose entries are all positive). This cycle can then be repeated infinitely to give an infinite periodic path whose associated infinite sequence is close to the original sequence you began with.

To find a dense orbit, do the same kind of arguement where one wants to extend an admitted word to the right so that it contains the next admitted word in some linearly ordered list of admitted words.

The graph associated to the adjacency matrix is definitely the best way to view this. As a power of $A$ has all positive entries, it mean you can get from any vertex to any other vertex using a finite directed path, and so one just needs to build an infinite directed path which goes through every possible finite path at least once.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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