The walk matrix of a graph 
on 
vertices with adjacency
matrix 
is the 
matrix
![W(G)=[1,A1,...,A^(n-1)1],](/images/equations/WalkMatrix/NumberedEquation1.svg) |
where 
is the 
-vector of all 1's (Godsil 2012).
For 
, the 
th entry of 
is the number of walks of length 
beginning at the 
th graph vertex. Thus the 
st column of 
records the numbers of such walks
beginning at each graph vertex.
A graph is a controllable graph precisely when its walk matrix has matrix rank 
, and it is an almost
controllable graph when its matrix rank is 
(Wang and Wang 2025).
