  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}:=\big[{\rm
e},\,A{\rm e},\,A^{2}{\rm e},\dots,A^{n-1}{\rm e}\big]$$ is the {\it walk
matrix} of $G$ for $S.$ This name relates to the fact that in $W^{S}$ the
$k^{\rm 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\leq 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,$ or more properly, of
its characteristic vector. The key result of this paper is that the walk matrix
$W^{S}$ determines the spectral decomposition of $S$ and {\it vice versa.} This
holds for any non-empty set $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}.$ Several theorems can be derived from this result.
We show that $W^{S}$ determines the adjacency matrix of $G$ if $W^{S}$ has rank
$\geq n-1$. This theorem is best possible as there are examples of pairs of
graphs with the same walk matrix of rank $n-2$ but with different adjacency
matrices.
