Controllable Subsets in Graphs

Let X be a graph on ?? vertices with adjacency matrix A, and let S be a subset of its vertices with characteristic vector z. We say that the pair (X, S) is controllable if the vectors A ^r z for r =? 1, . . . , ?? ? 1 span ${\mathbb{R}^{\nu}}$ . Our concern is chiefly with the cases where S =?V(X), or S is a single vertex. In this paper we develop the basic theory of controllable pairs. We will see that if (X, S) is controllable then the only automorphism of X that fixes S as a set is the identity. If (X, S) is controllable for some subset S then the eigenvalues of A are all simple.