Adjacency matrices of graphs, binary trees and the Farey tree

Viewing graph energy as a function from rational numbers to algebraic integers

The adjacency matrix A(\Gamma) of a graph \Gamma is a symmetric matrix with 0’s on the main diagonal and 0’s or 1’s elsewhere. A(\Gamma), and therefore \Gamma is uniquely determined by the upper triangular entries a_{i,j} with j > i. For a graph with n vertices there are \frac{1}{2}n(n-1) such entries and we can arrange them as a single vector of 0’s and 1’s of length \frac{1}{2}n(n-1): (a_{1,2}, a_{1,3}, a_{1,4}, \ldots,a_{1,n}, a_{2,3}, a_{2,4},\ldots, a_{2,n},a_{3,4}, \ldots, a_{3,n}, \ldots, a_{n-1,n}).

This vector of 0’s and 1’s uniquely determines the symmetric adjacency matrix and so uniquely determines the graph \Gamma.

We can view a vector of 0’s and 1’s as determining a unique position in the infinite binary tree. We navigate the infinite binary tree by making a left move from any node if we are at a 0 in the sequence of 0’s and 1’s (starting from the left) and by making a right move if we are at a 1 in the sequence of 0’s and 1’s.

For example, the graph:

with adjaceny matrix \left(\begin{array}{c c c c } 0 & 1 & 0& 1\\ \ 1 & 0 & 1& 0 \\ \ 0 & 1 & 0 & 1 \\ \ 1 & 0 & 1& 0\end{array}\right) , gives the sequence (1,0,1,1,0,1) which corresponds to the bottom node shown below on the infinite binary tree:

We can conveniently, think of this node as representing the dyadic number 0.10111= \frac{23}{32}. Because the sequences of 0’s and 1’s we obtain from the upper triangular portion of the adjacency matrix of a graph are finite, we obtain in this way, dyadic fractions – that is fractions between 0 and 1 whose numerators are a power of 2. We can view the tree of dyadic rationals as follows:

We do not obtain all dyadic fractions in this way, without some reflection. For example, the dyadic fraction \frac{11}{16} is the dyadic number 0.1011 which corresponds in the binary tree to the binary sequence (1,0,1,1). Because this sequence is of length 4, which is not a triangular number – that is, of the form \frac{1}{2}n(n-1) – it does not come from the adjacency matrix of a simple graph. However, we can rectify this situation by appending as many 0’s to the sequence (1,0,1,1) as needed until we do obtain a sequence whose length is a triangular number. For example, the smallest triangular number greater than or equal to 4 is 6, so we add two 0’s to the sequence (1,0,1,1) to get (1,0,1,1,0,0). This sequence corresponds uniquely to the matrix \left(\begin{array}{c c c c } 0 & 1 & 0& 1\\ \ 1 & 0 & 1& 0 \\ \ 0 & 1 & 0 & 0 \\ \ 1 & 0 & 0 & 0\end{array}\right) , and so to the graph:

If we add as many 0’s as we require to get to the smallest triangular number greater than or equal to the length of the dyadic number corresponding to a dyadic rational , then we will have a well-defined procedure for mapping any dyadic rational, in the interval (0,1), back into a unique sequence of 0’s and 1’s whose length is a triangular number. In this way we obtain a one-one correspondence between simple graphs and dyadic fractions greater than 0 and less than 1.

Now we can match rationals between 0 and 1 with dyadic rationals by using the Farey tree and Minkowski’s question mark function. The Farey construction of the rational numbers consists of the fractions between 0 and 1 generated recursively as follows: the initial sequence of rationals is (\frac{0}{1},\frac{1}{1}); At each step a new sequence is constructed by forming the mediant of neighboring fractions in the previous sequence. The mediant of two fractions \frac{p}{q}, \frac{r}{s} is \frac{p+r}{q+s}. So the next sequence is (\frac{0}{1}, \frac{1}{2},\frac{1}{1}) and the following sequence is (\frac{0}{1}, \frac{1}{3},\frac{1}{2}, \frac{2}{3},\frac{1}{1}). Following this construction, the entire set of rational numbers between 0 and 1 can be arranged in a tree with two initial nodes 0 and 1, with each fraction placed in the tree immediately below its lowest mediant progenitor:

Utilizing the identical stucture of the Farey tree and the binary tree, Minkowski’s question mark function, denoted ?, maps the fractions between 0 and 1, inclusive, onto the dyadic rationals. An inductive definition of ? goes as follows: ?(0) = 0, ?(1) = 1 and ?(\frac{p+r}{q+s}) =?(\frac{p}{q})+?(\frac{r}{s}), where \frac{p+r}{q+s} is the mediant of \frac{p}{q} and \frac{r}{s}.

Minkowski’s question mark function is a a continuous and monotonically increasing function from the set of rational numbers between 0 and 1 to the set of dyadic rationals between 0 and 1. It’s graph looks as follows:



So now we can uniquley match any rational number strictly between 0 and 1 with a dyadic rational number strictly between 0 and 1; we can match the dyadic rational with a unique sequence of 0’s and 1’s whose length is a triangular number; we can match each such sequence with a symmetric matrix of 0’s and 1’s with 0’s on the main diagonal; we can match such matrices with simple graphs; and vice versa. So by this procedure we have matched each simple graph with one and only one rational number between 0 and 1 and each rational number with one and only one graph.

As a result, any function defined for all graphs can be regarded as a function defined on the rational numbers. In particular, we can view the energy of a graph as a function defined on the rational numbers in the interval (0,1) and taking values in the ring of algebraic integers.

Isomorphic graphs, which give row-permuted adjacency matrices, will generally give different dyadic rationals and so different rational numbers, under this correspondence.

For computational purposes the recursive definition of the Minkowski question mark function can be replaced by the alternative definition that comes from the finite continued fraction for a rational number in the interval \lbrack 0,1 \rbrack: if the rational number x has the finite continued fraction \lbrack a_1,a_2,\ldots,a_n\rbrack then ?(x) = 2\sum_{k=1}^n(-1)^{k-1} 2^{-(a_1+\ldots+a_n)} (Reference: minkowski_question_mark_function – although notice that Linas Vepstas gets the power of -1 wrong: it should be (-1)^{k-1} and not (-1)^k).

For example, \frac{7}{9}=\lbrack1,3,2\rbrack so?(\frac{7}{9})= 2(\frac{1}{2}^1- \frac{1}{2}^{1+3} +\frac{1}{2}^{1+3+2}) =\frac{29}{32} =0.11101_2. The base 2 string of digits of ?(\frac{7}{9}) has length 5, which is not a triangular number, so we add an extra 0 to get the binary string 111010. This corresponds to the matrix \left(\begin{array}{c c c c } 0 & 1 & 1 & 1\\ \ 1 & 0 & 0 & 1 \\ \ 1 & 0 & 0 & 0 \\ \ 1 & 1 & 0 & 0\end{array}\right) and so to the graph:

with energy \approx 4.96239.

Here is a plot of the energy for the dyadic rationals \{\frac{a}{2^{10}}\vert a = 1,\ldots,2^{10}-1\}:

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s