# Which graphs do have invertible adjacency matrices?

I would like to know if there is any class of graphs for which the adjacency matrices are invertible. At this moment I am aware of only the class of graphs $n K_2$ which is the disjoint union of $n$ number of $K_2$ matrices where the adjacency matrices are self-inverse.

Are there any other classes?

• – Bach Nov 12 '15 at 10:43

## 1 Answer

Given a permutation $\pi$ of a finite set $V$, form its cycle graph $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$ for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency matrix will in fact be the permutation matrix corresponding to $\pi$, which is invertible.

We can also form graphs with loops whose adjacency matrices are upper triangular: take the vertex set $\{1,\cdots,n\}$ and adjoin edges $i\to j$ as one wishes but only when $i\le j$ (and of course make sure every vertex has at least one loop).

• Are there any other classes? – Omar Shehab Oct 7 '15 at 17:30
• @OmarShehab Yes, for instance $[\begin{smallmatrix}2 & 1 \\ 1 & 1 \end{smallmatrix}]$. A complete classification would seem to characterize all invertible matrices with nonnegative integer entries, and I am not aware of such a characterization (although I haven't looked). My guess is it'd be unlikely there is a strictly graph-theoretic characterization of these graphs, but you'd have to ask a graph theorist to be more confident. – whacka Oct 7 '15 at 17:39
• Just asked a supplementary question at cstheory.stackexchange.com/questions/32743/… – Omar Shehab Oct 7 '15 at 17:41
• @OmarShehab I don't know what the term in graph theory would be or if there is one (it would seem the term "cycle graph" that graph-theorists use is a more restrictive notation), but I'm almost certain I have seen the term "cycle graph of a permutation" used for this construction in the theory of combinatorial species (a mixture of combinatorics, permutation group theory and category theory). – whacka Oct 7 '15 at 23:36
• The cycle graph of a permutation, specifically, is what I defined in my answer, yes. – whacka Oct 8 '15 at 3:18