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.
Best Answer
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.