# Determinant of identity minus adjacency matrix

Let $M$ be the adjacency matrix of a directed graph $G$. Is there any known relation between $\det(\textrm{id}-M)$ and the cycles of $G$?

It is easy to see that if $G$ is acyclic then this determinant is $1$ (because we can take $M$ to be strictly upper triangular). What does this measure in general?

Somewhat related: How to tell if a directed graph is acyclic from the adjacency matrix

Using sage I computed these determinants for all the 9608 directed graphs on $5$ vertices and I found that we have $\det(I-M)=1$ iff $G$ is acyclic. Moreover this is the list of possible determinants together with the number of graphs with such determinant:

[(-48, 1), (-40, 1), (-36, 2), (-32, 6), (-30, 3), (-28, 9), (-27, 1),
(-26, 4), (-25, 4), (-24, 36), (-23, 4), (-22, 18), (-21, 9), (-20, 49),
(-19, 12), (-18, 75), (-17, 23), (-16, 144), (-15, 76), (-14, 124),
(-13, 69), (-12, 361), (-11, 116), (-10, 339), (-9, 290), (-8, 676),
(-7, 294), (-6, 917), (-5, 500), (-4, 1195), (-3, 889), (-2, 1144), (-1,
749), (0, 1166), (1, 302)]

• Note that, up to an overall sign, this determinant is the same as the characteristic polynomial $\det{(M-\lambda \text{ id})}$ evaluated at $\lambda=1$. Consequently this determinant is the same as $\prod_{k}(1-\lambda_k)$. Interestingly, it vanishes if 1 is an eigenvalue. – Semiclassical Aug 15 '14 at 20:31

According to my calculations in sage, there are 11 graphs (out 156) on six vertices such that $\det(I-M)=1$ and exactly two of these eleven are trees. This shows that is is going to be very difficult to determine information about cycles from the value of $\det(I-M)$. (There is nothing special about the value '1' here, for example example there are 35 graphs with $\det(I-M)=0$ and two of these are trees.)
Note that, trees aside, no useful combinatorial interpretation of $\det(M)$ is known, and there seems to be little reason to expect $\det(I-M)$ to work better.
• I was working with directed graphs... If you have an DAG, then you can label the vertices using a topological order and the matrix $I-M$ becomes upper triangular with $1$ in the diagonal. So, it seems that the analysis is a little bit different with directed graphs. – Quimey Aug 18 '14 at 12:35
• Are you trying to decide if a directed graph is acyclic using the value of $\det(I-M)$? That's a different question. – Chris Godsil Aug 18 '14 at 15:47