When does the adjacency matrix of a graph have an eigenvalue zero?

Question

When does the adjacency matrix $A$ of an undirected graph $G$ not have full rank? Is there any intuition to understanding this?

Recall that the adjacency matrix of a graph (without parallel edges) is obtained by labeling the vertices and forming the $0-1$ matrix where $a_{i,j}=1$ if and only if thee is an edge from the $i$-th to the $j$-th vertex.

Answer 1

See the paper by Irene Sciriha, A characterization of singular graphs, Electronic Journal of Linear Algebra, Volume 16, pp. 451-462, December 2007.

Its abstract reads:

Characterization of singular graphs can be reduced to the non-trivial solutions of a system of linear homogeneous equations $Ax=0$ for the $0-1$ adjacency matrix $A$. A graph $G$ is singular of nullity $\eta(G)\ge 1$, if the dimension of the nullspace $\operatorname{ker}(A)$ of its adjacency matrix $A$ is $\eta(G)$. Necessary and sufficient conditions are determined for a graph to be singular in terms of admissible induced subgraphs.

I've had a look at the paper, and can't see any simple way to summarize what's in it.

But this paper is freely available online. If the link stops working go to https://repository.uwyo.edu/ela/, or any resource that has the journal, and navigate to the volume specified above.

Answer 2

Simply, if an undirected graph $G$ has an isolated vertex $v$, i.e. a vertex with no neighbors, then the adjacency matrix $A$ has a zero column (and zero row, since the adjacency matrix of an undirected graph is symmetric), which implies that the determinant of $A$ is zero, which means $\lambda = 0$ is an eigenvalue of the adjacency matrix.