Is the following condition NASC for connectivity of a graph?

Question

Is the statement true that a graph $G$ with $n$ vertices is connected iff $(A+A^2+...+A^n)$ has no $0$ entry,where $A$ is the adjacency matrix of $G$.I have tried to prove it but I could not conclude anything.I now doubt whether the statement is correct at all.Can someone provide me the correct statement?

Answer 1

A fact about adjacency matrices is that that $A^k_{i, j}$ counts the number of walks of length exactly $k$ between vertices $i$ and $j$, see here: Proof - raising adjacency matrix to $n$-th power gives $n$-length walks between two vertices ("Walk" is not the same as "path", for definition see here: https://en.wikipedia.org/wiki/Path_(graph_theory)#Walk,_trail,_path).

Therefore $(A + A^2 + \dots + A^n)_{i, j}$ is a number of all walks between vertices $i, j$ of lengths $1, \dots, n$. Notice that if a graph has $n$ vertices, if there doesn't exist a walk between $i, j$ having length at most $n$, there won't exist a walk having length bigger than $n$, as the vertices would have to repeat, implying an existence of a shorter walk between $i, j$. Therefore $(A + A^2 + \dots + A^n)_{i, j} = 0$ is equivalent to the fact that there is no walk between vertices $i$ and $j$, so the graph must be disconnected. Naturally it works both ways, if $i, j$ lie in different components of the graph, there won't exist a walk between them for any length $k$, so $(A + A^2 + \dots A^\infty)_{i, j} = 0$. As entries in the adjacency matrix are nonnegative, it implies that $(A + A^2 + \dots A^n)_{i, j} = 0$. It follows naturally that there are no $0$ entries in $(A + A^2 + \dots + A^n)$ iff the graph is connected.