  We characterize the conditions under which a translationally invariant matrix
product state (MPS) is invariant under local transformations. This allows us to
relate the symmetry group of a given state to the symmetry group of a simple
tensor. We exploit this result in order to prove and extend a version of the
Lieb-Schultz-Mattis theorem, one of the basic results in many-body physics, in
the context of MPS. We illustrate the results with an exhaustive search of
SU(2)--invariant two-body Hamiltonians which have such MPS as exact ground
states or excitations.
