Basis Collapse for Holographic Algorithms Over all Domain Sizes
summary
Proves a collapse: for domain size K any holographic algorithm that uses a full‑rank matchgate can be simulated with basis size l = floor(log2 K). Proof uses algebraic matchgate identities and a wedge/exterior‑power argument to show rank rigidity (matrix ranks are powers of two), extracts a cluster of 2^r rows of independent rows, then builds smaller generators and a matchgate transducer (matrix inversion realized as a matchgate) to simulate the original algorithm — the construction succeeds under the full‑rank assumption.
AI-written summary · about