# Holographic Algorithms - Equivalence of Bases

I was going through Les Valiant's seminal paper and I had a tough time with Proposition 4.3 on page 10 of the paper.

I cannot see why is it the case that if there is a generator with certain values for $valG$ with a basis $\{(a_1,b_1) \ldots (a_r,b_r)\}$, then there exists some generator with same $valG$ values for any basis $\{(xa_1,yb_1) \ldots (xa_r,yb_r)\}$ ($1^{st} kind$) or $\{(xb_1,ya_1) \ldots (xb_r,ya_r) \}$ ($2^{nd} kind$) for any $x,y \in F$.

Valiant points out the reason in preceding paragraph - namely the $1^{st}$ kind of transformation can be achieved by appending to every input or output node an edge of weight $1$. The $2^{nd}$ kind of transformation, Valiant says, can be achieved by appending to input or output nodes chains of length $2$ weighted by $x$ and $y$ respectively.

I have not been really able to understand these statements. Maybe they are already clear, but still I cannot really see why the above construct helps achieve any realizable $valG$ values with one basis with the new basis which is one of the above types.

Please help illuminate them to me. On a different note, are there some tensor free surveys for hologaphic algorithms available online. Most of them use tensors which, sadly, scare me :-(

Best -Akash

Tensors (in this sense) are just arrays of numbers, so I don't think you'll find tensor free surveys unless they're completely free of calculations.

The "$T^{\otimes k}$" operation formalizes both the operations of changing basis and attaching gadgets to each output node (in fact I like to think of a change of basis as a sort of gadget operation). Let $\Gamma$ be a generator matchgate with standard signature $M_{i_1i_2\cdots i_k}=u(\Gamma)$. This an array of $2^k$ numbers. The signature in a new basis is given by

$(T^{\otimes k}M)_{i_1i_2\cdots i_k}:=\sum_{i_1',\cdots,i_k'} T_{i_1i_1'} \cdots T_{i_ki_k'} M_{i_1'i_2'\cdots i_k'}$

where $T$ is some two-by-two matrix descring the new basis.

Let $\Gamma'$ be the matchgate formed by adding $k$ new vertices to $\Gamma$, taking these to be the new outputs, and connecting them to the old outputs by an edge of weight $x$. Then the new signature is $C^{\otimes k}M$ where $C_{ij}$ is the matrix $\begin{pmatrix}0&x\\1&0\end{pmatrix}$. If you then perform the change of basis $TC^{-1}$ you get the signature $T^{\otimes k}M$.

• Sorry for the late reply, I was occupied today. I am afraid, due to my limited understanding of tensors, I still cannot understand you. I used to think that the signature of a generator matchgate in the new basis, $S$ was derived from the signature $u(\Gamma)$ in the old basis by the solution $S = S_0$ to $T^{\otimes k} \times S = u(\Gamma)$. I thought Valiant mentioned in his $valG(\Gamma, x)$ example that he just intended to express perfMatch vector as the sum of coefficients wrt to the new basis. I cannot be sure though, for my obvious lack of background with tensors. Feb 17, 2011 at 4:06
• [contd] Also, I am not able to follow your example with $C^{\otimes k}M$. Could you please elaborate a little more? Thanks -- Akash Feb 17, 2011 at 4:11
• I'm happy to try to elaborate, but I might just be adding confusing notation. Could you answer this first: if you add edges at each output node, what effect do you think this would have on the signature? Also, that $S_0$ can be expressed as $(T^{-1})^{\otimes k} S$ - I can't remember off-hand what the actual coefficients of $T$ should be in terms of Valiant's $n_0,n_1,p_0,p_1$. Feb 17, 2011 at 10:31
• I will try to state my confusion with an example. Consider a generator which is path of length 3 where all the 3 nodes are o/p nodes. The std signature of this generator is $(0,1,1,0,1,0,0,1)$. And the signature of the modified gadget with 3 new nodes each connected to one o/p node in the std basis is $x(1,1,1,1\ 1,1,1,0)$. Could you please continue with this example? I would like to see how does $C^{\otimes 3} where$$C = (0,\ 1)^t (x=1,\ 0)^t$ act on $u(\Gamma)$. Thanks for your patience Feb 17, 2011 at 13:20
• Let $P_3$ be a path of order 3. Call the vertices x,y,z where y is the middle vertex. $P_3 \setminus Z$ has a perfect matching iff Z is {x}, {z}, or {x,y,z}. So $u(P_3)=(0,1,0,0,1,0,0,1)$. With edges attached the signature is $(1,0,0,1,0,0,1,0)$. Try calculating for example $(C^{\otimes 3} u(P_3))_{1,2,2}=1$ using the formula above. Feb 17, 2011 at 14:21