Holographic algorithms on bases of rank 2

•A theorem to determine if recognizers on domain size k>2k>2 are simultaneously realized on a basis of rank 2.•A theorem to reduce SRP on domain size k>2k>2 to SRP on domain size 2 for holographic algorithms with matchgates.•A collapse theorem for holographic algorithms with matchgates on domain size k>2k>2.

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized under a suitable basis transformation (SRP). For holographic algorithms with matchgates on domain size 2, [1], [2], [4] and [5] have built a systematical theory. In this paper, we reduce SRP on domain size k≥3k≥3 to SRP on domain size 2 for holographic algorithms with matchgates on bases of rank 2. Furthermore, we generalize the collapse theorem of [3] to domain size k≥3k≥3.