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?

  • 3
    $\begingroup$ "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? $\endgroup$ – D.W. Oct 9 '15 at 5:14
  • $\begingroup$ @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?" $\endgroup$ – Omar Shehab Oct 9 '15 at 5:21
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Oct 9 '15 at 5:22
  • $\begingroup$ @D.W., I just found that the General linear group over $\mathbb{Z}$ is what I should be studying. $\endgroup$ – Omar Shehab Oct 9 '15 at 5:35
  • 1
    $\begingroup$ @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). $\endgroup$ – Morgan Rodgers Oct 16 '15 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.