In this question, a graph is a nonoriented, unlabeled, simple graph.
Such a graph can be represented by its incidence matrix $G$: if the vertices of the graph are labeled by $1,2,3,...,n$, then $G$ is the $n\times n$ matrix so that the entry $G[i,j]$ at row $i$ and column $j$ is equal to $1$ if there is an edge between vertices $i$ and $j$, and $0$ otherwise.
For $k\geqslant 1$, the entries of the powers $G^k$ of $G$ have a nice interpretation: $G^k[i,j]$ is the number of paths of length exactly $k$ from $i$ to $j$. Here, a path can go through a same vertex multiple times.
Assume that the graph has $n$ vertices. Then the minimum length of a path between two vertices is at most $n-1$. This leads to the following theorem:
Let $G$ be a symmetric $n\times n$ matrix with entries in $\{0,1\}$. If $G^k[i,j]=0$ for $k\in\{1,2,\dots,n-1\}$, then $G^k[i,j]=0$ for every $n\geqslant 1$.
That's a nice proof, but I am wondering if there is a direct way to prove this, using linear algebra.
How can we prove the theorem above using linear algebra?
You can prove the following more general statement:
Lemma Let $G$ be any symmetric $n \times n$ matrix. If $i,j$ is any entry such that $G^k[i,j]=0 \forall 1 \leq k \leq n-1$ then $G^n[i,j]=0 \forall n\geq 1$.
Proof:
Sketch of the proof.
Case 1: $i=j$, then, since $G$ is symmetric we have $$ 0=G^2[i,i]=\sum_{k=1}^n G[i,k]^2 $$
This shows that the $i$^th row of $G$ is identically $0$, from where, by induction you can prove that the $i$th row of $G^nb$ is zero for all $n \geq 1$.
Case 2 $i \neq j$.
Let $P_G=X^n+a_{n-1}X^{n-1}+...+a_1X+a_0$ be the characteristic polynomial of $G$. Then, by hamilton -Cayley we have $P_G(G)=0$ and hence $$G^n=-a_{n-1}G^{n-1}-a_{n-1}G^{n-2}-...-a_1G-a_0I (*)$$
In particular, for each $ m \geq 0$ you have $$G^{n+m}=-a_{n-1}G^{n-1+m}-a_{n-1}G^{n-2+m}-...-a_1G^{1+m}-a_0G^m$$
From here, it follows immediately by induction of $m$ that for all $m \geq 0$ you have $$G^{n+m}[i,j]=0$$
Note $G$ symmetric is only used to sort the case $i=j$. Alternately, you can drop this requirement and prove the following statement:
Let $G$ be any $n \times n$ matrix. If $i,j$ is any entry such that $G^k[i,j]=0 \forall 1 \leq k \leq n$ then $G^m[i,j]=0 \forall m\geq 1$.
Note that for $i \neq j$, if you know that $G^k[i,j]=0 \forall 1 \leq k \leq n-1$, the equation (*) implies that this also holds for $k=n$.