Prove that $G$ is connected if and only if the matrix $(I_n + A)^{n−1}$ has no $0$'s.

Question

Let $G$ be a graph on $n$ vertices, $A = AG$ its adjacency matrix, and $I_n$ the $n \times n$ identity matrix. Prove that $G$ is connected if and only if the matrix $(I_n + A)^{n−1}$ has no $0$'s.

For the if part- as $G$ is connected there is a path between any two vertices, the maximum size of the path can be $n$ as there are $n$ vertices because of this observation there is always a path from any $u$ to any $v$ of length $n-1$. Thus $(I_n+A)^{n-1}$ is non zero. (But I am not convinced with the idea).

For the only if part I am not getting any convincing idea either.

Thank you.

Answer 1

For vertices $u,v$ in $G$, and an integer $k \geqslant 0$, the $(u,v)$-th entry of $A^k$ is the number of walks of length $k$ from $u$ to $v$ in $G$. If we denote this number by $W_k(u,v)$, then the $(u,v)$-th entry of $(I_n+A)^{n-1}$ is equal to $$\sum_{k=0}^{n-1}\binom{n-1}{k}W_k(u,v).$$ This is nonzero if and only if $W_k(u,v)$ is nonzero for some $0 \leqslant k \leqslant n-1$.

Answer 2

The answer by metamorphy is great. However, there is a combinatorial interpretation of each entry of the matrix $(I_n+A)^k$ for each integer $k\geq 0$.

Let $G$ be a simple graph on the set of vertices $V:=\{1,2,\ldots,n\}$ with adjacency matrix $A$. If $C$ is a connected component of $G$ with $n_C$ vertices, then observe that there exists a path involving at most $n_C-1$ edges from any vertex in $C$ to any other vertex in $C$. (An empty path is included as a path from a vertex to itself.)

Now, let $D$ be the directed graph obtained from $G$ by adding a directed loop at each vertex of $G$. Note that, for $i,j\in V$, the $(i,j)$-entry of the matrix $I+A$ (here, $I$ is a shorthand for $I_n$, the $n$-by-$n$ identity matrix) is precisely the number of ways to go from vertex $i$ to vertex $j$, using only one edge (directed or undirected) in $D$. Now, observe that $D$ is connected if and only if $G$ is connected.

Finally, for $k=0,1,2,3,\ldots$, note that the $(i,j)$-entry $t_{i,j}^k$ of $(I+A)^k$ is the number of ways to go from $i\in V$ to $j\in V$ involving exactly $k$ edges (directed or undirected) in $D$. If there exists a path in $D$ (whence in $G$) from $i$ to $j$ within $k$ steps, it is easy to see that $t_{i,j}^l>0$ for all integers $l\geq k$. If $G$ is connected, then $D$ is connected and there exists a path of length at most $n-1$ in $G$ from any two vertices. Therefore, $t^k_{i,j}>0$ for all $k\geq n-1$ and $i,j\in V$. Conversely, if $t^{n-1}_{i,j}>0$ for all $i,j\in V$, then $D$ is connected, whence so is $G$.