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?



Binary subspace membership testing with signed vectors
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$. 


