Unlocking the walk matrix of a graph

Abstract

Let $G$ be a graph with vertex set $V=\{v_1,\dots ,v_n\}$ 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_{\ell }=1$ if $v_{\ell }\in S$ and $x_{\ell }=0$ otherwise. Then the $n\times n$ matrix $$W^S:=[\mathrm{e},A\mathrm{e},A^2\mathrm{e},\dots ,A^{n-1}\mathrm{e}]$$ is the {\it walk matrix} of $G$ for $S.$ This name relates to the fact that in $W^S$ the $k^{\mathrm{th}}$ entry in the row corresponding to $v_{\ell }$ is the number of walks of length $k-1$ from $v_{\ell }$ 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 ${\mu }_1,\dots ,{\mu }_s$ of $A$ so that \begin{eqnarray}\label{SSA}{\rm SD}(S)\!:\,\e&=&\e_{1}+\e_{2}+\dots+\e_{r}\, \end{eqnarray} where $r\le s$ and $\e_{i}$ is an eigenvector of $A$ of ${\mu }_i$ for all $1\leq i\leq r. We refer to (\ref{SSA}) as the {\it spectral decomposition} of $S,$ormoreproperly,ofitscharacteristicvector.Thekeyresultofthispaperisthatthewalkmatrix$W^{S}$determinesthespectraldecompositionof$S$andviceversa.Thisholdsforanynon-emptyset$S$ 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.Weshowthat$W^{S}$determinestheadjacencymatrixof$G$if$W^{S}$hasrank$\geq n-1$.Thistheoremisbestpossibleasthereareexamplesofpairsofgraphswiththesamewalkmatrixofrank$n-2$ but with different adjacency matrices.

28 pages, 7 figures