# Determinants in Graph Theory

In graph theory, we work with adjacency matrices which define the connections between the vertices. These matrices have various linear-algebraic properties. For example, their trace can be calculated (it is zero in the case of a loopless graph, i.e., an irreflexive symmetric binary relation). And we can also calculate their determinants.

How would you interpret the determinant in the context of a graph? For example, I teach network theory and the calculation of 'eigenvector centrality' requires the use of determinants. But the general question always comes up: what does the determinant mean in the context of the network (or graph)? Does it tell me of a property of the network that is useful?

In essence, I am trying to find a user-friendly interpretation of determinants in the context of networks or graphs. I would be grateful for any assistance.

• This is not quite what you are asking, but the determinant of the graph Laplacian counts the number of spanning trees. This is known as Kirchhoff's matrix tree theorem: en.wikipedia.org/wiki/Kirchhoff's_theorem – Jeff Schenker Jun 27 '13 at 4:34
• You may be interested in Frank Harary, The determinant of the adjacency matrix of a graph, SIAM Review, Vol. 4, No. 3. (Jul., 1962), pp. 202-210, which I found at yaroslavvb.com/papers/harary-determinant.pdf If you have access to Math Reviews online, you might look for papers which cite this one. – Gerry Myerson Jun 27 '13 at 5:48
• @JeffSchenker The determinant of the graph Laplacian is actually 0. – Jernej Jun 27 '13 at 9:23
• @JeffSchenker As Jernej has pointed out, not the Laplacian itself, but any order $n-1$ principal sumbatrix thereof. – Felix Goldberg Jun 27 '13 at 9:53
• @Feliz and Jernej, thanks for pointing this out. you are of course correct. – Jeff Schenker Jun 27 '13 at 13:37

Let $G$ be a graph with adjacency matrix $A$. Let $s(G)$ be the number of connected components of $G$ that are cycles and $r(G)$ the number of connected components that are either $K_2$ or even cycles. Then $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs $H$ of $G$ that have only $K_2$ and cycles as their connected components.

In particular if $T$ is a tree the determinant of its adjacency matrix is $\pm$ the number of perfect matchings of $T$.

A relevant passage from N. Biggs: Algebraic Graph Theory. Second Edition. Cambridge University Press, is: This identity can be generalized to all other coefficients of the characteristic polynomial of $A.$ For more information check the chapter "Determinant expansions" of Biggs' book on algebraic graph theory.

• Looking at Biggs (chapter "Determinant expansions"), and also the original Harary 1962 paper referenced there, it seems that $r(H)$ represents the number of even components, not the number of $K_2$ components as you describe here. Is that correct? – Tyler Streeter Mar 23 '16 at 20:20
• @TylerStreeter That's right r(H) has a different meaning in general (the rank of H). In this case the function is simplified since we only evaluate it for the specific class of graphs – Jernej Mar 23 '16 at 20:25
• Even in this specific class of graphs (i.e. spanning subgraphs of $G$ having only $K_2$ and cycles as components), I think $r(H)$ here should be (congruent to, mod 2) the number of even components, not the number of $K_2$ components. Or am I missing something? – Tyler Streeter Mar 23 '16 at 21:10
• To rephrase my comments: in both the Biggs and Harary references, it appears that the expression involves $(-1)$ raised to the power "number of even components," not "number of $K_2$ components." So the description above appears incorrect, unless I'm missing something. – Tyler Streeter Mar 23 '16 at 22:28
• @TylerStreeter Yes, you're right about the references. I am not sure at this point how I got to the presented definition of $r(H)$ and at this point its safer to just edit the post to use the number of even cycles. – Jernej Mar 23 '16 at 23:48

If your graph is directed and each edge has weight $1$ then the determinant counts the number of not-necessarily-connected-cycles (that is subgraphs being disjoint unions of connected cycles) passing through every vertex of the graph. The cycle is counted as $-1$ if the number of its components has different parity than the number of vertices of the graph, otherwise it is counted as $1$.