An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized by matchgates under a suitable basis. For domain size two, [1,3] characterized all functions directly realizable as matchgate signatures without a basis transformation, and  gave a polynomial time algorithm for the realizability problem for symmetric signatures under basis transformations. We generalize this to arbitrary domain size
. Specifically, we give a polynomial time algorithm for the realizability problem on domain size
≥ 3. Using this, one can decide whether suitable signatures for a holographic algorithms on domain size
are realizable and if so, to find a suitable linear basis to realize these signatures by an efficient algorithm.