Is there a way/algorithm to determine if there is a cycle in a graph if I only have the adjacency matrix and can not visualize the graph?
$\endgroup$ 31 Answer
$\begingroup$Let the vertices of $G$ be labelled $v_1,\ldots,v_n$, and the adjacency matrix of $G$ be $A$ with row/column $i$ of $A$ correspond to $v_i$.
If you want a purely linear algebraic approach (albeit non-constructive), consider $L=D-A$, where $D$ is the diagonal matrix with $(D)_{i,i}=\deg(v_i)$. This matrix is called the Laplacian matrix of $G$. A basic fact is that the number of times zero appears as an eigenvalue of $L$, i.e., $n-\text{rank}(L)$, is the number of connected components of $G$.
Claim: $G$ is acyclic if and only if $\text{trace}(L)=2\text{rank}(L).$
Equivalently, $G$ has a cycle if and only if $$\text{trace}(L)\geq2(\text{rank}(L)+1).$$
Proof: $G$ is acyclic if and only if it is a forest, i.e., $G$ has $c$ components and exactly $n-c=\text{rank}(L)$ edges. On the other hand, by the Handshaking Lemma we have $|E(G)|=\frac{1}{2}\text{trace}(L)$. The claim follows.
$\endgroup$ 4
