# Class of all graphs with invertible adjacency matrices

This question is a generalization of the question asked here.

From the answers of the questions, I can list four classes of graphs which have invertible adjacency matrices.

1. The class of graphs $nK_2$
2. Given a permutation $\pi$ of a finite set $V$, its cycle graph $G$ can be defined 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 be the permutation matrix corresponding to $\pi$, which is invertible. The class of all such graphs.
3. Graphs with loops whose adjacency matrices are upper triangular: we 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 we have to make sure every vertex has at least one loop).
4. Graphs with adjacency matrices which are diagonal with non-zero entries

Is there a systematic way to generate the group of all invertible adjacency matrices?

• "Can we formally define a class of all graphs with invertible adjacency matrices?" - Of course you could. Why wouldn't you be able to? You can define anything you like. I don't think I understand your question. What exactly is your question? What are your thoughts, and what is your specific confusion/uncertainty? – D.W. Oct 9 '15 at 5:14
• @D.W., I am afraid I didn't clarify it. The question should have been "Is there a systematic way to generate the group of all invertible adjacency matrices?" – Omar Shehab Oct 9 '15 at 5:21
• I encourage you to edit the question to whatever it should be / should have been. Make sure you define what you mean by "systematic way to generate a group". And do some self-study: e.g., the group of invertible matrices is a standard group with lots written about it. See en.wikipedia.org/wiki/General_linear_group. – D.W. Oct 9 '15 at 5:22
• @D.W., I just found that the General linear group over $\mathbb{Z}$ is what I should be studying. – Omar Shehab Oct 9 '15 at 5:35
• @OmarShehab Even then, you only want symmetric $0$-$1$ matrices with zeroes on the diagonal. You might be better off considering: what would prevent a graph from having an invertible adjacency matrix (hint: consider eigenvalues). – Morgan Rodgers Oct 16 '15 at 16:05