23
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ 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 $\endgroup$ – Jeff Schenker Jun 27 '13 at 4:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 27 '13 at 5:48
  • 2
    $\begingroup$ @JeffSchenker The determinant of the graph Laplacian is actually 0. $\endgroup$ – Jernej Jun 27 '13 at 9:23
  • $\begingroup$ @JeffSchenker As Jernej has pointed out, not the Laplacian itself, but any order $n-1$ principal sumbatrix thereof. $\endgroup$ – Felix Goldberg Jun 27 '13 at 9:53
  • $\begingroup$ @Feliz and Jernej, thanks for pointing this out. you are of course correct. $\endgroup$ – Jeff Schenker Jun 27 '13 at 13:37
23
$\begingroup$

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:

excerpt from Biggs: Algebraic Graph Theory

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Tyler Streeter Mar 23 '16 at 20:20
  • $\begingroup$ @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 $\endgroup$ – Jernej Mar 23 '16 at 20:25
  • $\begingroup$ 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? $\endgroup$ – Tyler Streeter Mar 23 '16 at 21:10
  • $\begingroup$ 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. $\endgroup$ – Tyler Streeter Mar 23 '16 at 22:28
  • $\begingroup$ @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. $\endgroup$ – Jernej Mar 23 '16 at 23:48
11
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.