2
$\begingroup$

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.

  • 0
    It can be a little tricky. There was a question here a few days ago about cycle graphs --- just $n$ vertices in a single cycle, $n\ge3$. Turns out in this case that the adjacency matrix has full rank if and only if $n$ is not a multiple of $4$.2012-11-19

1 Answers 1

4

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.