The rank of Pseudo walk matrices: controllable and recalcitrant pairs

A pseudo walk matrix W v of a graph G having adjacency matrix A is an n × n matrix with columns v , A v , A 2 v , … , A n − 1 v whose Gram matrix has constant skew diagonals, each containing walk enumerations in G . We consider the factorization over Q of the minimal polynomial m ( G , x ) of A . We prove that the rank of W v , for any walk vector v , is equal to the sum of the degrees of some, or all, of the polynomial factors of m ( G , x ) . For some adjacency matrix A and a walk vector v , the pair ( A , v ) is controllable if W v has full rank. We show that for graphs having an irreducible characteristic polynomial over Q , the pair ( A , v ) is controllable for any walk vector v . We obtain the number of such graphs on up to ten vertices, revealing that they appear to be commonplace. It is also shown that, for all walk vectors v , the degree of the minimal polynomial of the largest eigenvalue of A is a lower bound for the rank of W v . If the rank of W v attains this lower bound, then ( A , v ) is called a recalcitrant pair. We reveal results on recalcitrant pairs and present a graph having the property that ( A , v ) is neither controllable nor recalcitrant for any walk vector v .