The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ NP, we must begin to develop a theory which captures the limit of expressibility and power of this new methodology.

In holographic algorithms, {\it symmetric signatures} have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results~\cite{CC-icalp} where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. This in particular confirms a conjecture by Valiant. We also give a complete characterization of Boolean symmetric signatures over bases of size 1.