Lesson 8

Transfer matrices also explain why linear recurrence relations appear so often. Let \(A\) be any fixed square matrix, and let \(u\) and \(v\) be fixed column vectors. Consider the sequence \[s_{n}=u^{T}A^{n}v.\] We can write the following formal power series: \[\sum_{n\ge 0}u^{T}A^{n}vx^{n} = u^{T}(I+xA+x^{2}A^{2}+\dotsb)v = u^{T}(I-xA)^{-1}v.\] The entries of the inverse matrix \((I-xA)^{-1}\) are rational functions whose denominators divide \(\det(I-xA)\). Therefore the sequence \(s_{n}\) satisfies a linear recurrence relation with constant coefficients. Informally, the polynomial \(\det(I-xA)\) tells us what recurrence to expect.

For the binary strings above, \[\det\left( I-x \begin{pmatrix}1&1\\ 1&0\end{pmatrix} \right) = \det \begin{pmatrix}1-x&-x\\ -x&1\end{pmatrix} = 1-x-x^{2}.\] This is another way to see the recurrence \(N(n)=N(n-1)+N(n-2)\).