Unlocking the walk matrix of a graph
Let G be a graph with vertex set V={v1,…,vn} and adjacency matrix A. For a subset S of V let $\e=(x_{1},\,\dots,\,x_{n})^{\tt T}$ be the characteristic vector of S, that is, xℓ=1 if vℓ∈S and xℓ=0 otherwise. Then the n×n matrix WS:=[e,Ae,A2e,…,An−1e] is the {\it walk matrix} of G for S. This name relates to the fact that in WS the kth entry in the row corresponding to vℓ is the number of walks of length k−1 from vℓ to some vertex in S. Since A is symmetric the characteristic vector of S can be written uniquely as a sum of eigenvectors of A. In particular, we may enumerate the distinct eigenvalues μ1,…,μs of A so that \begin{eqnarray}\label{SSA}{\rm SD}(S)\!:\,\e&=&\e_{1}+\e_{2}+\dots+\e_{r}\, \end{eqnarray} where r≤s and $\e_{i}$ is an eigenvector of A of μi for all $1\leq i\leq r. We refer to (\ref{SSA}) as the {\it spectral decomposition} of $S,ormoreproperly,ofitscharacteristicvector.ThekeyresultofthispaperisthatthewalkmatrixW^{S}determinesthespectraldecompositionofSandviceversa.Thisholdsforanynon−emptysetS$ of vertices of the graph and explicit algorithms which establish this correspondence are given. In particular, we show that the number of distinct eigenvectors that appear in \,(\ref{SSA})\, is equal to the rank of $W^{S}.Severaltheoremscanbederivedfromthisresult.WeshowthatW^{S}determinestheadjacencymatrixofGifW^{S}hasrank\geq n-1.Thistheoremisbestpossibleasthereareexamplesofpairsofgraphswiththesamewalkmatrixofrankn-2$ but with different adjacency matrices.
