Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In graph theory, we work with adjacency matrices which define the connections between the vertices. These matrices have various properties in themselves. For example, their trace can be calculated (it is zero in the case of a non-recursive graph). 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 form a user-friendly interpretation of determinants in the context of networks or graphs. I would be grateful for any assistance.

share|improve this question
5  
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
1  
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
1  
@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
add comment

2 Answers 2

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 $K_2$. Then $$\det(A) = \sum_{H} (-1)^{r(H)} 2^{s(H)}$$ where the sum is over all spanning subgraphs 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$.

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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