1
$\begingroup$

I'm currently struggling with this concept for my master's thesis in a computing discipline.

If we have an adjacency matrix for a directed graph, $G$, where $A[i, j] = 1$ indicates a directed edge from $i$ to $j$, and $A[i, j] = 0$ otherwise; is it possible to safely assume (and prove) that if every row and column of the adjacency matrix only adds up to $1$, then the graph $G$ is a cycle or collection of cycles?

That is to say, each row and each column contains only a single occurrence of a $1$, indicating a directed edge. It certainly seems to be the case if I inspect the graphs graphically using graphviz, but I'm struggling to formulate a proof for this.

All help appreciated, including references to articles which may help. I have tried googling, but could not find applicable results.

$\endgroup$
3
$\begingroup$

Such a matrix is a permutation matrix. Every permutation is a product of disjoint cycles, so the graph is indeed a union of disjoint cycles (including loops, if you allow $1$'s on the main diagonal).

Added: You can give a quick direct proof as follows. Given such an adjacency matrix, each vertex of the digraph must have in-degree $1$ and out-degree $1$, and the edge in and edge out of any vertex have only the one endpoint in common. Start at any vertex $v$ and follow the only possible path; the graph is finite, so eventually you must re-enter your path. That cannot happen a vertex $u$ different from $v$, as that make the in-degree of $u$ at least $2$, so you must return to $v$, completing a cycle. If there are any vertices not in the cycle, pick one, and repeat the process. Keep going until all vertices have been incorporated into cycles. If two of the resulting cycles were not disjoint, they would have a common vertex $v$ with in-degree $2$: start at a vertex that’s on one but not the other — the construction guarantees its existence — and follow its cycle to the first vertex $v$, that is shared. And the source vertex of an edge from one cycle to another would have out-degree $2$, which is also impossible. Thus, the graph is a disjoint union of cycles.

$\endgroup$
  • $\begingroup$ Thank you, this helps a lot. There are no 1's on the main diagonal since the application of my research topic does not allow self loops. I will look for a formal reference to support the statement that every permutation represents a product of disjoint cycles (if you have such a reference readily available, this would of course be appreciated; does this go back to group theory concepts, perhaps?). $\endgroup$ – janvdl Jan 19 '15 at 10:37
  • $\begingroup$ @janvdl: Yes, any decent group theory text should have the result. Alternatively, you can give a quick direct proof that doesn’t even mention permutations; I’ll add it to my answer. $\endgroup$ – Brian M. Scott Jan 19 '15 at 16:46
  • $\begingroup$ @janvdl: My pleasure; good luck with the thesis! $\endgroup$ – Brian M. Scott Jan 20 '15 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.