Binary subspace membership testing with signed vectors

Question

Say we are working in $\mathbb{F}^{2n}_2$ where vectors can be written as pairs $(a,b)$ with $a,b \in \mathbb{F}^{n}_2$. Given a list of basis vectors for an $n-1$ dimensional subspace $S \subset \mathbb{F}^{2n}_2$, I want a polynomial time algorithm that can test membership of an input vector $(a,b)$.

This version of the problem is easy to solve using coding theory: I construct a generator matrix of the null space of $S$, call it $S^\perp$, and use $S^\perp$ as a parity check matrix: if $S^\perp(a,b) = \mathbf{0}$ then $(a,b) \in S$.

I am interested in a weird case where my vectors have an additional sign bit: $(s,a,b)$. Addition is defined as: $$(s,a,b) + (s',a',b') = (s + s' + a^Tb' + b^Ta', a+a', b+b')$$ How can I test for membership in this case? By ignoring the sign bit I can use the parity check test to determine membership of the $(a,b)$ part, but since this method does not tell me a decomposition into basis vectors I can't use the result to verify if the sign is correct. Let's say either $(0,a,b) \in S$ or $(1,a,b) \in S$, but never both.

(To those who want context, this is a question about $[[n,1]]$ quantum stabilizer codes: Given a list of stabilizer generators, test for membership of a given Pauli operator, taking the sign of the operator into account.)

For example, let the rows of the following matrix be a basis for $S$ when $n = 4$: $$\begin{bmatrix}1, & 1&0&0&1,&0&0&0&0\\ 0,&0&1&0&0,&0&1&1&0\\0,&0&0&1&0,&0&1&1&0 \end{bmatrix}$$ Is the vector $(0,1111,0000)$ in this space? The parity check method says yes, but in fact the vector has the wrong sign. How can I verify this without expanding out the whole space?

Answer 1

Took me a while but I figured it out. Say I already know that either $(0,a,b) \in S$ or $(1,a,b) \in S$ and I want to find out which for some $(a,b)$.

Define a regular inner product $(a,b) \cdot (a',b') = a^Ta' + b^T b'$. I can compute the null space $\text{Null}(S)$ of a space $S$ with respect to this inner product using a standard elimination procedure from a basis for $V = \mathbb{F}^{2n}_2$. For each basis element $(a,b) \in S$:

1. let $V_0 = \{ (v_a, v_b) \in V | (v_a, v_b) \cdot (a,b) = 0 \}$
2. let $V_1 = \{ (v_a, v_b) \in V | (v_a, v_b) \cdot (a,b) = 1 \}$
3. Take any $(v_a,v_b) \in V_1$. Then define $V_1' = \{ (v_a, v_b) + (v_a', v_b') | (v_a',v_b') \in V_1 / \{(v_a,v_b)\} \}$. I.e. take out $(v_a,v_b)$ and add it to all the other elements. Now all of $V_1'$ is orthogonal to $(a,b)$: $$(a,b) \cdot ((v_a, v_b) + (v_a', v_b')) = (a,b) \cdot (v_a, v_b) + (a,b) \cdot (v_a', v_b') = 1+1 = 0 $$
4. update $V = V_0 \cup V_1'$.

Observe that we can keep track of sign in $V$ if we want to, and that the final $V$ is a subset of the starting $V$, even with respect to sign, because all we did is remove vectors from $V$ or add vectors from $V$ together.

We have $\text{Null}(\text{Null}(S)) = S$. Let's do this procedure for the space spanned by $(a,b)$. First we shrink a basis $V = \mathbb{F}^{2n}_2$ with respect to $(a,b)$ to obtain $\text{Null}(\text{span}((a,b)))$. Next, we shrink $V = S$ with respect to all vectors in $\text{Null}(\text{span}((a,b)))$ but this time keeping track of sign. We obtain either $(0,a,b) \in S$ or $(1,a,b) \in S$.

Let me solve the example: The null space of $(1111,0000)$, starting with $V = \mathbb{F}^{2n}_2$ and shrinking:

$$\begin{bmatrix} 1 & 1 & 0 & 0, & 0 & 0 &0 &0\\ 0 & 1 & 1 & 0, & 0 & 0 &0 &0\\ 0 & 0 & 1 & 1, & 0 & 0 &0 &0\\ 0 & 0 & 0 & 0, & 1 & 0 &0 &0\\ 0 & 0 & 0 & 0, & 0 & 1 &0 &0\\ 0 & 0 & 0 & 0, & 0 & 0 &1 &0\\ 0 & 0 & 0 & 0, & 0 & 0 &0 &1\\ \end{bmatrix}$$

Now we compute the null space of the above matrix, starting with $S$ (the matrix in the question) and shrinking while keeping track of sign.

After the first vector $(1100,0000)$:

$$\begin{bmatrix} 1, &1 & 1 & 0 & 1, & 0 & 1 & 1 &0\\ 0, &0 & 0 & 1 & 0, & 0 & 1 & 1 &0\\ \end{bmatrix}$$

After the second vector $(0110,0000)$ (adding the rows changes the sign):

$$\begin{bmatrix} 0, &1 & 1 & 1 & 1, & 0 & 0 & 0 &0\\ \end{bmatrix}$$

And the remaining vectors do nothing. We see that $(0,1111,0000) \in S$.