When a directed graph is represented in matrix form, what is the interpretation of the inverse of this matrix? Let $G$ be a directed (unweighted) graph with $n$ nodes.  We can represent $G$ with an $n \times n$ binary matrix $A$, with $A_{ij} = 1$ if there is an edge $i \to j$ and $A_{ij} = 0$ otherwise.
Assuming $A$ is nonsingular, does $A^{-1}$ have any nice interpretation in the world of graphs?
 A: Assuming $A$ is non-singular and further assuming that $A^{-1}$ is also the adjacency matrix of some graph, we can show that each vertex of the graph must have precisely one in-degree and one out-degree. Let $G(A)$ denote the graph of $A$ and similarly for $G(A^{-1})$.
Each vertex of $G(A)$ must have at least one in-degree and out-degree. Otherwise the the corresponding column/row would be all zero and the matrix would be singular.
We interpret the entries of the adjacency matrix as the number of walks. $AA^{-1}$ would be interpreted as concatenated walks with the first edge taken in $G(A)$ and the second in the graph of $G(A^{-1})$. In particular this means that for every edge in the graph of $A$, there must be an edge of the reverse direction in $G(A^{-1})$. If this was not the case, then suppose $u$ is connected to $v$ in $G(A)$ and $v$ is not connected to $u$ in $G(A^{-1})$. Then there exists an edge from $v$ to some $w\neq v$ in $G(A^{-1})$. But then the entry $(u,\ w)$ will be non-zero in $AA^{-1}$ contradicting the fact that it's the identity. By symmetry, this means that the edges of $G(A)$ and $G(A^{-1})$ are identical, except for a reversal in direction.
If some $u$ in $G(A)$ had out-degree greater than two, then there would exist $2$ or more walks back to $u$ in $AA^{-1}$. A symmetrical argument shows the result for in-degrees. It follows that the only graphs which have such adjacency matrices are directed cycle graphs (or unions of such).
A: The determinant of 
$$ 0 1 1 $$
$$ 1 0 1 $$
$$ 1 1 0 $$
is $2$. Thus the inverse matrix has a determinant of $\frac{1}{2}$, which means it cannot be directly associated with a graph....
The cofactor matrix though has integral entries, but in general some will be negative...
A: Not quite what you asked for, but perhaps this will help.  Suppose $A$ is nilpotent (which is true iff the graph is acyclic).  Then $(I-A)^{-1} = \sum_{j=0}^\infty A^j$ so $(I-A)^{-1}_{ij}$ is the number of paths in the graph from $i$ to $j$.  
