7
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.