Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S_1, \ldots, S_m \in \mathbb{Z}_2^n$ be elements forming a subgroup of $\mathbb{Z}_2^n$. How can I find a set of congruences (mod 2) over $x_1, \ldots, x_n$ satisfying exactly $x_1 = S_j[1], \ldots, x_n = S_j[n]$ for all $j \in [m]$.

For exemple, given $S_1 = 000$ and $S_2 = 111$, this is an associated set of congruences: $$x_1 \equiv x_2 \, (\text{mod 2}) \text{ and } x_3 \equiv x_2 \, (\text{mod 2}).$$

I've also post the question of MathOverflow.

share|improve this question
    
Also posted to MathOverflow. In the example you give, you don't have a subgroup; you have a coset of a subgroup. –  Gerry Myerson Aug 31 '11 at 2:31
    
Sorry, I've edited the question. –  Thomas Aug 31 '11 at 2:36
    
If x1 = S1= 000, x2 = S2 = 111 in your example, then what is x3 ? –  ndroock1 Aug 31 '11 at 5:35
    
You might tag this problem under Group Theory, this problem does not belong in elementary-number-theory or algorithms. Willy Wong may do this anyway. –  ndroock1 Aug 31 '11 at 5:38
    
@ndroock1, I think you've misunderstood the notation. $x_1$ is the first component of $S_j$. In the example, $x_1(S_1)=S_1[1]=0$, $x_1(S_2)=S_2[1]=1$. Also, elementary number theory seems OK to me for a question on congruences. Group Theory may be better, but I actually see it as Linear Algebra. –  Gerry Myerson Aug 31 '11 at 7:15

2 Answers 2

up vote 1 down vote accepted

If I understand the question correctly, you're looking for the orthogonal complement of the subspace spanned by the vectors $S_1,\dotsc,S_m$ (considered as vectors in $\mathbb Z_2^n$ over $\mathbb Z_2$). Each congruence

$$\sum_{i=1}^nc_ix_i\equiv0\pmod2$$

is a constraint that all vectors $S_1,\dotsc,S_m$ are orthogonal to the vector $c$ with components $c_i$. So find a basis for the $S_1,\dotsc,S_m$, then find a basis for the orthogonal complement, and the set of all congruences satisfied by the $x_i$ corresponds to the subspace spanned by that basis. The $S_1,\dotsc,S_m$ forming a group (i.e. a subspace) isn't required for this; you just need to find a basis for the subspace they span.

share|improve this answer
    
You seem to use the fact that $\langle S_1, \ldots, S_m \rangle^{\perp \perp} = \langle S_1, \ldots, S_m \rangle$. Is it actually the case? –  Thomas Sep 13 '11 at 1:11
    
@Thomas: I don't seem how I'm using that, unless by "satisfying exactly" you mean that only the $S_j$ should satisfy the congruences. (In this latter case also the requirement that they form a subgroup/subspace would be necessary after all.) However, for finite dimension indeed $V^{\perp\perp}=V$; see e.g. here. –  joriki Sep 13 '11 at 3:09
    
I meant only the $S_j$. The link you've gave states "For a finite dimensional inner product space", but as far as I know, this isn't an "inner product space". –  Thomas Sep 13 '11 at 17:04
    
@Thomas: You're right, sorry, I didn't notice that. An inner product space has a notion of positivity, but we don't need that here; all we need is orthogonality. To see that $V^{\perp\perp}=V$, note that forming the orthogonal complement of a $k$-dimensional subspace of an $n$-dimensional space imposes $k$ linearly independent linear constraints and thus yields a subspace of dimension $n-k$; forming the orthogonal complement again imposes $n-k$ linearly independent linear constraints and thus yields a subspace of dimension $k$... –  joriki Sep 13 '11 at 17:37
    
... Since $V\subseteq V^{\perp\perp}$ and $V$ can't be properly contained in a subspace of the same dimension, we must have $V= V^{\perp\perp}$. I think my answer remains valid, except, as I said, since you meant only the $S_j$, of course they do have to form a subgroup/subspace. –  joriki Sep 13 '11 at 17:37

Here's a method which is most likely very impractical when $n$ is large. First, write a matrix $A$ whose rows are your subgroup elements. In the example, $$A=\pmatrix{0&0&0\cr1&1&1\cr}$$ Then write a matrix whose columns are all possible $n$-tuples of zeros and ones. For $n=3$, this is $$B=\pmatrix{0&0&0&0&1&1&1&1\cr0&0&1&1&0&0&1&1\cr0&1&0&1&0&1&0&1\cr}$$ The order of the columns of $B$ is immaterial. Each column of $B$ corresponds to a congruence, e.g., the column $(0,1,1)$ corresponds to $x_2+x_3\equiv0\pmod2$. Now form the product: $$AB=\pmatrix{0&0&0&0&0&0&0&0\cr0&1&1&0&1&0&0&1\cr}$$ Look at the all-zero columns of the product (namely, columns 1, 4, 6, and 7). The corresponding columns in $B$ give the congruences you want. The first column is the trivial congruence $0\equiv0\pmod2$, but the other columns give you $x_2+x_3\equiv0\pmod2$, $x_1+x_3\equiv0\pmod2$, and $x_2+x_3\equiv0\pmod2$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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