19 Transfer Matrix Method
Let \(D\) be a directed graph on the vertices \(1, \dots, n\). The adjacency matrix of \(D\) is the matrix \(A = A(D)\) where \[ A_{ij} = \begin{cases} 1 & \text{if } i \to j \text{ is a directed edge}, \\ 0 & \text{otherwise} \end{cases} \]
These adjacency matrices allow for loop edges \(i \to i\) and can be made to allow for parallel edges if we let \(A_{ij}\) be the number of parallel edges from \(i \to j\).
19.1 Example
Consider the graph
The adjacency matrix of this digraph is \[ A ={} \begin{array}{c c} & \begin{array}{@{} c c c @{}} 1 & 2 & 3 \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \hspace{-1em} & \begin{pmatrix} 0 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix} \\ \mbox{} \end{array} \tag{19.1}\]
For instance, row \(1\) says that vertex \(1\) has edges \(1 \to 2\) and \(1 \to 3\).
19.2 Matrix Multiplication
In linear algebra, we define the product of two matrices \(A\) and \(B\) by \[ (AB)_{ij} = \sum_t A_{it} B_{tj}. \]
Visually, this means we take the \(i\)-th row of \(A\) and take the dot product with the \(j\)-th row of \(B\). For instance, if \(A\) is the adjacency matrix in Equation 19.1, then \[ A_{12} = \begin{pmatrix} 0 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 = 2. \]
This product has a combinatorial meaning: \[ (A^2)_{ij} = \sum_t A_{it}A_{tj} = \sum_t \begin{cases} 1 & \text{if } i \to t \to j \text{ are edges}, \\ 0 & \text{else}. \end{cases} \]
In other words: \(A^2\) gives the number of walks of length \(2\).
Theorem 19.1 If \(A\) is the adjacency matrix for some digraph \(D\), then \((A^n)_{ij}\) is the number of walks of length \(n\) from \(i\) to \(j\).
Proof. We prove this by induction. First, the base case: if \(n = 1\) then \((A^1)_{ij} = A_{ij}\) is by definition the number of walks (single edges) from \(i\) to \(j\).
For the inductive step, we assume that (for every \(i\) and \(j\)) \((A^{n - 1})_{ij}\) counts the number of walks from \(i\) to \(j\) of length \(n - 1\). Then \[ (A^n)_{ij} = (A^{n - 1}A)_{ij} = \sum_t (A^{n-1})_{it}A_{tj}. \] Here, the first factor, \((A^{n-1})_{it}\) counts the number of walks from \(i\) to \(t\) of length \(n - 1\) and \(A_{tj}\) is the number of edges from \(t\) to \(j\). So the whole term \((A^{n-1})_{it}A_{tj}\) counts the number of walks from \(i\) to \(t\) to \(j\). So this is every walk of length \(n\) from \(i\) to \(j\).
19.2.1 Example
For the digraph in Figure 19.1, how many walks are there of length \(3\) from vertex \(1\) to vertex \(2\)? We can do \(1,2,2,2\); or \(1,3,2,2\); or \(1,3,1,2\). So there are \(3\) walks of length \(3\). Therefore, we expect that \(A^3\) will have a \(3\) in row \(1\), column \(2\). Let’s use SageMath to check this.
%display latex
A = Matrix([[0, 1, 1], [0, 1, 0], [1, 1, 0]])
A^3
\(\displaystyle \left(\begin{array}{rrr}
0 & 3 & 1 \\
0 & 1 & 0 \\
1 & 3 & 0
\end{array}\right)\)
Examples of other things this matrix tells us: there are \(0\) walks from \(1\) to \(1\) of length \(3\); there is only \(1\) walk of length \(3\) from \(1\) to \(3\), namely \(1,3,1,3\).
19.3 Generating Functions
Recall that when we started with generating functions, a monomial like \(ax^n\) meant “\(a\) objects of length or size \(n\).” So if we do \(A^nx^n\) then the entries will represent “\((A^n)_{ij}\) walks of length \(n\).” Then the generating function for this is \[\begin{align*} M &= A^0x^0 + A^1x^1 + A^2x^2 + A^3x^3 + \cdots \\ &= I + Ax + A^2x^2 + A^3x^3 + \cdots \\ &= (I - Ax)^{-1} \end{align*}\]
Where we use a similar formula as our geometric series, \(\frac{1}{1-ax}\), except \(a\) is now a matrix.
For the digraph in Figure 19.1, this generating function is
M = (identity_matrix(3) - A*x)^-1
M.simplify_rational()
\(\displaystyle \left(\begin{array}{rrr}
-\frac{1}{x^{2} - 1} & \frac{x}{x^{2} - 2 \, x + 1} & -\frac{x}{x^{2} - 1} \\
0 & -\frac{1}{x - 1} & 0 \\
-\frac{x}{x^{2} - 1} & \frac{x}{x^{2} - 2 \, x + 1} & -\frac{1}{x^{2} - 1}
\end{array}\right)\)
Theorem 19.2 Each entry \(M_{ij}\) of this matrix is the generating function for the number of walks from vertex \(i\) to vertex \(j\).
For instance, the generating function for walks from vertex \(1\) to vertex \(3\) is \[ \frac{x}{1 - x^2} = x + x^3 + x^5 + x^7 + \cdots. \] This agrees with what we can see from the diagram: there is exactly one walk of length \(n\) for any odd number \(n\) and none of even length.
Of course, the true utility of this is when we can’t do the calculation in our heads of the number of walks. For instance, the number of walks from vertex \(1\) to vertex \(2\) of length \(n\) is given by the generating function \[ \frac{x}{1 - 2x + x^2} = \frac{x}{(1 - x)^2} = \sum_{n = 0}^\infty nx^n \] (using the formula from Section 13.4). So there are \(n\) walks of length \(n\).
19.4 Fibonacci
We can use this method to simplify a lot of the work we had to do with state elimination. Have a look at our Fibonacci automaton again, simplified down to \(2\) states.
stateDiagram
direction LR
0 --> 0 : 0
0 --> 1 : 1
1 --> 0 : 0
A valid string is a walk from vertex \(0\) to either vertex \(0\) or vertex \(1\) (depending on the last bit of the string). So we want \(M_{00} + M_{01}\) for the number of walks from vertex \(0\) to vertex \(0\) plus from vertex \(0\) to vertex \(1\).
Here’s how to accomplish that in SageMath. We start with the adjacency matrix
\[ A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \]
Then compute \(M = (I - A)^{-1}\)
A = Matrix([[1, 1], [1, 0]])
I = identity_matrix(2)
M = (I - A*x)^-1
OGF = M[0][0] + M[0][1]
OGF.simplify_rational()
\(\displaystyle -\frac{x + 1}{x^{2} + x - 1}\)
And this matches our answer in Section 18.2.
19.5 Recurrence Relations
With all this matrix algebra, the results we get can get pretty gnarly. Sometimes it’s enough to get a recurrence relation to describe our answer. By Section 18.4, we know that the recurrence is given by the denominator.
We will use now a theorem from linear algebra. ::: {#thm-matrix-inverse} The inverse of a matrix \(A\) is given by \[ A^{-1} = \frac{1}{\det A} \operatorname{Adj}(A) \] where the adjugate matrix \(\operatorname{Adj}(A)\) has entries given by determinants of \(A\) deleting one row and one column. :::
What’s important to us here is that the denominator is \(\det A\). So the denominator of our generating functions is \[ \det(I - Ax) \]
This is related to the characteristic polynomial but with the coefficients reversed.
19.5.1 Example
For our Fibonacci FSA in Figure 19.2, the denominator is
det(I - A*x)
\(\displaystyle -x^{2} - x + 1\)
This tells us the recurrence relation is \[ \begin{array}{cccc} 1 & -1 x & -1 x^2 & \\ \downarrow & \downarrow & \downarrow & \\ a_n & - a_{n - 1} & - a_{n - 2} & = 0 \end{array} \]
Note
In Section 19.3, we saw that some of the denominators were \(1 - x^2 = (1 - x)(1 + x)\) and some were \(1 - x\) and some were \((1 - x)^2\). The denominator we calculate using \(\det(I - Ax)\) is \((1 - x)^2(1 + x) = 1 - x - x^2 + x^3\) leading to the recurrence \(a_n - a_{n - 1} - a_{n - 2} + a_{n - 3}\).
All of the quantities will satisfy the longer recurrence but they also individually satisfy a shorter recurrence which may be different from their siblings.