If G is connected graph, then show that there is no $0$ element in matrix $A+A^2+A^3+\cdots+A^{n-1}$ where A is adjacency matrix of G, and n number of vertices. If we are looking at element on position $ij$ where $i\ne j$ then it is clear(because G is connected) that there must exist path with length of at least one of the numbers $1,2,\cdots,n-1$. But how can we know that elements on position where $i=j$ will be non zero, because this graph does not need to have a cycle right, so maybe there is not closed path in it? Or I am missing something obvious?
Sum of adjacency matrices in connected graph G
adjacency matrixgraph theory
Best Answer
I think you are forgetting that the walks counted by the powers of the adjacency matrix can come and go through the same edge (because it is a walk, not a path).
Simple example:
\begin{align*} A &=\left[\begin{array}[cc] 00 & 1 \\ 1 & 0 \end{array}\right] \\ A^2&=\left[\begin{array}[cc] 01 & 0 \\ 0 & 1 \end{array}\right] \end{align*}
PS: Walks are "paths" where you are allowed to repeat edges and vertices.