[proofplan] A directed cycle gives a periodic bi-infinite admissible sequence, so the subshift is nonempty. We compare the language $\mathcal{L}_n(\Sigma_A)$ with directed paths of length $n-1$ in the graph of $A$. Strongly connected components separate the graph into recurrent pieces and transient connectors; the transient parts can change the number of admissible words only by polynomial and constant factors, so they do not change the exponential growth rate. Perron-Frobenius growth for nonnegative matrices then identifies this exponential growth rate with $\rho(A)$, and the language-growth formula for subshift entropy gives the result. [/proofplan]

[step:Produce a periodic bi-infinite point from a directed cycle] Let $G_A$ be the directed graph with vertex set $V := \{1,\dots,k\}$ and edge set \begin{align*} E_A := \{(i,j) \in V \times V : A_{ij}=1\}. \end{align*} By hypothesis there are vertices $v_0,\dots,v_{\ell-1} \in V$, with $\ell \in \mathbb{N}$, such that $A_{v_r v_{r+1}}=1$ for $0 \le r < \ell-1$ and $A_{v_{\ell-1}v_0}=1$. Define $x: \mathbb{Z} \to V$ by $x_m := v_r$, where $r \in \{0,\dots,\ell-1\}$ is the unique residue class satisfying $m \equiv r \pmod{\ell}$. Then for every $m \in \mathbb{Z}$, the pair $(x_m,x_{m+1})$ is one of the directed edges along the cycle, so $A_{x_m x_{m+1}}=1$. Hence $x \in \Sigma_A$, and therefore $\Sigma_A \neq \varnothing$. [/step]

[step:Relate words in the language to bi-infinitely extendable directed paths] For $n \in \mathbb{N}$, define the length-$n$ language of $\Sigma_A$ by \begin{align*} \mathcal{L}_n(\Sigma_A) := \{(i_0,\dots,i_{n-1}) \in V^n : \text{there exists } x \in \Sigma_A \text{ with } x_r=i_r \text{ for } 0 \le r \le n-1\}. \end{align*} Every word $(i_0,\dots,i_{n-1}) \in \mathcal{L}_n(\Sigma_A)$ satisfies $A_{i_r i_{r+1}}=1$ for $0 \le r < n-1$, so it is a directed path of length $n-1$ in $G_A$. Conversely, a directed path $(i_0,\dots,i_{n-1})$ belongs to $\mathcal{L}_n(\Sigma_A)$ exactly when it can be extended to a bi-infinite directed path in $G_A$. Let $P_n$ denote the number of all directed paths of length $n-1$ in $G_A$, with the convention $P_1=k$. For $n \ge 2$, entries of $A^{n-1}$ count directed paths with prescribed initial and terminal vertices, and hence \begin{align*} P_n = \sum_{i=1}^{k}\sum_{j=1}^{k} (A^{n-1})_{ij}. \end{align*} Since $\mathcal{L}_n(\Sigma_A)$ consists of some of these paths, we have \begin{align*} |\mathcal{L}_n(\Sigma_A)| \le P_n. \end{align*} [/step]

[step:Reduce the path growth to strongly connected components]Let $C_1,\dots,C_s$ be the strongly connected components of $G_A$. For each $a \in \{1,\dots,s\}$, let $A_a$ be the square submatrix of $A$ whose rows and columns are indexed by the vertices in $C_a$. Let \begin{align*} r := \max_{1 \le a \le s} \rho(A_a). \end{align*} After ordering the components topologically in the condensation directed acyclic graph, the matrix $A$ becomes block upper triangular with diagonal blocks $A_1,\dots,A_s$. Therefore the eigenvalues of $A$ are precisely the union, with algebraic multiplicity, of the eigenvalues of the diagonal blocks. Hence \begin{align*} \rho(A)=r. \end{align*} We now compare $P_n$ with the growth inside the components. A directed path in $G_A$ visits strongly connected components in a nondecreasing order in the condensation graph, and once it leaves a component it cannot return to it. Since there are only $s \le k$ components, such a path decomposes into at most $s$ internal component-paths joined by at most $s-1$ single directed connector edges. By the Perron-Frobenius growth theorem for nonnegative matrices, applied to each nonnegative matrix $A_a$, the exponential growth rate of the total number of internal paths in $C_a$ is $\rho(A_a)$. More precisely, for every $\varepsilon>0$ there exists a constant $M_\varepsilon \ge 1$ such that for every $a \in \{1,\dots,s\}$ and every $m \in \mathbb{N}$, \begin{align*} \sum_{u \in C_a}\sum_{v \in C_a} (A_a^m)_{uv} \le M_\varepsilon (r+\varepsilon)^m. \end{align*} Here we are using the standard Perron-Frobenius growth estimate for nonnegative matrices (citing a result not yet in the wiki: Perron-Frobenius theorem for nonnegative matrices). The number of possible component itineraries is at most $2^s$, because an itinerary is a directed path in the acyclic condensation graph and cannot repeat a component. The number of possible connector edges is at most $k^2$ at each transition. Thus there is a constant $C_\varepsilon>0$, depending only on $A$ and $\varepsilon$, such that \begin{align*} P_n \le C_\varepsilon n^s (r+\varepsilon)^{n-1} \end{align*} for every $n \ge 1$. Since $\varepsilon>0$ is arbitrary, this gives \begin{align*} \limsup_{n \to \infty} P_n^{1/n} \le r. \end{align*} For the reverse inequality, choose a component $C_b$ with $\rho(A_b)=r$. Since $G_A$ contains a directed cycle, $r=\rho(A)>0$ for at least one component, and if $r=0$ then the conclusion below is immediate. For $r>0$, Perron-Frobenius growth applied to $A_b$ gives \begin{align*} \limsup_{m \to \infty} \left(\sum_{u \in C_b}\sum_{v \in C_b}(A_b^m)_{uv}\right)^{1/m}=r. \end{align*} Every internal path in $C_b$ is a directed path in $G_A$, so $P_{m+1}$ is at least this sum. Therefore \begin{align*} \limsup_{n \to \infty} P_n^{1/n} \ge r. \end{align*} Combining the two inequalities, \begin{align*} \limsup_{n \to \infty} P_n^{1/n}=\rho(A). \end{align*}[/step]

[guided]The purpose of this step is to isolate the only part of the graph that can contribute exponential growth. A path may wander through several strongly connected components, but it can never leave a component and later return to it; otherwise the two components would lie in the same strongly connected component. Thus transient movement between components contributes only a bounded number of choices for connectors and only polynomially many choices for how long the path spends in each component. Let $C_1,\dots,C_s$ be the strongly connected components of $G_A$, and let $A_a$ be the adjacency submatrix of $A$ restricted to the vertices of $C_a$. The condensation graph, whose vertices are the components and whose directed edges record possible transitions between components, is acyclic. Choose a topological ordering of this condensation graph. With respect to the corresponding ordering of the vertices of $G_A$, the matrix $A$ is block upper triangular, and its diagonal blocks are $A_1,\dots,A_s$. The characteristic polynomial of a block upper triangular matrix is the product of the characteristic polynomials of its diagonal blocks. Hence the spectrum of $A$ is the union of the spectra of the $A_a$, and therefore \begin{align*} \rho(A)=\max_{1 \le a \le s}\rho(A_a). \end{align*} Denote this maximum by $r$. We next bound the total number $P_n$ of all length-$n-1$ directed paths. Fix $\varepsilon>0$. By the Perron-Frobenius growth estimate for nonnegative matrices, applied separately to the finitely many matrices $A_1,\dots,A_s$, there exists $M_\varepsilon \ge 1$ such that for every component $C_a$ and every $m \in \mathbb{N}$, \begin{align*} \sum_{u \in C_a}\sum_{v \in C_a}(A_a^m)_{uv} \le M_\varepsilon (r+\varepsilon)^m. \end{align*} This is the only external spectral input in the proof; it is the standard Perron-Frobenius growth theorem for nonnegative matrices (citing a result not yet in the wiki: Perron-Frobenius theorem for nonnegative matrices). Now take any directed path of length $n-1$ in $G_A$. Its sequence of strongly connected components is an itinerary in the acyclic condensation graph, so it contains no repeated component. Therefore it has length at most $s$. Once the itinerary is fixed, the path consists of internal paths inside those components, connected by single transition edges between successive components. There are at most $2^s$ possible component itineraries and at most $k^2$ choices for each connector edge. The remaining choice is how the total path length is distributed among at most $s$ internal component segments. The number of such length distributions is bounded by a polynomial in $n$ of degree at most $s$. For each fixed distribution of lengths, the Perron-Frobenius estimate bounds the product of internal path counts by a constant times $(r+\varepsilon)^{n-1}$, because the internal segment lengths add up to at most $n-1$. Absorbing the finitely many itinerary choices, connector choices, and the polynomial number of length distributions into a constant $C_\varepsilon>0$, we obtain \begin{align*} P_n \le C_\varepsilon n^s (r+\varepsilon)^{n-1}. \end{align*} Taking $n$-th roots and then the limit superior gives \begin{align*} \limsup_{n \to \infty} P_n^{1/n} \le r+\varepsilon. \end{align*} Since $\varepsilon>0$ was arbitrary, \begin{align*} \limsup_{n \to \infty} P_n^{1/n} \le r. \end{align*} For the opposite inequality, choose a component $C_b$ such that $\rho(A_b)=r$. If $r=0$, the lower bound is automatic. If $r>0$, Perron-Frobenius growth gives \begin{align*} \limsup_{m \to \infty}\left(\sum_{u \in C_b}\sum_{v \in C_b}(A_b^m)_{uv}\right)^{1/m}=r. \end{align*} Every path counted by this sum is also a path in the full graph $G_A$, so it is counted by $P_{m+1}$. Hence \begin{align*} \limsup_{n \to \infty} P_n^{1/n} \ge r. \end{align*} Combining the upper and lower bounds gives \begin{align*} \limsup_{n \to \infty} P_n^{1/n}=\rho(A). \end{align*}[/guided]

[step:Show bi-infinite extendability has the same exponential growth rate] Let $C_b$ be a strongly connected component with $\rho(A_b)=\rho(A)$. Since $\rho(A)>0$, the component $C_b$ contains a directed cycle and every finite directed path inside $C_b$ can be extended to a bi-infinite directed path in $C_b$: from the terminal vertex, strong connectivity gives a path to a cycle, and from a cycle strong connectivity gives a path to the initial vertex for the negative-time extension. Therefore every internal path in $C_b$ of length $n-1$ determines a word in $\mathcal{L}_n(\Sigma_A)$. Hence \begin{align*} |\mathcal{L}_n(\Sigma_A)| \ge \sum_{u \in C_b}\sum_{v \in C_b}(A_b^{n-1})_{uv}. \end{align*} By Perron-Frobenius growth for $A_b$, \begin{align*} \limsup_{n \to \infty} |\mathcal{L}_n(\Sigma_A)|^{1/n} \ge \rho(A_b)=\rho(A). \end{align*} Together with the upper bound $|\mathcal{L}_n(\Sigma_A)| \le P_n$ and the result of the previous step, we obtain \begin{align*} \limsup_{n \to \infty} |\mathcal{L}_n(\Sigma_A)|^{1/n}=\rho(A). \end{align*} [/step]

[step:Apply the language-growth formula for entropy] For a subshift over a finite alphabet, the topological entropy of the shift is given by the language-growth formula \begin{align*} h_{\mathrm{top}}(\sigma)=\lim_{n \to \infty}\frac{1}{n}\log |\mathcal{L}_n(\Sigma_A)|. \end{align*} Equivalently, \begin{align*} h_{\mathrm{top}}(\sigma)=\log\left(\limsup_{n \to \infty}|\mathcal{L}_n(\Sigma_A)|^{1/n}\right). \end{align*} Applying the growth computation from the previous step gives \begin{align*} h_{\mathrm{top}}(\sigma)=\log \rho(A). \end{align*} This proves both that $\Sigma_A$ is nonempty and that its topological entropy is the logarithm of the spectral radius of $A$. [/step]