Café Math : Adjacency Matrices of Graphs

Yesterday I rewatched the movie "Good Will Hunting" with Matt Damon. The film is really good, if you haven't saw it yet, go see it. It really is a masterpiece. It tells the story of some genius orphan young man that was detected by a mathematician as he solved problems that were written on a black board at the University where he was employed as a cleaner. By chance there is one second in the film when one can see the problem written on the black board. It is an actual math problem. Not that difficult but by no mean trivial.

I solved it in my head (just the line of reasoning, not the computations of course) and by the end of the movie my friend Alfredo De la Fuente started to talk to me via a social network. As I was excited by the film I started to tell him about the problem. He really enjoyed the film too and was very curious to learn about the problem and how to solve it. We chatted a lot, exploring the properties of adjacency matrices of graphs and the way one can form the generating series of walks from one vertex to another.

As a running example to support our conversation we used the following very simple graph (doing math on a tiny chat window is a bit of a challenge) but we succeeded. Alfredo was extatic to find out that the generating series of walks inside our toy graph was related to the Fibbonacci sequence. This was perfectly coincidental but made the connection with some of our previous conversations on generating series.

I was very impressed when the day after, he came out with a full resolution of the problem, proving that he brilliantly understood every aspects of the method. In what follows, I give a transcription of this memorable conversation, in the hope that you'll enjoy it as much as we did.

Let's consider first a very simple graph with just two vertices, say $1$ and $2$, and two edges, say $b$ and $c$. Where $b$ connects the two vertices while $c$ connects the first vertex to itself forming a loop. The adjacency matrix of this graph is, $$ A = \left[\begin{array}{cc}1 & 1 \\1 & 0\end{array}\right]. $$ By definition, the entries $a_{ij}$ of this matrix are the number of edges (possibly directed) with source $i$ and destination $j$.

A *walk* of length $k$ is a an alternated succession of vertices and edges,
$$
\langle\, x_0, y_1, x_1, \dots, y_n, x_n \,\rangle,
$$
where the $x$'s and the $y$'s are the successive vertices and edges along the walk.

If we denote by $a_{ij}^{(n)}$ the number of those walks of length $n$ from $i$ to $j$, we can arrange them into a matrix and the first interesting property of the adjacency matrix $A$ is that the matrix with coefficients $a_{ij}^{(n)}$ is the $n$-th power of $A$, $$ A^n = \left[\begin{array}{cc}a_{11}^{(n)} & a_{12}^{(n)} \\a_{21}^{(n)} & a_{22}^{(n)}\end{array}\right]. $$ Of course, that property isn't special to our graph and generalizes to any graphs of any sizes.

There are two walks of length zero, namely $\langle\, 1 \,\rangle$ and $\langle\, 2 \,\rangle$, and there are three walks of length one, namely $\langle\, 1, b, 2 \,\rangle$, $\langle\, 2, b, 1 \,\rangle$ and $\langle\, 1, c, 1 \,\rangle$, corresponding to the three different ways to traverse the two edges. \begin{align*} A^0 &=\, \mathrm{I} \,= \left[\begin{array}{cc}1 & 0 \\0 & 1\end{array}\right], \\ A^1 &= A = \left[\begin{array}{cc}1 & 1 \\1 & 0\end{array}\right]. \end{align*} So now, what is the number of walks of length $2$, $3$, $4$, etc... of our graph ? Applying the last principle, a simple computation gives, \begin{align*} A^2 &= \left[\begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array}\right], \\ A^3 &= \left[\begin{array}{cc} 3 & 2 \\ 2 & 1 \end{array}\right], \\ A^4 &= \left[\begin{array}{cc} 5 & 3 \\ 3 & 2 \end{array}\right]\dots \end{align*} In order to convince oneself of the effectiveness of those computations, it is instructive to draw a small picture of the graph and then try to enumerate the list of the associated walks, counting them by their length, their origin and their destination, and then compare the result with the corresponding entries of the above matrices.

Now we want to arrange the sequence of those matrices into a generating series. A generating series of matrices at first, but it turns out that it can be considered a matrix of generating series. $$ W(z) = \mathrm{I} + zA + (zA)^2 + (zA)^3 + \cdots = (\mathrm{I} - zA)^{-1} $$ So what is $W(z)$ ? Well let's do the computation, \begin{align*} (\mathrm{I} - zA)^{-1} &= \left[\begin{array}{cc} 1 - z & -z \\ -z & 1 \end{array}\right]^{-1} \\ &= \frac{1}{1-z-z^2}\left[\begin{array}{cc} 1 & z \\ z & 1 - z \end{array}\right] \end{align*} In the end, well this is it, \begin{align*} W(z) = \left[\begin{array}{cc} \dfrac{1}{1-z-z^2} & \dfrac{z}{1-z-z^2} \\ \dfrac{z}{1-z-z^2} & \dfrac{1- z}{1-z-z^2} \end{array}\right] \end{align*}

Interpretation. To those familiar with generating series, this solution is satisfactory. To those who are not, some explanations are needed. What do we have ? Four rational functions in the matrix $W(z)$. Take the upper left coefficient for example,
\begin{align*}
G(z) = \frac{1}{1-z-z^2}
\end{align*}
It's the generating series of Fibbonacci sequence,
$$
\frac{1}{1-z-z^2} = 1 + z + 2\,z^2 + 3\,z^3 + 5\,z^4 + 8\,z^5 + 13\,z^6
+ \dots
$$
In our case this means that, there is *one* walk of size *zero* (term $1$, read 1 times $z^0$), from the vertex $1$ to itself, *one* walk of length *one* (term $z$, read $1$ times $z^1$), *two* walks of length *two* (term $2\,z^2$), etc... and that in general, there are $F_n$ walks of length $n$ from that vertex to itself, where $F_n$ is the $n^\text{th}$ term of the Fibbonacci sequence.
Let's prove that to see what's going on. From the equation above one gets,
$$
G(z) = 1 + z\,G(z) + z^2\,G(z)
$$
which translates into the following recurrence equations on the coefficients $a_n$.
$$
\begin{cases}
a_0 &= 1, \\
a_1 &= 1, \\
a_n &= a_{n-1} + a_{n-2}
\end{cases}
$$
which gives,
\begin{align*}
a_0 &= 1, &
a_1 &= 1, &
a_2 &= 2, \\
a_3 &= 3, &
a_4 &= 5, &
a_5 &= 8, \\
a_6 &= 13, &
a_7 &= 21, && \text{etc}...
\end{align*}
nothing but the Fibbonacci sequence.
Now what are the other entries ? Well just shifted versions of the Fibbonacci sequence. At the end of the day we have,
$$
A^n = \left[\begin{array}{cc} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{array}\right]
$$

Now we got the idea, let's turn to the somewhat more complicated graph that is drawn on the blackboard in the movie. Its adjacency matrix is, $$ A = \left[\begin{array}{cccc} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 1 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right] $$ Just as before, we compute the matrix of generating series of walks, $$ W(z) = (\mathrm{I} - zA)^{-1} = \left[\begin{array}{cccc} 1 & -z & 0 & -z \\ -z & 1 & -2\,z & -z \\ 0 & -2\,z & 1 & 0 \\ -z & -z & 0 & 1 \end{array}\right]^{-1} $$ An elementary but tiresome computation gives us, \begin{align*} W(z) = \frac{1}{1-z-6\,z^2+4\,z^3} \left[ \begin{array}{cccc} \dfrac{1-5\,z^2}{1+z} & z & 2\,z^2 & \dfrac{z + z^2 - 4\,z^3}{1+z} \\ \\ z & 1 - z & 2\,(z-z^2) & z \\ \\ 2\,z^2 & 2\,(z-z^2) & 1 - z - 2\,z^2 & 2\,z^2\\ \\ \dfrac{z + z^2 - 4\,z^3}{1+z} & z & 2\,z^2 & \dfrac{1-5\,z^2}{1+z} \end{array} \right] \end{align*}

Samuel Vidal posted 2012-03-31 15:19:12

I can't resist talking about a very clever way to compute a given term of the Fibbonacci sequence called binary exponentiation, using the following formula, $$ A^n = \left[\begin{array}{cc} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{array}\right] $$ Suppose we're interested in the value of $F_{100}$, we begin by writing $100$ in binary form, \begin{align*} 100 &= 4 + 32 + 64 \\ &= 2^2 + 2^5 + 2^6 \end{align*} The good thing now is that raising a matrix to successive powers of two is quite simple. We can just write, \begin{align*} A^2 &= A \cdot A, \\ A^4 &= A^2 \cdot A^2, \\ A^8 &= A^4 \cdot A^4 , \dots \end{align*} the result is that, \begin{align*} A^{100} &= A^4 \cdot A^{32} \cdot A^{64} \\ &= \left[ \begin {array}{cc} 5&3\\3&2\end {array} \right] \cdot \left[ \begin {array}{cc} 3524578&2178309\\2178309& 1346269\end {array} \right] \cdot \left[ \begin {array}{cc} 17167680177565&10610209857723 \\10610209857723&6557470319842\end {array} \right] \\ &= \left[ \begin {array}{cc} 573147844013817084101&354224848179261915075 \\354224848179261915075&218922995834555169026 \end {array} \right] \end{align*} And we have, $$ F_{100} = 573147844013817084101. $$

Samuel VIDAL posted 2012-04-01 19:53:33

My friend Alfredo sent me the copy of his Java source code to compute the Fibbonacci numbers using the binary exponentiation algorithm. It can be downloaded here:

[Download Java source code]I used the following implementation from Cassiopeia of the binary exponentiation algorithm,

[Download C# source code]Vincenzo posted 2012-04-29 15:27:13

At last! Someone who understands! Thanks for posting!

Samuel VIDAL posted 2012-04-29 18:42:05

You're welcome Vicenzo ;-)

Christophe Zhang posted 2013-01-25 16:21:02

Actually, the generating series of any adjacency matrix is a rational function (the coefficients of W(z) are all rational functions in the variable z) : using the Trace to represent the linear form \"f_ij(A)=(A)_ij\" and the minimal polynomial of A you prove that the coefficients of f_ij(W)\'s power series follow a linear reccurrence, ie f_ij(W) is a rational function! The minimal polynomial of A even gives us a way to express these rational functions.

Anonymous posted 2013-11-10 09:20:36

Vladimyr Burachynsky posted 2014-01-10 02:54:27

I suspect that, while you are well beyond my level, I have found a set of rectangular matrices or Graphs that are very Strange. Flowers to Tornadoes using a walk along a folded straight line sequence. I was unprepared and have been looking for Help. I work with Maple14 SkyDrive Site below

https://skydrive.live.com/?cid=14A5CDB09AEE4237&id=14A5CDB09AEE4237

Paul posted 2014-05-24 23:24:55

I\'m not a mathematician, not even close. Nevertheless, I have an interest in determining an adjacency matrix for a graph of a certain city\'s streets (all 350 miles of them). I am told that I need it before I can determine the shortest route covering all the streets [with the least amount of duplication], i.e. the Chinese Postman Problem. If someone knows of a computer algorithm that can create such a complex adjacency matrix I would be keen to know of it.

Anyone have a suggestion for this

Generating functions make everything simpler $$\frac{1}{1-z-z^2}$$