# Dot product over $\mathbb{F}_2$ and orthogonality

In answer to the question here:

Lights out game on hexagonal grid

The following argument is given:

"Thus if v is in the null space of A, then d is orthogonal to v and as a consequence, d is in the row space of A."

Here everything is over $\mathbb{F}_2$, and the "inner product" is the standard dot product $x\cdot y=\sum_{i=1}^nx_iy_i$.

However, this is not an inner product at all! It may very well be the case that $x\cdot x=0$ but $x\ne 0$.

I'm sure that a certain amount of linear algebra can still be preserved here. In particular, if I can prove that $$\dim W + \dim W^\perp = \dim V$$ it will suffice. So my main question here is how can I prove the above equality in this setting.

-
Dear Gadi: The equality $\dim W + \dim W^\perp = \dim V$ holds whenever the bilinear form is non-degenerate. The proof is the obvious one. (I assume $\dim V < \infty$.) – Pierre-Yves Gaillard Jan 24 '12 at 15:53

Let $f$ be a non-degenerate bilinear form on a finite dimensional vector space $V$, let $W$ be a subspace, and let $X$ be the right orthogonal of $W$. Then we have $$\dim W+\dim X=\dim V.$$ Proof. The map $g:V\to V^*$ defined by $g(v)(v'):=f(v',v)$ is bijective.

The restriction map $V^*\to W^*$ is surjective and its kernel is $g(X)$.

-

The usual definition of inner product makes essential use of the properties of $\mathbb{R}$ and $\mathbb{C}$ and so is not really available for vector spaces over fields which are not subfields of $\mathbb{C}$. However, once we drop the positive-definiteness condition what we are left with is the notion of a non-degenerate symmetric bilinear form. Explicitly,

Definition. Let $V$ be a vector space over the field $k$. A non-degenerate symmetric bilinear form is a function $f : V \times V \to k$ with the following properties:

1. $f(v, w) = f(w, v)$
2. $f(\lambda v, w) = \lambda f(v, w)$
3. $f(u + v, w) = f(u, w) + f(v, w)$
4. If $f(v, w) = 0$ for all $w$, then $v = 0$.

Now, let $V$ be equipped be a non-degenerate symmetric bilinear form $(v, w) \mapsto \langle v, w \rangle$. This is good enough to make sense of various other notions in linear algebra, at least in the finite-dimensional case. (In the infinite-dimensional case things are better if we introduce some analytic/topological considerations.) From here on all vector spaces are assumed to be finite-dimensional and equipped with a non-degenerate symmetric bilinear form.

1. The linear map $V \to V^*$ defined by $v \mapsto \langle v, - \rangle$ is an isomorphism of vector spaces.

2. This implies that for any linear map $T : V \to W$, there is a unique linear map $T^* : W \to V$ such that $$\langle T^* v, w \rangle = \langle v, T w \rangle$$

3. For any subspace $U$, let $U^\perp$ be the subspace defined below: $$U^\perp = \{ w \in V : \forall u \in U . \, \langle u, w \rangle = 0 \}$$ It is precisely the kernel of the linear map $V \to U^*$ defined by $v \mapsto (w \mapsto \langle v, w \rangle)$. By (1) $V \to V^*$ is surjective, and the restriction map $V^* \to U^*$ is surjective (by choosing a basis of $U$ and extending to a basis of $V$), so by the rank-nullity theorem $$\dim U^\perp + \dim U^* = \dim U^\perp + \dim U = \dim V$$ as required.

Unfortunately, as Henning points out in the comments, it may happen that $U \cap U^\perp \ne \{ 0 \}$. A counterexample can be constructed in every even dimension. Let $n$ be a positive integer, and let $V = k^{2n}$ with standard basis vectors $e_1, \ldots, e_{2n}$. Suppose $\operatorname{char} k = 2$, i.e. $1 + 1 = 0$. Let $$\langle e_i, e_j \rangle = \begin{cases} 1 & \text{if } i + n = j \text{ or } j + n = i \\ 0 & \text{otherwise} \end{cases}$$ and extend to bilinearly to $V \times V$. This is easily checked to be a non-degenerate symmetric bilinear form, but by construction $\langle e_i, e_i \rangle = 0$ for each $e_i$! (But, for $\operatorname{char} k \ne 2$, there exist some vector $v$ so that $\langle v, v \rangle = 0$.)

-
How about $V=(\mathbb F_2)^2$ and define $\langle v,w\rangle=1$ iff $v$ and $w$ are different nonzero vectors? In that case $U^\bot=U$ for a one-dimensional subspace $\{0,v\}$, so $U\cap U^\bot=\{0\}$ seems to fail. Or did I miss some condition on "nondegenerate symmetric bilinear form" that this example doesn't satisfy? (I think this is basically a case of the usual equivalence between "symmetric bilinear" and "quadratic" forms breaking down in characteristic 2). – Henning Makholm Jan 24 '12 at 17:18
@Henning: That seems to be the only part of the theorem that breaks – everything else is still true, though we have to weaken "equals" to "is isomorphic to" in $V \cong U \oplus U^\perp$. – Zhen Lin Jan 24 '12 at 18:12
Not only is it true that it might happen that $U \cap U^\perp \ne \{ 0 \}$, but it might also be that $U = U^\perp$. Over $(\mathbb F_2)^2$ equipped with the usual inner product, if $U$ is the one-dimensional subspace $U = \{[0,0], [1,1]\}$, then $U^\perp = U$. There is some literature in coding theory on the topic of self-dual codes, subspaces $U$ of dimension $n$ of the $2n$-dimensional space $(\mathbb F_2)^{2n}$ for which $U^\perp = U$. – Dilip Sarwate Jan 24 '12 at 19:46