Topology of directed graph $G$ with non-singular adjacency matrix

Question

Given a directed graph $G$ with non-singular adjacency matrix,

Q. Is there a directed subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $G$?

Answer 1

There is an edge emanating from any vertex of $G$ because otherwise the corresponding row (or column, according to our convention for forming the adjacency matrix) would be zero. Label the vertices as $v_1,\dots,v_n$. According to the observation just made, for any $i$, we can pick an index $f(i)$ such that there is a directed edge from $v_i$ to $v_{f(i)}$—thus a function $f:\{1,\dots,n\}\rightarrow\{1,\dots,n\}$. There clearly exists an index $k$ and a positive integer $m$ such that $f^{\circ m}(k)=k$ and $k,f(k),\dots,f^{\circ (m-1)}(k)$ are pairwise distinct. Now $v_k,v_{f(k)},\dots,v_{f^{\circ (m-1)}(k)}$ is a directed cycle of $G$.

Update) The OP seems to be asking for a subgraph $H$ which is a disjoint union of directed cycles; and furthermore, contains all vertices of $G$. This harder question asks if every vertex of $G$ belong to a directed cycle. For this to hold, every vertex should belong to a directed cycle. My argument above shows that $G$ admits a directed cycle if no row of its adjacency matrix is zero. To show the stronger result that every vertex of $G$ belongs to a directed cycle, one should exploit the non-singularity of the adjacency matrix. Here is a simple argument based on the Cayley-Hamilton theorem: Denote the adjacency matrix by $A$—the entry $(i,j)$ is $1$ iff there is a directed edge from $v_i$ to $v_j$ ($i,j\in\{1,\dots,n\}$). By the Cayley-Hamilton theorem, there is a linear combination of $n\times n$ matrices $I,A,\dots,A^{n-1}$ which is zero and has $\pm\det(A)\neq 0$ as the coefficient of $I$. Considering entries $(i,i)$ ($1\leq i\leq n$ arbitrary), we deduce that for at least one of the matrices $A,\dots,A^{n-1}$ the entry at that position is non-zero. But if the entry $(i,i)$ of the $m^{\rm{th}}$ power of the adjacency matrix, $A^m$, is non-zero, then $v_i$ must lie on a directed cycle of length at most $m$.

Update 2) I am adding my comments to the solution following OP's request. The solution is really Fedor Petrov's. My solutions above were only partial.

There exist disjoint directed cycles containing all vertices of $G$ if and only if the adjacency matrix, $A$, has non-zero permanent (which is of course the case if the adjacency matrix is non-singular).

Writing $A$ as $[a_{ij}]_{1\leq i,j\leq n}$ where $a_{ij}$'s are non-negative integers, ${\rm{perm}}(A)\neq 0$ iff there exists a permutation $\sigma:\{1,\dots,n\}\rightarrow\{1,\dots,n\}$ with $a_{1\sigma(1)}\dots a_{n\sigma(n)}\neq 0$. The cyclic decomposition of $\sigma$ then yields the desired disjoint cycles. Conversely, any collection of disjoint cycles of the graph $G$ involving all $n$ vertices amounts to a permutation $\sigma$ of $\{1,\dots,n\}$ for which $a_{1\sigma(1)}\dots a_{n\sigma(n)}\neq 0$.

Finally, the OP asked about the algorithmic aspect of this problem. I came across the following from the Theoretical CS Stack Exchange: cstheory.stackexchange.com/a/32887. By Valiant's theorem, the problem of computing the permanent for a binary matrix is #P-complete. But the problem of deciding if ${\rm{perm}}(A)\neq 0$, or more generally, finding a permutation $\sigma$ with $a_{1\sigma(1)}\dots a_{n\sigma(n)}\neq 0$, has a polynomial-time solution because, as the link above outlines, it can be translated into the problem of finding a perfect matching in a bipartite graph.

Answer 2

Well, if $V=\{1,\ldots,n\}$, $(a_{ij})_{1\leqslant i,j\leqslant n}$ is the adjacency matrix, and it is non-singular, then its determinant (considered as a sum over permutations) has a non-zero term $\prod_i a_{i,\sigma(i)}$. It corresponds to a disjoint collection of cycles (these are cycles of the permutation $\sigma$ on $V$) which cover all vertices.