<p>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.</p>

<p>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</p>

<p>$(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;}$</p>

<p>where $T$ is some two-by-two matrix descring the new basis.</p>

<p>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$.</p>

CC BY-SA 2.5
2011-02-17T04:06:10.203Z
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.
Akash Kumar
CC BY-SA 2.5
2011-02-17T04:11:54.253Z
[contd] Also, I am not able to follow your example with $C^{\otimes k}M$. Could you please elaborate a little more? Thanks -- Akash
Akash Kumar
CC BY-SA 2.5
2011-02-17T10:31:55.780Z
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$.
Colin McQuillan
CC BY-SA 2.5
2011-02-17T13:20:01.373Z
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
Akash Kumar
CC BY-SA 2.5
2011-02-17T14:21:08.663Z
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.
Colin McQuillan
CC BY-SA 2.5
2011-02-17T17:39:33.637Z
Thanks Colin. Now I finally get how many things I can understand the wrong way. Sometimes I amaze myself. Thanks for bearing with all those questions. Best -- Akash
Akash Kumar
CC BY-SA 2.5
2011-02-16T19:06:21.723Z
2011-02-16T19:13:52.993Z
2011-02-16T19:13:52.993Z
Colin McQuillan
<p>I was going through Les Valiant's <a href="http://people.seas.harvard.edu/~valiant/holographic11-07.pdf">seminal paper</a> and I had a tough time with Proposition 4.3 on page 10 of the paper.</p>

<p>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$. </p>

<p>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.</p>

<p>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. </p>

<p>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 :-(</p>

<p>Best
-Akash</p>

<ds.algorithms><counting-complexity><survey>
Holographic Algorithms - Equivalence of Bases
Akash Kumar
# Holographic Algorithms - Equivalence of Bases

(Asked by: username_0 on 2011-02-16)

I was going through Les Valiant's [seminal paper](http://people.seas.harvard.edu/~valiant/holographic11-07.pdf) 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

**Tags:** ds.algorithms, counting-complexity, survey


---

## 1 answers

### Answer by username_1 on 2011-02-16. Score: 8 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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.  
> **username_0**: [contd] Also, I am not able to follow your example with $C^{\otimes k}M$. Could you please elaborate a little more? Thanks -- Akash  
> **username_1**: 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$.  
> **username_0**: 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  
> **username_1**: 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.  
> **username_0**: Thanks Colin. Now I finally get how many things I can understand the wrong way. Sometimes I amaze myself. Thanks for bearing with all those questions. Best -- Akash  

---

