1
$\begingroup$

I am trying to solve a problem that I have but I lack the theoretical knowledge that might be necessary to solve it.

I have a directed graph encoded as an adjacency matrix.

Is it possible to test whether a graph is acyclic just by using algebra (operations/transformations/properties of that adjacency matrix)? Any help greatly appreciated. Thank you.

$\endgroup$
  • 1
    $\begingroup$ If you have a DAG (i.e. Directed Acyclic Graph), then it is acyclic just by definition. $\endgroup$ – dtldarek Oct 3 '13 at 10:46
  • $\begingroup$ You're right, I have a directed graph and I want to check if it is acyclic. Thanks. $\endgroup$ – mr.sverrir Oct 3 '13 at 11:41
0
$\begingroup$

I'm assuming that the graph is just a directed graph, not a DAG.

Let $A$ be its adjacency matrix. The graph is a DAG if and only if each matrix $A^n$, $n > 0$, has only zeroes on the main diagonal. Notation $A^n$ means matrix product of $A$ with itself $n$ times, and it is understood that "multiplication" of individual entries is the logical AND, and "addition" is the logical OR.

So, this test uses "algebra", but it is boolean algebra, not the normal algebra of real numbers. I can't think of a way using the algebra of reals.

Also, the test includes an infinite number of matrices $A^n$, one for each natural $n$. In practice it is enough to check each $n$ from $1$ up to the number of vertices in the graph, inclusive.

$\endgroup$
  • $\begingroup$ Thank you. Do you know if this can be backed by some theorem, perhaps? $\endgroup$ – mr.sverrir Oct 3 '13 at 13:00
  • $\begingroup$ This is almost obvious. You can prove this statement by induction: matrix $A^n$ has $1$ at position $(i,j)$ if there is a path from vertex $i$ to vertex $j$ with $n$ edges, and $0$ otherwise. At $n=1$ this is the definition of adjacency matrix, and the induction step is not difficult either. $\endgroup$ – Dan Shved Oct 3 '13 at 13:13
1
$\begingroup$

This is also assuming your graph is just a (simple) digraph, not necessarily acyclic, and $A$ is defined by setting the $(i,j)$ entry to: $1$ if there is an edge from $i$ to $j$, to $-1$ if there is an edge from $j$ to $i$, and $0$ otherwise.

You can interpret the standard topological sort algorithm using just $A$ as follows: Look for a row with only non-negative entries. If no such row exists, then the graph is not acyclic. Otherwise, delete that row and the corresponding column. Repeat...

$\endgroup$
1
$\begingroup$

In theory, you can use the nice property that the powers $A^k$ of the adjacency matrix tell you how many paths of length $k$ there are from each node to each other node: the graph is acyclic as long as $A^k$ has zeroes along the diagonal for every $k \geq 1$. Furthermore, the matrix exponential $\exp A$ is a positive linear combination of the powers of $A$, so it seems like the graph will be acyclic if and only if $\exp(A) - I$ has zeroes along the diagonal. (You must subtract the identity matrix because the first term of the exponential power series is $A^0 = I$, which is irrelevant here.)

In practice: I believe matrix exponentials are difficult to calculate in general, but there are routines for approximating them.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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