On the invertibility of the adjacency matrix of a graph

Which are the sufficient and necessary conditions for an undirected graph with no self edges (i.e. no loop of length $1$) to have an invertible adjacency matrix?

In this case, the adjacency matrix is symmetric (i.e. $A = A^\top$). Moreover, all the diagonal elements are $0$ and there is a $1$ in both the entries $(i,j)$ and $(j,i)$, with $i\neq j$, if and only if vertices $i$ and $j$ are connected.

A first necessary condition is the following: all vertices must have at least one connection, otherwise the relative row of $A$ is null. But what else?

Solution 1:

As far as I know, there is no "simple" necessary and sufficient condition of $G$ for an invertible adjacency matrix. A few comments:

• A necessary condition that generalizes your "each vertex needs at least one connection" condition is that if $S$ is any subset of vertices of the graph, there are at least $|S|$ vertices in the graph having at least one neighbor in $S$ (including possibly vertices in $S$ itself). This is because the rows of the adjacency matrix corresponding to $S$ need to have at least $|S|$ different columns with a non-zero entry to be independent.

This necessary condition is not sufficient. For example, a $4$ cycle has the expansion property, but a singular adjacency matrix.

• A special case of the above: If $G$ is bipartite with non-singular adjacency matrix, both halves of the bipartition have equal size.

• The property is not in general what is termed "monotone" -- adding edges to an invertible graph can both turn a non-singular matrix into a singular one and vice versa (e.g. closing a path on $3$ vertices to a triangle vs. closing a path on $4$ vertices to a $4$ cycle).

• It's been conjectured that the vast majority of singular adjacency matrices are caused by pairs of vertices having identical neighborhoods (these correspond to pairs of equal rows in the adjacency matrix). In other words, if we look at all graphs on $n$ vertices, then it is believed that $$\frac{|\{G \textrm{ with at least one pair of identical neighborhoods }\}|}{|\{G \textrm{ with singular adjacency matrix }\}|} \rightarrow 1$$ as $n$ goes to infinity. however, this is still an open problem. The numerator is an $O\left(n^2 2^{-n}\right)$ fraction of all $n$-vertex graphs, and the best known result is that the denominator is a $\exp(-n^c)$ fraction of graphs for some small positive $c$ (Vershynin was the first to prove a bound of this form. The current best value of $c$ is due to Ferber and Jain).

Solution 2:

I think a general set of conditions will be hard to come by. To substantiate this claim I make the following negative observation.

The adjacency matrix of any bipartite graph with an odd number of vertices is not invertible.

This follows since the eigenvalues of a bipartite graph are symmetric about $0$, and since there are an odd number of eigenvalues (if the graph has an odd number of vertices) then at least one of these is $0$.

Solution 3:

You may find the following reference useful:

• Sciriha, Irene. "A characterization of singular graphs." Electronic Journal of Linear Algebra 16.1 (2007): 38.

It describes necessary and sufficient conditions for the adjacency matrix of a simple graph to be singular (non-invertible). Be forewarned: these do not appear to be particularly "nice" conditions.

Solution 4:

You might have some luck approaching the problem from the other side and exploring the meaning of properties of an invertible matrix (by the invertible matrix theorem) in terms of properties of the graph described by your adjacency matrix. I agree with Owen that you're unlikely to find an exhaustive general set of conditions, but you may find some graph properties that do guarantee an invertible adjacency matrix and which just might be useful in your particular situation.

To clarify with an example, a promising property of an invertible matrix is that each of the columns must be linearly independent. This obviously imposes restrictions on the connectivity of the underlying graph, which might translate to some well known, or at least properly definable, properties of undirected graphs.