The n-Category Café

Compact semigroups

By a compact semigroup we mean a non-empty semigroup $S$ with a compact Hausdorff topology and jointly continuous multiplication $S\times S\to S$. We shall assume for simplicity that the topology on $S$ is metric since our main examples have this property. The following simple exercise from topology will be used without comment in the sequel.

Lemma 1  Let $(X,d)$ be a compact metric space and $\{x_n\}$ a sequence in $X$. Then $x_n$ converges to $x\in X$ if and only if every convergent subsequence of $\{x_n\}$ converges to $x$.

For example, it is easy to prove from this lemma that if $S$ is a compact semigroup which is algebraically a group, then the inverse is continuous. Indeed, if $s_n\to s$ and $\tilde{s}$ is a limit of some subsequence of $\{s_n^{-1}\}$, then $\tilde{s}s=1=s\tilde{s}$ and so $\tilde{s}=s^{-1}$. By the lemma, it follows that $s_n^{-1}\to s^{-1}$.

A compact semigroup is called monothetic if it is topologically generated by a single element, that is, $S=\overline{⟨s⟩}$ for some $s\in S$ where, as usual, $⟨s⟩=\{s^n\mid n\ge 1\}$ is the subsemigroup generated by $s$. One easily checks that $S$ is commutative. In fact, the structure of $S$ is well known and we record it in the following theorem, due independently to Koch and Numakura without the metric assumption.

Theorem 2 (Koch, Numakura)  Let $S=\overline{⟨s⟩}$ be a monothetic compact (metric) semigroup. Then $S$ has a unique minimal ideal $I$, namely the set of all limits of convergent subsequences of $\{s^n\}$. Moreover, $I$ is a compact abelian group. The identity $s^{\omega }$ of $I$ is the unique idempotent of $S$. Furthermore, $I=s^{\omega }S$ and the map $x\mapsto s^{\omega }x$ is a surjective continuous homomorphism $S\to I$ and so in particular $I$ is a monothetic compact abelian group.

Proof:  The sets $s^{n}S$ with $n\ge 1$ form a decreasing chain of closed ideals and hence have non-empty intersection by compactness. Put $I={\bigcap }_{n\ge 1}{s}^{n}S$; clearly $I$ is a closed ideal. We claim it consists precisely of all limits of convergent subsequences of $\{s^n\}$.

Indeed, suppose that $x=\lim s^{n_k}$ and $n\ge 1$. Then by passing to a subsequence we may assume that $n_k>n$ for all $k$ and $\{s^{n_k-n}\}$ converges to an element $y\in S$. Then $x=s^{n}y$ by continuity of multiplication. We conclude that $x\in I$. For the converse, first observe that every element of $S\setminus \{s^k\mid k\ge 1\}$ is a limit of a subsequence of $\{s^n\}$. Thus it suffices to prove that if $s^m\in I$ for some $m\ge 1$, then $s^m$ is a limit of a convergent subsequence of $\{s^n\}$. But then we have $s^m=s^{m}y$ for some $y\in S$. If $y=\lim s^{n_k}$ with $n_k$ an increasing sequence, then $s^m=\lim s^{m+n_k}$. Otherwise, $s^m=s^{m+k}$ for some $k\ge 1$. But then $s^{m+nk}=s$ for all $n\ge 1$ and so $s^{m+nk}\to s^m$. Thus $I$ consists of all limits of convergent subsequences of $\{s^n\}$.

We next show that $I$ is algebraically a group. It will then follow that it is a compact abelian group. To do this, it suffice to show (by commutativity) that $ax=b$ has a solution $x\in I$ for all $a,b\in I$. Suppose $a=\lim s^{n_k}$ and $b=\lim s^{m_k}$. Passing to a subsequence, we may assume that $m_k>n_k$ for all $k$. Extracting further subsequences, we may assume $s^{m_k-n_k}$ converges to an element $x\in S$. Then $$ax=\lim s^{n_k}{s}^{m_k-n_k}=\lim s^{m_k}=b.$$ This completes the proof that $I$ is a group.

Let us show that $I$ is the unique minimal ideal. Let $J$ be an ideal of $S$. Then $\varnothing \ne IJ\subseteq I\cap J\subseteq J$. But $I$ is a group and so has no proper ideals. Thus $IJ=I$ and so $I\subseteq J$.

Suppose that $f\in S$ is an idempotent. From $f=\lim f^n$, it is immediate that $f$ is a limit of a subsequence of $\{s^n\}$ and hence belongs to $I$. But $I$ is a group and therefore contains a unique idempotent, its identity. Clearly $s^{\omega }S\subseteq I$ and so $s^{\omega }S=I$ by minimality. For $x,y\in S$, one has $s^{\omega }x{s}^{\omega }y=(s^{\omega }{)}^{2}xy=s^{\omega }xy$ and so $x\mapsto s^{\omega }x$ is a continuous surjective homomorphism $S\to s^{\omega }S=I$. This completes the proof.

Let $S=\overline{⟨s⟩}$ be a compact monothetic semigroup (which we continue to assume to be metric) and let $S\times X\to X$ be a faithful continuous left action of $S$ on a compact Hausdorff space $X$. Then $s^{\omega }X$ is a closed $S$-invariant subspace, known as the eventual range of $s$, and $S$ acts on $s^{\omega }X$ by homeomorphisms. Moreover, the action of $S$ on $s^{\omega }X$ factors through the homomorphism $S\to s^{\omega }S$ from Theorem 2.

Notice that the fixed-point set of $s$ is contained in the eventual range. Indeed, $sx=x$ implies $s^{n}x=x$ for all $n\ge 1$ and so $s^{\omega }x=x$. It follows that if the eventual range of $s$ is a singleton, that is, if $s^{\omega }$ acts as a constant map, then $s$ has a unique fixed-point. Indeed, if $s^{\omega }X=\{x_0\}$, then since the eventual range of $s$ is $S$-invariant, clearly $s{x}_0=x_0$. But the above discussion shows that each fixed point of $s$ belongs to the eventual range and so $x_0$ is the unique fixed-point of $S$. In this case, $s^{\omega }S=\{s^{\omega }\}$ (by faithfulness of the action) and hence $s^n\to s^{\omega }$ in light of Theorem 2 and Lemma 1. We summarize this discussion in the following proposition.

Proposition 3  Let $S=\overline{⟨s⟩}$ be a monothetic compact semigroup acting faithfully on the left on a compact Hausdorff space $X$ and suppose that $s^{\omega }$ acts as a constant map with image $x_0$, i.e., $\{x_0\}$ is the eventual range of $s$. Then $x_0$ is the unique fixed-point of $s$ on $X$, $s^n\to s^{\omega }$ (uniformly) and $s^{n}x\to x_0$ for all $x\in X$. The dual statement holds for right actions.

As a warmup exercise let us give a quick proof of the Banach fixed point theorem for compact metric spaces. Let $(X,d)$ be a compact metric space. A mapping $f:X\to X$ is a weak contraction if $d(f(x),f(y))\le d(x,y)$ for all $x,y\in X$. If the inequality is strict for $x\ne y$, then $f$ is said to be a (strict) contraction. The weak contractions form a submonoid $\mathrm{WCtr}(X)$ of the monoid of continuous self-maps of $X$, which is easily verified to be closed in the compact-open topology (and hence is metric via the sup norm). Since the weak contractions clearly form an equicontinuous family, the monoid $\mathrm{WCtr}(X)$ is in fact compact by the Arzelà–Ascoli theorem. The weak contractions form an ideal $J$ of $\mathrm{WCtr}(X)$.

Let $f:X\to X$ be a weak contraction such that $f^N$ is a contraction for some $N\ge 1$. Then $S=\overline{⟨f⟩}$ is a compact monothetic subsemigroup of $\mathrm{WCtr}(X)$. Moreover, if $I$ is the minimal ideal of $S$, then $I\subseteq f^{N}S\subseteq J$ and hence consists of contractions. In particular, $f^{\omega }$ is a contraction. But the image of an idempotent is its fixed-point set and it is easily checked that a contraction has at most one fixed-point. Thus $f^{\omega }$ is a constant map to some point $x_0$. By Proposition 3, $x_0$ is the unique fixed-point of $f$ and $f^n(x)\to x_0$ for all $x\in X$. This is the Banach fixed-point theorem for compact metric spaces.

Stochastic matrices

Let ${𝒫}_n$ be the space of all probability distributions on $\{1,\dots ,n\}$. We may identify it with the subspace of (row) vectors in ${ℝ}^n$ with non-negative entries summing to $1$. That is, ${𝒫}_n$ is the standard $(n-1)$-simplex in ${ℝ}^n$ and hence is compact. Let ${𝒮}_n$ be the set of all $n\times n$ stochastic matrices, that is, the set of all square matrices whose rows belong to ${𝒫}_n$. Then ${𝒮}_n$ is a compact monoid (homeomorphic to ${𝒫}_n^n$) with respect to matrix multiplication. Moreover, it is a partially ordered monoid with respect to the usual ordering ($A\ge B$ if $A-B\ge 0$) on non-negative matrices.

The natural right action ${ℝ}^n\times {𝒮}_n\to {ℝ}^n$ is clearly continuous and ${𝒫}_n$ is a compact invariant subspace. Moreover, the action of ${𝒮}_n$ on ${𝒫}_n$ is faithful because ${𝒫}_n$ contains the standard unit vectors. Thus we can also view ${𝒮}_n$ as a compact monoid of transformations of both ${𝒫}_n$ and ${ℝ}^n$ with respect to the compact-open topology.

Let $J$ denote the matrix of all ones; note that $PJ=J$ for any stochastic matrix $P$.

Lemma 4  Let $\epsilon >0$. Then $I_{\epsilon }=\{Q\in {𝒮}_n\mid Q\ge \epsilon J\}$ is a closed left ideal of ${𝒮}_n$.

Proof:  Clearly $I_{\epsilon }$ is closed. If $P,Q\in {𝒮}_n$ with $Q\in I_{\epsilon }$, then $PQ\ge P(\epsilon J)=\epsilon J$ and so $PQ\in I_{\epsilon }$, as required.

Consequently, the positive stochastic matrices form a left ideal of ${𝒮}_n$ (topologically open). A probability distribution $\pi \in {𝒫}_n$ is stationary for a stochastic matrix $P$ if $\pi P=\pi$, i.e., it is a fixed-point of $P$.

Lemma 5  An idempotent positive stochastic matrix $Q$ has a unique stationary distribution $\pi$. Moreover, $\pi$ is strictly positive, each row of $Q$ is $\pi$, and all fixed vectors of $Q$ are multiples of $\pi$. Consequently, $Q$ has rank $1$ and acts as a constant map on ${𝒫}_n$ with image $\pi$.

Proof:  Let $Q_{ij}$ be the largest entry in column $j$. Then $$\sum _{k=1}^n{Q}_{ik}(Q_{ij}-Q_{kj})=\sum _{k=1}^n{Q}_{ik}{Q}_{ij}-\sum _{k=1}^n{Q}_{ik}{Q}_{kj}=Q_{ij}-Q_{ij}=0$$ and hence $Q_{ij}=Q_{kj}$, for $k=1,\dots ,n$, as each $Q_{ik}>0$ and $Q_{ij}-Q_{kj}\ge 0$. Thus all rows of $Q$ are $\pi$ for some strictly positive probability distribution $\pi$. Idempotency immediately yields $\pi Q=\pi$. Moreover, since $Q$ is a rank $1$ idempotent, every fixed vector of $Q$ must be a multiple of $\pi$. Consequently, $\pi$ is the unique stationary distribution for $Q$. Since the image of an idempotent mapping is its fixed-point set, we conclude that $Q$ acts on ${𝒫}_n$ as a constant map with image $\pi$.

A stochastic matrix $P$ is said to be ergodic if $P^m>0$ for some $m$. Now we can prove one of the main theorems of finite Markov chain theory. Recall that an eigenvalue of a matrix is simple if it has multiplicity one as a root of the characteristic polynomial.

Theorem 6  Let $P$ be an ergodic stochastic matrix. Then:

1. $P$ has a unique stationary distribution $\pi$;
2. $\pi$ is strictly positive;
3. $P^n\to \Pi$ where $\Pi$ is the matrix all of whose rows are $\pi$;
4. if $\mu$ is any probability distribution, then $\mu P^n\to \pi$;
5. the eigenvalue $1$ of $P$ is simple and all other eigenvalues of $P$ have modulus strictly less than $1$.

Proof:  Let $P\in {𝒮}_n$ with $P^m>0$. Put $S=\overline{⟨P⟩}$ and let $I$ be the minimal ideal of $S$. As $I\subseteq S{P}^m$, it follows from Lemma 4 that $I$ consists of positive elements. Thus $P^{\omega }>0$ and so Lemma 5 implies that $P^{\omega }$ is a constant map on ${𝒫}_n$ with image $\pi >0$ its stationary distribution. Proposition 3 then yields that $\pi$ is the unique stationary distribution for $P$, that $P^n\to P^{\omega }$ and that $\mu P^n\to \pi$ for all $\mu \in {𝒫}_n$. Moreover, $P^{\omega }=\Pi$ by Lemma 5.

For the final statement, observe that $${ℝ}^n={ℝ}^n{P}^{\omega }\oplus \ker P^{\omega }=ℝ\pi \oplus \ker P^{\omega }$$ (the last equality by Lemma 5). Moreover, $P$ preserves this direct sum decomposition because $P$ and $P^{\omega }$ commute. Set $V=\ker P^{\omega }$. From the fact that $P^n\to P^{\omega }$, it follows that the powers of the restriction $P{\mid }_V$ of $P$ to $V$ converge to $0$ and hence $P{\mid }_V$ has spectral radius strictly less than $1$. Since the characteristic polynomial of $P$ is the product of $x-1$ and the characteristic polynomial of $P{\mid }_V$, it follows that $1$ is a simple eigenvalue of $P$.

A stochastic matrix $P$ is called irreducible if, for all $i,j$, there exists $k>0$ such that $P_{ij}^k>0$. It is easy to verify that if $P$ is irreducible, then $Q=(1/2)I_n+(1/2)P$ is ergodic, where $I_n$ is the $n\times n$ identity matrix. Observe that $vQ=v$ if and only if $v=vP$ for any vector $v$. This leads to the existence and uniqueness of stationary distributions for irreducible Markov chains.

Corollary 7  Let $P$ be an irreducible stochastic matrix. Then $P$ has a unique stationary distribution $\pi$. Moreover, $\pi$ is strictly positive and every fixed vector of $P$ is a multiple of $\pi$.