Linear independence of adjacency powers up to the diameter
= Linear independence of adjacency powers up to the diameter
If a connected graph has adjacency matrix $A$ and diameter $d$, then
$$
I,A,\ldots,A^d
$$
are linearly independent. For the largest index $k$ with a nonzero coefficient, choose vertices at distance $k$; the corresponding entries of all lower powers vanish, while $(A^k)_{uv}>0$ by the <walk count from powers of an adjacency matrix>.