= Solution
Let $d=d(G)$ and suppose
$$
c_0I+c_1A+\cdots+c_dA^d=0.
$$
If some coefficient is nonzero, let $k$ be the largest index with $c_k\ne0$. Choose a path
$$
v_0,v_1,\ldots,v_d
$$
whose endpoints realize the <graph diameter>. Every initial segment is a shortest path, since a shorter route from $v_0$ to $v_k$ could be followed by the remaining segment to shorten the path from $v_0$ to $v_d$. Thus
$$
d(v_0,v_k)=k.
$$
By the <walk count from powers of an adjacency matrix>,
$$
(A^j)_{v_0v_k}=0\quad(j<k),
\qquad
(A^k)_{v_0v_k}>0.
$$
Taking the $(v_0,v_k)$ entry of the assumed relation and using maximality of $k$ gives
$$
c_k(A^k)_{v_0v_k}=0,
$$
a contradiction. Every coefficient is therefore zero, proving the <linear independence of adjacency powers up to the diameter>:
$$
\boxed{I,A,A^2,\ldots,A^{d(G)}\ \text{are linearly independent}.}
$$
Back to article page
