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.

  • 2
    How do you define orthogonality in $\mathbb F_2^n$?2012-11-23
  • 0
    What is $\mathbb{F}_{2}^{n}$?2012-11-23
  • 0
    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.2012-11-23
  • 1
    Thanks. What does "magnitude" mean?2012-11-23
  • 0
    Here I am really just counting the number of $1$s in the vector as the magnitude (so not by the inner product).2012-11-23
  • 3
    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.2012-11-23
  • 0
    Right, I asked because $\sum x_i^2$ is either $0$ or $1$ mod 2. Why call the number of 1s the magnitude? Is this standard terminology somewhere? Thanks for clarifying.2012-11-23
  • 0
    Sorry about the confusion.2012-11-23
  • 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.