Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
How do you define orthogonality in $\mathbb F_2^n$? – Calle Nov 23 '12 at 21:14
What is $\mathbb{F}_{2}^{n}$? – Jonas Meyer Nov 23 '12 at 21:14
Sorry about that. I define orthogonality to be with respect to the inner product $\sum x_{i} y_{i} \pmod{2}$. $\mathbb{F}_{2}^{n} $ is just the field of 2 elements. – Usman Iqbal Nov 23 '12 at 21:15
Thanks. What does "magnitude" mean? – Jonas Meyer Nov 23 '12 at 21:16
The definition of inner product requires $\langle x,x\rangle \geq 0$, so you need an ordering on the scalars. And an ordered field has (a subfield isomorphic to) $\mathbb Q$ as its prime subfield. In particular no vector space over a finite field admits an inner product. What you have is a symmetric bilinear form on $\mathbb F_2^n$, but it's not an inner product. – kahen Nov 23 '12 at 21:20

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.

share|cite|improve this answer

Your Answer


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.