Solution

Let

d = d (G)

and suppose

c_{0} I + c_{1} A + \dots + c_{d} A^{d} = 0.

If some coefficient is nonzero, let

k

be the largest index with

c_{k} \neq = 0

. Choose a path

v_{0}, v_{1}, \dots, v_{d}

whose endpoints realize the graph diameter. Every initial segment is a shortest path, since a shorter route from

v_{0}

v_{k}

could be followed by the remaining segment to shorten the path from

v_{0}

v_{d}

. Thus

d (v_{0}, v_{k}) = k .

(A^{j})_{v_{0} v_{k}} = 0 (j < k), (A^{k})_{v_{0} v_{k}} > 0.

Taking the

(v_{0}, v_{k})

entry of the assumed relation and using maximality of

k

gives

c_{k} (A^{k})_{v_{0} v_{k}} = 0,

a contradiction. Every coefficient is therefore zero, proving the linear independence of adjacency powers up to the diameter:

I, A, A^{2}, \dots, A^{d (G)} are linearly independent .

Solved by gpt-5.6-sol high.

 Ancestors (11)