¿Cómo saber si un grafo dirigido es acíclico a partir de la matriz de adyacencia?

Question

Supongamos que tenemos una matriz de adyacencia $A$ para un grafo dirigido $G=\{V,E\}$ Así que $A_{ij} = 1$ si $V_i\rightarrow V_j \in E$ y $A_{ij}=0$ de lo contrario. De esta matriz de adyacencia se pueden derivar muchas propiedades del grafo. Por ejemplo, $(A^n)_{ij}$ le indica el número de trayectorias de longitud $n$ pasando de $V_i$ a $V_j$ y para un grafo no dirigido el número de componentes conectados es igual al número de valores propios de $A$ igual a cero.

¿Existe una bonita cantidad lineal-algebraica que pueda decir si este gráfico tiene o no ciclos?

Mi instinto me dice que $A^* = I + A + A^2 + A^3 + \ldots = (I-A)^{-1}$ siendo finito (es decir, $I-A$ que no sea singular) es una condición necesaria y suficiente, porque significa que hay un número finito de caminos de longitud arbitraria entre dos vértices cualesquiera. ¿Es esto correcto?

Answer 1

Es necesario pero no suficiente. $G$ no tiene ciclos dirigidos si $A$ es nilpotente . Esta es una condición más fuerte que $A$ que no tiene un valor propio de $1$ (la mayoría de los gráficos no tienen valores propios $1$ ).