[proofplan] We compare the number of admissible words in the sofic shift with the number of directed paths in the presenting graph. Right-resolvingness gives a uniform bound on the size of each fibre of the label map from paths to words, while essentiality ensures that every finite graph path contributes a word appearing in a bi-infinite point of the shift. Thus word growth and path growth have the same exponential rate. Perron--Frobenius theory for finite non-negative matrices then identifies the exponential growth rate of paths with the spectral radius of the adjacency matrix. [/proofplan]

[step:Define the language and the path-counting functions] For each $m\in\mathbb{N}$, let $\mathcal{L}_m(Y)\subseteq \mathcal{A}^m$ denote the set of length-$m$ words appearing in some point of $Y$. The topological entropy of the subshift $Y$ is \begin{align*} h_{\mathrm{top}}(\sigma|_Y)=\lim_{m\to\infty}\frac{1}{m}\log |\mathcal{L}_m(Y)|. \end{align*} This limit exists by submultiplicativity of the language-counting sequence. Let $\mathcal{P}_m$ denote the finite set of directed paths in $\mathcal{G}$ with exactly $m$ edges. Define the path-counting function \begin{align*} P_m:\mathbb{N}\to\mathbb{N}, \qquad m\mapsto |\mathcal{P}_m|. \end{align*} If $\mathbf{1}\in\mathbb{R}^{V}$ denotes the column vector with every coordinate equal to $1$, then \begin{align*} P_m=\mathbf{1}^{\top}M^m\mathbf{1}. \end{align*} Indeed, the $(u,v)$-entry of $M^m$ counts directed paths of length $m$ from $u$ to $v$, and summing over all ordered pairs $(u,v)\in V\times V$ counts all length-$m$ paths. [/step]

[step:Compare words with paths using right-resolvingness]Define the label map on length-$m$ paths by \begin{align*} \Lambda_m:\mathcal{P}_m\to\mathcal{A}^m \end{align*} by \begin{align*} \Lambda_m(e_1,\dots,e_m):=\ell(e_1)\cdots \ell(e_m). \end{align*} Since $\mathcal{G}$ is essential, every finite path in $\mathcal{G}$ occurs as a subpath of some bi-infinite path in $\mathcal{G}$. To justify this, let $p=(e_1,\dots,e_m)$ be a finite path with initial vertex $u$ and terminal vertex $v$. Essentiality gives a bi-infinite path passing through $u$, so taking its left half up to $u$ gives a left-infinite path ending at $u$. Essentiality also gives a bi-infinite path passing through $v$, so taking its right half starting at $v$ gives a right-infinite path beginning at $v$. Concatenating the left-infinite path, $p$, and the right-infinite path gives a bi-infinite path containing $p$. Hence every word in $\Lambda_m(\mathcal{P}_m)$ appears in a point of $Y$, so \begin{align*} \Lambda_m(\mathcal{P}_m)\subseteq \mathcal{L}_m(Y). \end{align*} Conversely, every word in $\mathcal{L}_m(Y)$ is read along some length-$m$ path in $\mathcal{G}$, so \begin{align*} \mathcal{L}_m(Y)\subseteq \Lambda_m(\mathcal{P}_m). \end{align*} Therefore \begin{align*} \mathcal{L}_m(Y)=\Lambda_m(\mathcal{P}_m). \end{align*} For each word $w\in\mathcal{L}_m(Y)$ and each starting vertex $v\in V$, right-resolvingness implies that there is at most one path in $\mathcal{P}_m$ starting at $v$ and labelled by $w$. Thus each fibre $\Lambda_m^{-1}(\{w\})$ has cardinality at most $|V|$. Hence \begin{align*} |\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)|. \end{align*}[/step]

[guided]The point of this step is to show that labelled word growth and graph path growth differ only by a bounded multiplicative factor. Define \begin{align*} \Lambda_m:\mathcal{P}_m\to\mathcal{A}^m \end{align*} by \begin{align*} \Lambda_m(e_1,\dots,e_m):=\ell(e_1)\cdots \ell(e_m) \end{align*} to be the map that forgets the vertices and remembers only the emitted labels. First, essentiality identifies the image of this map with the language of the shift. If $p=(e_1,\dots,e_m)\in\mathcal{P}_m$, let $u$ be the initial vertex of $e_1$ and let $v$ be the terminal vertex of $e_m$. Essentiality says that $u$ lies on some bi-infinite path, so the part of that path ending at $u$ supplies a left-infinite path ending at $u$. It also says that $v$ lies on some bi-infinite path, so the part of that path beginning at $v$ supplies a right-infinite path beginning at $v$. Concatenating the left-infinite path, the finite path $p$, and the right-infinite path gives a bi-infinite path containing $p$. Therefore $\Lambda_m(p)$ appears as a length-$m$ block in some point of $Y$, so $\Lambda_m(p)\in\mathcal{L}_m(Y)$. This proves \begin{align*} \Lambda_m(\mathcal{P}_m)\subseteq \mathcal{L}_m(Y). \end{align*} The reverse inclusion follows from the definition of the presented shift: if $w\in\mathcal{L}_m(Y)$, then $w$ appears in a bi-infinite label sequence read along a bi-infinite graph path, and the corresponding $m$ consecutive edges form a path $p\in\mathcal{P}_m$ with $\Lambda_m(p)=w$. Hence \begin{align*} \mathcal{L}_m(Y)\subseteq \Lambda_m(\mathcal{P}_m). \end{align*} Thus \begin{align*} \mathcal{L}_m(Y)=\Lambda_m(\mathcal{P}_m). \end{align*} Now we use right-resolvingness. Fix a word $w=a_1\cdots a_m\in\mathcal{L}_m(Y)$ and a starting vertex $v\in V$. Because the graph is right-resolving, there is at most one outgoing edge from $v$ labelled $a_1$. If that edge exists, its terminal vertex is then fixed. From that terminal vertex, there is at most one outgoing edge labelled $a_2$, and continuing inductively, there is at most one length-$m$ path starting at $v$ and labelled by $w$. Since there are exactly $|V|$ possible starting vertices, the fibre $\Lambda_m^{-1}(\{w\})$ has cardinality at most $|V|$. Therefore the total number of paths is bounded by summing these fibre bounds over all words: \begin{align*} P_m=|\mathcal{P}_m|\le \sum_{w\in\mathcal{L}_m(Y)} |V|=|V|\,|\mathcal{L}_m(Y)|. \end{align*} The opposite inequality follows because $\Lambda_m$ maps $\mathcal{P}_m$ onto $\mathcal{L}_m(Y)$, so the number of words cannot exceed the number of paths: \begin{align*} |\mathcal{L}_m(Y)|\le P_m. \end{align*} Combining the two estimates gives \begin{align*} |\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)|. \end{align*}[/guided]

[step:Pass from bounded multiplicative comparison to equal exponential growth] Taking logarithms in \begin{align*} |\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)| \end{align*} gives \begin{align*} \frac{1}{m}\log |\mathcal{L}_m(Y)|\le \frac{1}{m}\log P_m\le \frac{1}{m}\log |\mathcal{L}_m(Y)|+\frac{1}{m}\log |V|. \end{align*} Since $V$ is finite, \begin{align*} \lim_{m\to\infty}\frac{1}{m}\log |V|=0. \end{align*} By the [squeeze theorem](/theorems/627), \begin{align*} h_{\mathrm{top}}(\sigma|_Y)=\lim_{m\to\infty}\frac{1}{m}\log P_m. \end{align*} [/step]

[step:Identify path growth with the spectral radius of the adjacency matrix] We use the finite non-negative matrix growth formula: if $M$ is a finite non-negative matrix and $\mathbf 1^\top M^m\mathbf 1$ is not eventually zero, then \begin{align*} \lim_{m\to\infty}\frac{1}{m}\log \left(\mathbf{1}^{\top}M^m\mathbf{1}\right)=\log \rho(M). \end{align*} This is the standard Perron--Frobenius spectral-radius growth formula applied to the total path-counting functional. The hypotheses are satisfied because $M$ is a finite square matrix with non-negative integer entries, and essentiality together with $Y\neq\varnothing$ ensures that the path-counting sequence is not eventually zero. Since $P_m=\mathbf{1}^{\top}M^m\mathbf{1}$, we obtain \begin{align*} \lim_{m\to\infty}\frac{1}{m}\log P_m=\log \rho(M). \end{align*} Combining this with the previous step yields \begin{align*} h_{\mathrm{top}}(\sigma|_Y)=\log \rho(M). \end{align*} [/step]

[step:Reduce the nonessential case to the essential part] Suppose now that $\mathcal{G}$ is not essential. Let $\mathcal{G}_{\mathrm{ess}}$ be the subgraph consisting exactly of the vertices and edges that occur in some bi-infinite path whose label sequence belongs to $Y$. Removing all other vertices and edges does not change the set of bi-infinite labelled paths, and therefore does not change the presented shift $Y$ or its language $\mathcal{L}_m(Y)$ for any $m\in\mathbb{N}$. The graph $\mathcal{G}_{\mathrm{ess}}$ is essential by construction and remains right-resolving because it is a subgraph of the right-resolving graph $\mathcal{G}$. Applying the essential case to $\mathcal{G}_{\mathrm{ess}}$ and its adjacency matrix $M_{\mathrm{ess}}$ gives \begin{align*} h_{\mathrm{top}}(\sigma|_Y)=\log \rho(M_{\mathrm{ess}}). \end{align*} This proves both assertions. [/step]