0
$\begingroup$

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?

1 Answers 1

2

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