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

Improve this question
$\endgroup$
6
  • 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
    Commented Jun 27, 2013 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
    Commented Jun 27, 2013 at 5:48
  • 2
    $\begingroup$ @JeffSchenker The determinant of the graph Laplacian is actually 0. $\endgroup$
    – Jernej
    Commented Jun 27, 2013 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
    Commented Jun 27, 2013 at 9:53
  • $\begingroup$ @Feliz and Jernej, thanks for pointing this out. you are of course correct. $\endgroup$
    – Jeff Schenker
    Commented Jun 27, 2013 at 13:37

2 Answers 2

Reset to default
28
$\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.

Improve this answer
$\endgroup$
6
  • 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
    Commented Mar 23, 2016 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
    Commented Mar 23, 2016 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
    Commented Mar 23, 2016 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
    Commented Mar 23, 2016 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
    Commented Mar 23, 2016 at 23:48
13
$\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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .