Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 16 / 1 / b

Write $W_n(i,j)$ for the number of locally admissible words $(x_0,\dots ,x_n)$ with $x_0=i$ and $x_n=j$. Here local admissibility means $A_{x_r{x}_{r+1}}=1$ for each consecutive pair; length counts symbols, so there are $n$ transitions. For $n=0$, the single-symbol word gives $W_0(i,j)={\delta }_{ij}=(A^0{)}_{ij}$, and for $n=1$ we have $W_1(i,j)=A_{ij}$.

To append the last symbol $j$, choose the penultimate symbol $k$. Every choice gives a locally admissible word exactly when its length-$n$ prefix is locally admissible and $A_{kj}=1$. Different prefixes or penultimate symbols give different words, and every admissible word is obtained once. ThereforeThis is precisely the rule for matrix multiplication. Mathematical induction consequently givesEquivalently, expanding the matrix entry sums the products $A_{i{x}_1}{A}_{x_1{x}_2}\cdots A_{x_{n-1}j}$ over all intermediate symbols; each product is the indicator function of one allowed transition chain.

The intended meaning of “allowed” here is local admissibility. If instead it means a word that actually occurs in some two-sided sequence in ${\Sigma }_A$, the assertion needs an additional extension assumption. For example, $A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ and has $(A{)}_{12}=1$, but ${\Sigma }_A$ is empty because no symbol can continue after $2$. Having a nonzero entry in every row and every column is sufficient: one can successively choose a predecessor and a successor to extend every locally admissible word indefinitely in both directions. No such assumption is needed for the local counting formula.