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&#39;,\cdots,i_k&#39;} T_{i_1i_1&#39;} \cdots T_{i_ki_k&#39;} M_{i_1&#39;i_2&#39;\cdots i_k&#39;}$

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

Let $\Gamma&#39;$ 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&amp;x\\1&amp;0\end{pmatrix}$. If you then perform the change of basis $TC^{-1}$ you get the signature $T^{\otimes k}M$.