# Complexity of counting products of commuting operators drawn from a specific set.

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

• 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 Apr 20 '11 at 17:12
• @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 Apr 20 '11 at 17:19
• 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 Apr 20 '11 at 17:34
• 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 Apr 20 '11 at 17:38
• @Tsuyoshi: exactly! $b = \{b_i\}$ and so while $C_i = C_j$ is possible, each $C_i$ is specified uniquely. – Joe Fitzsimons Apr 20 '11 at 19:03

## 1 Answer

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.

• @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 Apr 20 '11 at 19:47
• I wasn't sure whether you were fixing $D$ or not. Bounded by $n$ means unbounded! – Colin McQuillan Apr 20 '11 at 19:53
• @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 Apr 20 '11 at 20:00
• @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 Apr 20 '11 at 20:11
• In fact for fixed $D$ I think there's a reduction to general $D$. – Colin McQuillan Apr 20 '11 at 20:17