[proofplan] We prove both directions by translating the dynamics of the shift into paths in the directed graph encoded by $M$. Cylinder sets form the basic open sets in $\Sigma_M$, so topological mixing is equivalent to eventual intersection of shifted cylinders. Primitivity gives admissible connecting blocks of every sufficiently large length between the terminal symbol of one cylinder and the initial symbol of another. Conversely, mixing applied to the active one-symbol cylinders $[i]$ and $[j]$ forces paths of all sufficiently large lengths from $i$ to $j$, which is exactly eventual positivity of the matrix powers. [/proofplan]

[step:Relate matrix powers to admissible paths]For $i,j \in \{1,\dots,m\}$ and $n \in \mathbb{N}$, the entry $(M^n)_{ij}$ is the number of admissible paths of length $n$ from $i$ to $j$, counted with multiplicity through intermediate symbols. More explicitly, \begin{align*} (M^n)_{ij} = \sum_{a_1,\dots,a_{n-1}=1}^{m} M_{i a_1} M_{a_1 a_2} \cdots M_{a_{n-1} j}. \end{align*} Since every factor is either $0$ or $1$, the inequality $(M^n)_{ij} > 0$ is equivalent to the existence of symbols $a_1,\dots,a_{n-1} \in \{1,\dots,m\}$ such that \begin{align*} M_{i a_1} M_{a_1 a_2} \cdots M_{a_{n-1} j} = 1. \end{align*} Equivalently, there exists an admissible word $(b_0,\dots,b_n)$ with $b_0=i$ and $b_n=j$.[/step]

[guided]The matrix $M$ is the adjacency matrix for allowed one-step transitions: $M_{ab}=1$ means that the symbol $b$ may follow the symbol $a$. Therefore a path of length $n$ from $i$ to $j$ is a sequence of symbols \begin{align*} (b_0,\dots,b_n) \in \{1,\dots,m\}^{n+1} \end{align*} with $b_0=i$, $b_n=j$, and $M_{b_{q} b_{q+1}}=1$ for every $q \in \{0,\dots,n-1\}$. The formula for matrix multiplication gives \begin{align*} (M^n)_{ij} = \sum_{a_1,\dots,a_{n-1}=1}^{m} M_{i a_1} M_{a_1 a_2} \cdots M_{a_{n-1} j}. \end{align*} Each summand corresponds to the candidate path \begin{align*} (i,a_1,\dots,a_{n-1},j). \end{align*} Because $M$ has entries in $\{0,1\}$, the product in a summand equals $1$ exactly when every adjacent transition in that candidate path is allowed. Thus $(M^n)_{ij}>0$ exactly means that at least one admissible path of length $n$ connects $i$ to $j$. This is the indexing convention used throughout the proof: powers of $M$ count edges, while finite words have one more symbol than the number of edges.[/guided]

[step:Use primitivity to connect arbitrary cylinders after all large shifts] Assume that $M$ is primitive. Let $U,V \subset \Sigma_M$ be nonempty open sets. Since cylinder sets form a basis for the [product topology](/page/Product%20Topology) on $\Sigma_M$, choose admissible words \begin{align*} u=(u_0,\dots,u_r) \in \{1,\dots,m\}^{r+1} \end{align*} and \begin{align*} v=(v_0,\dots,v_s) \in \{1,\dots,m\}^{s+1} \end{align*} such that the cylinders $[u_0\cdots u_r]$ and $[v_0\cdots v_s]$ are nonempty and satisfy \begin{align*} [u_0\cdots u_r] \subset U, \qquad [v_0\cdots v_s] \subset V. \end{align*} By primitivity, there exists $N_0 \in \mathbb{N}$ such that $(M^\ell)_{u_r v_0}>0$ for every $\ell \geq N_0$. Fix $n \geq r+N_0$. Define $\ell := n-r$. Then $\ell \geq N_0$, so the previous step gives an admissible word \begin{align*} (b_0,\dots,b_\ell) \in \{1,\dots,m\}^{\ell+1} \end{align*} with $b_0=u_r$ and $b_\ell=v_0$. Define a sequence $x \in \{1,\dots,m\}^{\mathbb{N}_0}$ by first prescribing \begin{align*} (x_0,\dots,x_r) := (u_0,\dots,u_r), \end{align*} then \begin{align*} (x_{r+q}) := b_q \quad \text{for } q \in \{1,\dots,\ell\}, \end{align*} and finally \begin{align*} (x_{n+q}) := v_q \quad \text{for } q \in \{1,\dots,s\}. \end{align*} If more symbols are needed after time $n+s$, choose any tail extending the nonempty cylinder $[v_0\cdots v_s]$; this is possible because that cylinder is nonempty. All adjacent transitions in the prescribed sequence are admissible: the word $u$ is admissible, the bridge $b$ is admissible, and the word $v$ is admissible. Hence $x \in \Sigma_M$. By construction $x \in [u_0\cdots u_r] \subset U$ and $\sigma^n x \in [v_0\cdots v_s] \subset V$. Therefore \begin{align*} U \cap \sigma^{-n}(V) \neq \varnothing \end{align*} for every $n \geq r+N_0$. This is precisely topological mixing. [/step]

[step:Apply mixing to active one-symbol cylinders] Conversely, assume that $(\Sigma_M,\sigma)$ is topologically mixing. Fix arbitrary symbols $i,j \in \{1,\dots,m\}$. By the active-symbol hypothesis, the one-symbol cylinders $[i]$ and $[j]$ are nonempty open subsets of $\Sigma_M$. By topological mixing, there exists $N_{ij} \in \mathbb{N}$ such that \begin{align*} [i] \cap \sigma^{-n}([j]) \neq \varnothing \end{align*} for every integer $n \geq N_{ij}$. For each such $n$, choose \begin{align*} x^{(n)} \in [i] \cap \sigma^{-n}([j]). \end{align*} Then $x^{(n)}_0=i$ and $x^{(n)}_n=j$. Since $x^{(n)} \in \Sigma_M$, the finite block \begin{align*} (x^{(n)}_0,\dots,x^{(n)}_n) \end{align*} is an admissible path of length $n$ from $i$ to $j$. By the path interpretation of matrix powers, this implies \begin{align*} (M^n)_{ij} > 0 \end{align*} for every $n \geq N_{ij}$. [/step]

[step:Conclude eventual positivity for every matrix entry] The symbols $i,j \in \{1,\dots,m\}$ were arbitrary. Hence for every ordered pair $(i,j)$ there exists $N_{ij} \in \mathbb{N}$ such that $(M^n)_{ij}>0$ for every $n \geq N_{ij}$. This is exactly the stated primitivity condition for $M$. Combining the primitive-to-mixing direction with the mixing-to-primitive direction proves that $(\Sigma_M,\sigma)$ is topologically mixing if and only if $M$ is primitive. [/step]