3
$\begingroup$

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?

3 Answers 3

3

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

2

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

  • 0
    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)?2012-10-11
1

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