Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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

share|improve this answer
    
Good point. What if we remove the restriction that the graphs are unweighted - that way, $A^{-1}$ might still represent a graph (possibly with negative edge weights)? –  GMB Oct 11 '12 at 20:59

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

share|improve this answer

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

share|improve this answer

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.