Lagmental Vicfred

A Transfer Matrix Counts Objects with Finite Memory by Vicfred

tags: mathematics, generating functions, recurrences, Lagrange inversion

Local constraints become transitions, and matrix powers concatenate legal states. A small computation will anchor the general statement before the abstraction takes over.

The data

A sequence \((a_n)_{n\ge0}\) becomes a formal series \(A(x)=\sum_{n\ge0}a_nx^n\). Algebra on \(A(x)\) translates recurrences, convolution, and recursive constructions into coefficient identities.

$$ M_{ij}=\#\{\text{legal transitions }i\to j\} $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ a_n=u^{\mathsf T}M^nv $$

Derivation

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ M=\begin{pmatrix}1&1\\1&0\end{pmatrix},\qquad M^n=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Invariant content

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad M_{ij}=\#\{\text{legal transitions }i\to j\},\\[5pt] \mathsf{C}\;&:\quad a_n=u^{\mathsf T}M^nv. \end{aligned} $$

Scope

Formal power series permit algebra without analytic convergence, but substitution and inversion still require the correct constant terms.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] a_n=u^{\mathsf T}M^nv \end{gathered}} $$

The final box is a summary, not a new assumption; the proof still lives in the definitions and the intervening calculation. The source keeps each scope delimiter visible for later inspection.

This article was posted on Fri 22 January 2010. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.