4
$\begingroup$

I have been trying to construct a orthogonal basis of $\mathbb{F}_{2}^{n}$ for an odd value of $n$ which is comprised of vectors which are not $1$ (to avoid the standard basis). In particular, to mirror the assumption on $n$, I want to ensure that the basis has only vectors with an odd number of $1$'s.

Is this possible? I have tried to prove otherwise, however have run out of ideas.

  • 0
    Maybe you mean [Hamming weight](http://en.wikipedia.org/wiki/Hamming_weight)?2012-11-23

1 Answers 1

1

If I denote the vectors $w_{i}$ and then their complements (that is the vectors obtained by switching 1 and 0 at each component) by $v_{i}$ I then have a collection, the $v_{i}$, of even weight vectors whose intersection with each other is odd.

Noting that the even weight vectors form a vector subspace of $\mathbb{F}_{2}^{n}$ of dimension $n-1$ we can deduce that there must be a dependence, and by playing around we can see that $\sum v_{i} = \mathbf{0}$. I can't see what to do though because this doesn't give me anything useable in the world of the $w_{i}$. I could transform the basis, $v_{1}, ... v_{n-1}$, of this $n-1$ dimensional space into some more canonical form, however under this basis change I cannot see that $v_{n}$ would retain any properties that would be useful in deriving a contradiction.

Even though I have this method of passing between the cases of even and odd weight I can't see an inductive method. Is there some nice isomorphism from the even weight vectors in $\mathbb{F}_{2}^{n}$ to $\mathbb{F}_{2}^{n-1}$ which will allow some form of induction? I can't see something that will obviously preserve weights/intersections enough to formulate some sort of inductive step.

As has been noted previously, the original result is true if we allow weight 1 vectors (namely the standard basis), and so it seems that if the result is false it would be possible to derive a contradiction at this point in the setup, however I can't see it.