Matrix products and walks in graphs

Section 2.1 Matrix products and walks in graphs

Here we investigate the combinatorial meaning of matrix multiplication.

Subsection 2.1.1 Theory

Theorem 2.1.1. Matrix products.

Let \(A_1,\dots,A_d\) be a sequence of matrices such that the product \(A_1A_2 \cdots A_d\) is defined. Let \(A[i,j]\) denote the entry of the \(i\)-th row and \(j\)-th column of the matrix \(A\text{.}\) We will switch back to the more usual \(A_{i,j}\) when our matrices are not themselves subscripted.

Then

\begin{align*} (A_1A_2 \cdots A_d)[i_0,i_d] \amp= \sum_{i_1,\dots,i_{d-1}} \prod_{k = 1}^{d} A_k[i_{k-1},i_k] \\ \amp= \sum_{i_1,\dots,i_{d-1}} A_1[i_0,i_1] A_2[i_1,i_2] \cdots A_d[i_{d - 1}, i_d]. \end{align*}

Where the sum is over the respective dimensions of \(A_1,\dots,A_d\text{.}\)

Proof.

For \(d = 2\text{,}\) we have, as a standard identity of matrix multiplication,

\begin{equation*} (AB)[i,k] = \sum_j A[i,j]B[j,k]. \end{equation*}

Now suppose this identity holds for every product of \(d\) matrices. Let \(A_1,\dots,A_{d + 1}\) be \(d + 1\) matrices for which the product \(A_1 \cdots A_{d + 1}\) is defined.

Using the \(d = 2\) case, and induction, we have

\begin{align*} ((A_1 \cdots A_d)A_{d + 1})[i_0, i_{d + 1}] \amp = \sum_{i_d} (A_1 \cdots A_d)[i_0,i_d] A_{d+1}[i_d, i_{d+1}]\\ \amp = \sum_{i_d} \left( \sum_{i_1,\dots,i_{d-1}} \prod_{k = 1}^{d} A_k[i_{k-1},i_k] \right)A_{d+1}[i_d, i_{d+1}]\\ \amp = \sum_{i_1,\dots,i_{d}} \prod_{k = 1}^{d+1} A_k[i_{k-1},i_k] \end{align*}

The claim follows by induction.

We will see this most often when \(A\) is a square matrix and \(A_1 = \dots = A_d = A\text{.}\)

Corollary 2.1.2. Walks in digraphs.

Let \(A\) be the adjacency matrix of a digraph \(G\text{.}\) Then \((A^n)_{i,j}\) is the number of walks from vertex \(i\) to vertex \(j\) of length \(n\text{.}\)

Proof.

Applying the previous theorem,

\begin{equation*} (A^n)_{i,j} = \sum_{v_1,\dots,v_{n-1}} A_{i,v_1} A_{v_1, v_2} \cdots A_{v_{n-1}, j}. \end{equation*}

But by definition, \(A_{u,v} = 1\) if and only if there is an arc \(u \to v\) and otherwise it is \(0\text{.}\)

Thus, the product \(A_{i,v_1} A_{v_1, v_2} \cdots A_{v_{n-1}, j}\) is \(1\) if and only if there is a walk \(i \to v_1 \to v_2 \to \dots \to v_{n-1} \to j\text{.}\) Otherwise the product is \(0\) and the result follows.

Example 2.1.3. Fibonacci Sequence.

Let us count the number of ways \(f(n)\) in which we can write \(n\) as a sum of \(1\)'s and \(2\)'s where order matters. Equivalently, take such a sum like \(1 + 1 + 2 + 1 + 2\) and remove the \(+\) signs to write it as a string \(11212\text{.}\) Now replace \(1\) by \(0\) and \(2\) by \(11\text{.}\) This ensures the strings always have length \(n\text{.}\)

E.g. for \(n = 5\text{,}\) these strings are (before and after replacement)

\begin{equation*} 11111, 1112, 1121, 1211, 2111, 122, 212, 221; \end{equation*}

\begin{equation*} 00000, 00011, 00110, 01100, 11000, 01111, 11011, 11110. \end{equation*}

Thus \(f(5) = 8\text{.}\) By construction, the \(1\)'s always appear in a pair in the second set of strings.

Directed graph associated with the Fibonacci sequence — Figure 2.1.4. Directed graph for Example 2.1.3

Now consider a directed graph \(G\) with two vertices named \(q_0\) and \(q_1\) and arcs \(q_0 \to q_1, q_1 \to q_0\) both labeled '\(1\)' and a loop \(q_0 \to q_0\) labeled '\(0\)'. We will start in state \(q_0\) and read the string from left to right following the arc whose label matches the next character in the string. This digraph is set-up precisely so that when we read the first '\(1\)' in a pair, we must read a second '\(1\)' immediately next or the walk is invalid.

Let

\begin{equation*} A = \begin{pmatrix} 1 \amp 1 \\ 1 \amp 0\end{pmatrix} \end{equation*}

be the adjacency matrix of \(G\text{.}\)

Applying Corollary 2.1.2, \(f(n)\) is the number of closed walks from \(q_0\) to \(q_0\) of length \(n\) and this is given by \((A^n)_{1,1}\text{.}\) For instance,

\begin{equation*} A^5 = \begin{pmatrix} 8 \amp 5 \\ 5 \amp 3 \end{pmatrix} \implies f(5) = 8. \end{equation*}

More ambitiously, we can obtain a generating function

\begin{align*} F(x) = \sum_{n = 0}^\infty f(n) x^n \amp = \sum_{n = 0}^\infty (A^n)_{1,1} x^n\\ \amp = \left( \sum_{n = 0}^\infty (Ax)^n \right)_{1,1}\\ \amp = ((I_2 - xA)^{-1})_{1,1}. \end{align*}

We can compute this inverse directly over \(\Q(x)\)

\begin{equation*} (I - xA)^{-1} = \frac{1}{1 - x - x^2} \begin{pmatrix} 1 \amp x \\ x \amp 1 - x \end{pmatrix} \end{equation*}