Transition matrix for a subshift ($A_{ij}\in \{0,1\}$)

The adjacency matrix of a directed graph whose vertices are symbols and whose directed edges are the permitted consecutive pairs. Its entries indicate permission. In comparison, the transition matrix of a Markov chain records transition probabilities.

A finite word over an alphabet is locally admissible for a zero-one symbolic transition matrix if every consecutive pair is permitted. Its length counts symbols, so length $n+1$ corresponds to $n$ transitions. The number with endpoints $i,j$ is $(A^n{)}_{ij}$ by matrix multiplication. Local admissibility does not always imply occurrence in a two-sided subshift of finite type: the matrix $\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ but admits no two-sided sequence. If every row and column has a nonzero entry, every locally admissible word extends in both directions.