The matrix-tree theorem

When I was an undergraduate graph theory was a subject which seemed to me completely uninteresting and I very consciously chose not to attend a lecture course on the subject. In the meantime I have realized that having become interested in reaction networks I could profit from knowing more about graph theory. One result which plays a significant role is the matrix-tree theorem. It asserts the equality of the number of subgraphs of a certain type of a given graph and a certain determinant. This could be used to calculate numbers of subgraphs. On the other hand, it could be used in the other direction calculate determinants and it is the second point of view which is relevant for reaction networks.

For the first part of the discussion here I follow these notes. If $G$ is an (unoriented) graph then a spanning tree is a connected subgraph which includes all vertices of $G$ and contains no cycles. The graph Laplacian $L$ of $G$ is the matrix for which $L_{ii}$ is equal to the number of edges containing the vertex $v_i$ , $L_{ij}=-1$ if $i\ne j$ and there is an edge joining vertex $v_i$ to vertex $v_j$ and $L_{ij}=0$ otherwise. The first version of the matrix tree theorem, due to Kirchhoff, says that the number of spanning trees of $G$ can be calculated in the following way. Choose any vertex $v_j$ of $G$ and remove the $j$ th row and $j$ th column from $L$ to get a matrix $L_j$ . Then compute the determinant of $L_j$ . Surprisingly the value of the determinant is independent of $j$ . The first version of the theorem can be obtained as a consequence of a second more sophisticated version proved a hundred years later by Tutte. This concerns directed graphs. A vertex $b$ is said to be accessible from $a$ if there is a directed path from $a$ to $b$ . A vertex in a directed graph is called a root if every other vertex is accessible from it. A directed tree is a directed subgraph which contains a root and which, when the orientation is forgotten, is a tree (i.e. it is connected and contains no unoriented cycles). There is then an obvious way to define a spanning rooted tree. To formulate the second version of the theorem we introduce the matrix Laplacian $L$ of the directed graph. If $i=j$ the entry $L_{ij}$ is the number of edges with final vertex $i$ . $L_{ij}=-1$ if $i\ne j$ and there is a directed edge from $v_i$ to $v_j$ . $L_{ij}=0$ if $i\ne j$ and there is no edge connecting $v_i$ and $v_j$ . The statement of the theorem is that the number of rooted trees with root $v_j$ is equal to the determinant of $L_j$ , a matrix derived from $L$ as before. To see that the first version of the theorem follows the second first associate an oriented graph to an unoriented one by putting in oriented edges joining a pair of vertices in both directions whenever they are joined by an edge in the original graph. Then there is a bijection between trees rooted at $v$ in the unoriented graph and oriented trees rootes at $v$ in the oriented graph. On the other hand the two graphs have the same Laplacian since the number of edges ending at a vertex in the oriented graph is the same as the number of edges having that endpoint in the unoriented graph.

What is the connection of all this with reaction networks? Consider a chemical reaction network with only monomolecular reactions and reaction coefficients all equal to one. Then under mass action kinetics the evolution equations for the concentrations are $\dot x=Lx$ , where $L$ is the Laplacian matrix of the network. There is a conserved quantity, which is the sum of the concentrations of all species. A steady state is an element of the kernel of $L$ . The next part of the discussion follows a paper of Gunawardena (PLoS ONE, 7(5), e36321). He allows general reaction constants. The notion of the Laplacian is extended correspondingly. If the network is strongly connected (in the terminology of graph theory) or weakly reversible (in the terminology of chemical reaction network theory) the kernel of the Laplacian matrix is one-dimensional. Thus there is precisely one steady state in each stoichiometric compatibility class. It is moreover possible to compute a vector spanning the kernel of $N$ by graph theoretical methods. This also goes back to Tutte. To get the $i$ th component first take the product of the reaction constants over a rooted tree and then sum these quantities over the rooted trees with root $v_i$ . More generally the dimension of the kernel of $N$ is equal to the number of terminal strong linkage classes. It is also revealed there that the Laplacian corresponds to the matrix $A$ considered by Horn and Jackson. These ideas are also related to the King-Altman theorem of enzyme kinetics. I have the impression that I have as yet only scratched the surface of this subject. I hope I will be able to come back and understand more about it at a later date.

This entry was posted on October 29, 2017 at 4:18 pm and is filed under dynamical systems, mathematical biology. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Hydrobates