<p>For $D$ unrestricted, computing $N_D$ exactly is equivalent to evaluating the Tutte polynomial of a graph: the values $N_D$ determine the weight enumerator of a linear code, also known as the Tutte polynomial of a binary matroid, and your restriction on the $\lambda^i$ corresponds to the linear code being given by a basis of vectors of Hamming weight 2, which is the just the usual cycle matroid of a graph.</p>

<p>On the other hand, we can calculate $N_{n-2k}$ if $k$ is constant in polynomial time as follows. There are $O(n^k)$ diagonal matrices $C$ with $n-k$ ones and $k$ minus-ones. These can be enumerated in polynomial time for fixed $k$. $C$ can be considered as a point in $\mathbb{F}_2^n$ and each $b$ can be considered as a point in $\mathbb{F}_2^m$ where $m$ is the number of $\lambda^i$s. This turns multiplication into addition, so the definition of $C_b$ becomes $C_{b_j}=\sum \lambda^i_{jj} b_i$. In Diestel's book on graph theory the values $b$ such that $\sum \lambda^i_{jj} b_i=0$ are called the cycle space of the graph.</p>

CC BY-SA 3.0
2011-04-20T19:47:50.147Z
@Colin: Thanks, this might be exactly what I am looking for, but I am having a little difficulty understanding your answer. $D$ is always bounded between $-n$ and $+n$, so I do not understand how it can be tractable for each individual value of $D$, but #P-Complete to calculate all $n$ values (half the values are necessarily 0).
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T19:53:35.170Z
I wasn't sure whether you were fixing $D$ or not. Bounded by $n$ means unbounded!
Colin McQuillan
CC BY-SA 3.0
2011-04-20T20:00:41.877Z
@Colin: So for fixed D there is a poly time algorithm? I'm not sure I see how, since as $n$ grows, the number of cycles may increase exponentially.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T20:11:45.373Z
@Joe: Sorry that was wrong, what I had in mind was $D-n$ or $D+n$ bounded (so there are a fixed number of 1s or -1s).
Colin McQuillan
CC BY-SA 3.0
2011-04-20T20:17:24.557Z
In fact for fixed $D$ I think there's a reduction to general $D$.
Colin McQuillan
CC BY-SA 3.0
2011-04-20T20:30:42.230Z
@Colin: Thanks. But suppose I fix the number of -1s to be 2, even if I specify the vertices associated with the -1 values, then surely the value of N is lower bounded by the number of cycles on the subgraph obtained by removing these two vertices.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T20:43:55.203Z
Using linear algebra over the field with two elements, for any $C$ you can calculate the number of $b$ such that $C=C_b$.
Colin McQuillan
CC BY-SA 3.0
2011-04-20T20:55:36.957Z
@Colin: This may be very obvious, but I'm afraid I am still not seeing it. Could you give me an explicit algorithm or even the equations that you would solve?
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T21:12:50.407Z
I've edited my answer with some equations. Section 1.9 of Diestel's book on graph theory might be helpful (it's free online).
Colin McQuillan
CC BY-SA 3.0
2011-04-21T10:56:27.923Z
Can you clarify the connection to the [Tutte polynomial](http://en.wikipedia.org/wiki/Tutte_polynomial) of a graph?  I guess that you are viewing the input as an n-vertex graph, each matrix representing an edge connecting two coordinates whose values are −1.  What puzzles me is that the Tutte polynomial has two variables and N_D has only one variable D.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-21T13:58:40.310Z
@Colin and @Tsuyoshi: I'm afraid I am still having difficulty seeing this too.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T18:50:39.717Z
2011-04-20T21:09:20.410Z
2011-04-20T21:09:20.410Z
Colin McQuillan
<p>I have run into the following problem in the course of trying to solve another problem, and have been unable to come up with a decent answer. This may reduce trivially to a known problem, but if so I am not seeing it, and would be extremely thankful if someone could point me in the right direction.</p>

<p>Given a set of unique $n \times n$ matrices $\{\lambda^{i}\}$ of the form $\lambda^{i}_{jk} = \delta_{jk} (1-2\delta_{x_i j}-2\delta_{y_i j})$, where $1\leq x_i &lt; y_i \leq n$, is there an efficient way to calculate $N_D$, the number of operators of the form $C_b = \prod_i \left(\lambda^i \right)^{b_i}$ which satisfy $\mbox{Tr}(C_b) = D$? Here $b_i \in \{0,1\}$. I would be interested to know if there is any polynomial time algorithm, or even if it is in <strong>P/poly</strong>, or alternatively, if this reduces to some more studied open problem.</p>

<p>As things stand, I can currently obtain $\sum_D N_D$ and $\sum_D N_D D$, but not enough other linearly independent equations to be able to solve individually for each $N_D$.</p>

CC BY-SA 3.0
2011-04-20T17:12:44.547Z
I do not understand the question and I guess that I am missing something.  As I understand it, each matrix λ^i is a diagonal matrix with ±1 diagonal elements.  The product of a subset of them is also a diagonal matrix with ±1 diagonal elements, so its determinant is ±1.  If you can compute N_{+1}+N_{−1} and N_{+1}−N_{−1}, you can compute N_{+1} and N_{−1}.  (Wild guess: Did you mean trace instead of determinant?)
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-20T17:19:49.857Z
@Tsuyoshi: sorry, somehow I wrote my question with the restriction on the determinant of the matrix rather than what I actually intended (a restriction on the trace). I've fixed the typo now.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-20T17:34:04.067Z
Now the question makes sense.  If I understand the problem correctly, it can be stated without referring to matrices at all: you are given distinct n-bit strings each of which contains exactly two 1s, and you want to know the number of ways to select a subset of the given strings so that the XOR of the selected strings has exactly k ones.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-20T17:38:46.717Z
If you obtain the same matrix C_b from two different vectors b, do you count it as one or two?  I assumed the answer is two in my previous comment.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-20T19:03:41.843Z
@Tsuyoshi: exactly! $b = \{b_i\}$ and so while $C_i = C_j$ is possible, each $C_i$ is specified uniquely.
Joe Fitzsimons
<cc.complexity-theory><co.combinatorics>
Complexity of counting products of commuting operators drawn from a specific set.
Joe Fitzsimons
# Complexity of counting products of commuting operators drawn from a specific set.

(Asked by: username_0 on 2011-04-20)

I have run into the following problem in the course of trying to solve another problem, and have been unable to come up with a decent answer. This may reduce trivially to a known problem, but if so I am not seeing it, and would be extremely thankful if someone could point me in the right direction.

Given a set of unique $n \times n$ matrices $\{\lambda^{i}\}$ of the form $\lambda^{i}\_{jk} = \delta\_{jk} (1-2\delta\_{x\_i j}-2\delta\_{y\_i j})$, where $1\leq x\_i < y\_i \leq n$, is there an efficient way to calculate $N\_D$, the number of operators of the form $C\_b = \prod\_i \left(\lambda^i \right)^{b\_i}$ which satisfy $\mbox{Tr}(C\_b) = D$? Here $b\_i \in \{0,1\}$. I would be interested to know if there is any polynomial time algorithm, or even if it is in **P/poly**, or alternatively, if this reduces to some more studied open problem.

As things stand, I can currently obtain $\sum\_D N\_D$ and $\sum\_D N\_D D$, but not enough other linearly independent equations to be able to solve individually for each $N\_D$.

**Tags:** cc.complexity-theory, co.combinatorics

> **Comments:**
> **username_1**: I do not understand the question and I guess that I am missing something.  As I understand it, each matrix λ^i is a diagonal matrix with ±1 diagonal elements.  The product of a subset of them is also a diagonal matrix with ±1 diagonal elements, so its determinant is ±1.  If you can compute N_{+1}+N_{−1} and N_{+1}−N_{−1}, you can compute N_{+1} and N_{−1}.  (Wild guess: Did you mean trace instead of determinant?)  
> **username_0**: @Tsuyoshi: sorry, somehow I wrote my question with the restriction on the determinant of the matrix rather than what I actually intended (a restriction on the trace). I've fixed the typo now.  
> **username_1**: Now the question makes sense.  If I understand the problem correctly, it can be stated without referring to matrices at all: you are given distinct n-bit strings each of which contains exactly two 1s, and you want to know the number of ways to select a subset of the given strings so that the XOR of the selected strings has exactly k ones.  
> **username_1**: If you obtain the same matrix C_b from two different vectors b, do you count it as one or two?  I assumed the answer is two in my previous comment.  
> **username_0**: @Tsuyoshi: exactly! $b = \{b_i\}$ and so while $C_i = C_j$ is possible, each $C_i$ is specified uniquely.  

---

## 1 answers

### Answer by username_2 on 2011-04-20. Score: 1

For $D$ unrestricted, computing $N\_D$ exactly is equivalent to evaluating the Tutte polynomial of a graph: the values $N\_D$ determine the weight enumerator of a linear code, also known as the Tutte polynomial of a binary matroid, and your restriction on the $\lambda^i$ corresponds to the linear code being given by a basis of vectors of Hamming weight 2, which is the just the usual cycle matroid of a graph.

On the other hand, we can calculate $N\_{n-2k}$ if $k$ is constant in polynomial time as follows. There are $O(n^k)$ diagonal matrices $C$ with $n-k$ ones and $k$ minus-ones. These can be enumerated in polynomial time for fixed $k$. $C$ can be considered as a point in $\mathbb{F}\_2^n$ and each $b$ can be considered as a point in $\mathbb{F}\_2^m$ where $m$ is the number of $\lambda^i$s. This turns multiplication into addition, so the definition of $C\_b$ becomes $C\_{b\_j}=\sum \lambda^i\_{jj} b\_i$. In Diestel's book on graph theory the values $b$ such that $\sum \lambda^i\_{jj} b\_i=0$ are called the cycle space of the graph.

> **Comments:**
> **username_0**: @Colin: Thanks, this might be exactly what I am looking for, but I am having a little difficulty understanding your answer. $D$ is always bounded between $-n$ and $+n$, so I do not understand how it can be tractable for each individual value of $D$, but #P-Complete to calculate all $n$ values (half the values are necessarily 0).  
> **username_2**: I wasn't sure whether you were fixing $D$ or not. Bounded by $n$ means unbounded!  
> **username_0**: @Colin: So for fixed D there is a poly time algorithm? I'm not sure I see how, since as $n$ grows, the number of cycles may increase exponentially.  
> **username_2**: @Joe: Sorry that was wrong, what I had in mind was $D-n$ or $D+n$ bounded (so there are a fixed number of 1s or -1s).  
> **username_2**: In fact for fixed $D$ I think there's a reduction to general $D$.  
> **username_0**: @Colin: Thanks. But suppose I fix the number of -1s to be 2, even if I specify the vertices associated with the -1 values, then surely the value of N is lower bounded by the number of cycles on the subgraph obtained by removing these two vertices.  
> **username_2**: Using linear algebra over the field with two elements, for any $C$ you can calculate the number of $b$ such that $C=C_b$.  
> **username_0**: @Colin: This may be very obvious, but I'm afraid I am still not seeing it. Could you give me an explicit algorithm or even the equations that you would solve?  
> **username_2**: I've edited my answer with some equations. Section 1.9 of Diestel's book on graph theory might be helpful (it's free online).  
> **username_1**: Can you clarify the connection to the [Tutte polynomial](http://en.wikipedia.org/wiki/Tutte_polynomial) of a graph?  I guess that you are viewing the input as an n-vertex graph, each matrix representing an edge connecting two coordinates whose values are −1.  What puzzles me is that the Tutte polynomial has two variables and N_D has only one variable D.  
> **username_0**: @Colin and @Tsuyoshi: I'm afraid I am still having difficulty seeing this too.  

---

