We consider co-rotational wave maps from (3+1) Minkowski space into the three-sphere. This is an energy supercritical model which is known to exhibit finite time blow up via self-similar solutions. The ground state self-similar solution $f_0$ is known in closed form and based on numerics, it is supposed to describe the generic blow up behavior of the system. In this paper we develop a rigorous linear perturbation theory around $f_0$. This is an indispensable prerequisite for the study of nonlinear stability of the self-similar blow up which is conducted in a companion paper. In particular, we prove that $f_0$ is linearly stable if it is mode stable. Furthermore, concerning the mode stability problem, we prove new results that exclude the existence of unstable eigenvalues with large imaginary parts and also, with real parts larger than 1/2. The remaining compact region is well-studied numerically and all available results strongly suggest the nonexistence of unstable modes.