The rank of pseudo walk matrices : controllable and recalcitrant pairs

Abstract

A pseudo walk matrixWv of a graph G having adjacency matrix A is an nXn matrix with columns (Formula presented.) 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 Wv, 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 Wv 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 Wv. If the rank of Wv 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.