How adjacency matrix shows that the graph have no cycles?

Question

Let $G$ a directed graph and $A$ the corresponding adjacency matrix. Let denote the identity matrix with $I$. I've read in a wikipedia article, that the following statement is true.

Question. Is it true, that $I-A$ matrix is invertible if and only if there is no directed cycle in $G$?

Answer 1

It is not true. Consider the graph

* <===> * <===> *

It has adjacency graph $A=\begin{pmatrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$, so $I-A=\begin{pmatrix}1 & -1 & 0 \\ -1 & 1 & -1 \\ 0 & -1 & 1 \end{pmatrix}$ which has determinant $-1$.

Thus $I-A$ is invertabile, but the graph certainly has cycles.

Answer 2

As Henning Makholm says, the result isn't true.

Looking at the Wikipedia article, a "proof" might go something like this:

$(I-A)^{-1}=I+A+A^2+A^3+\ldots$

The entries $a^n_{ij}$ of $A^n$ give the number of walks of length $n$ from $v_i$ to $v_j$.

If we assume that the graph is finite, any sufficiently long walk must revisit a vertex. Since the graph is directed, this means that there must be some cycle. So if $I+A+A^2+A^3+\ldots$ doesn't converge then there must be a cycle.

And if there is some cycle (containing $v_i$, say), there must be arbitrarily long walks (from $v_i$ to itself). So if there is a cycle then $I+A+A^2+A^3+\ldots$ doesn't converge.

But $(I-A)^{-1}=I+A+A^2+A^3+\ldots$, so we have the required result.

But the expansion of $(I-A)^{-1}$ only holds in certain cases (I think you need all eigenvalues of $A$ to have modulus $\lt 1$), so the proof isn't valid.