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.

I was reading the current issue of AMM when I came across this term "space of relations", which I don't understand. Basically, we are given 9 vectors (0,1,0,0), (2,0,0,0), (1,1,0,0), (3,0,0,0), (2,1,0,0), (1,0,0,1), (1,2,0,0), (2,0,1,0), (3,1,0,0). We consider these vectors in $\mathbb{F}_2$ and we want to determine in how many ways can select some of them so that the sum is (0,0,0,0).

In the example above, the rank of the 9 exponent vectors over $\mathbb{F}_2$ is 4. Hence the space of relations has dimension 9 − 4 = 5 and thus we can construct $2^5 − 1 = 31$ non-trivial relations in this way.

In group theory, I know that a relation is some combination of elements that yields the identity. So, I'm guessing that a relation in this context is some combination of vectors that sum up to 0. But why is it of dimension 9 - 4 = 5?

share|improve this question

1 Answer 1

You have nine vectors. Consider the map from $T\colon\mathbb{F}_2^9\to\mathbb{F}_2^4$ given by $$T(a_1,\ldots,a_9) = a_1v_1+\cdots+a_9v_9$$ where $v_1,\ldots,v_9$ are the given vectors modulo $2$. Note that $T$ is a linear transformation.

A subset of the vectors that adds up to $0$ corresponds to an element of the kernel of $T$; the "space of relations" is precisely the kernel of $T$. It corresponds to the subspace of "linear dependency relations" (including the trivial relation) among $v_1,\ldots,v_9$.

Since the image of $T$ has dimension $4$ and the domain has dimension $9$, it follows that the kernel of $T$ has dimension $5$ (by the Rank-Nullity Theorem). That means there are $2^5 = 32$ vectors in the kernel, of which one (the zero vector) is the trivial relation. The rest give you relations (that is, subsets of the vectors that add up, modulo $2$, to $(0,0,0,0)$).

share|improve this answer
    
thanks a lot !! –  nahuo Apr 5 '12 at 6:30

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.